Robust worst cases for parity games algorithms

DOI10.1016/j.ic.2019.104501zbMath1443.68067OpenAlexW2996393320MaRDI QIDQ2182730

Daniele Dell'Erba, Massimo Benerecetti, Fabio Mogavero

Publication date: 26 May 2020

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2019.104501

zbMATH Keywords

parity gamesformal methodsinfinite-duration games on graphs

Mathematics Subject Classification ID

Games involving graphs (91A43) Applications of game theory (91A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Unnamed Item ⋮ Unnamed Item

Uses Software

• PGSolver
• Oink

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Solving parity games in big steps
• Strategy logic
• Positional strategies for mean payoff games
• The complexity of stochastic games
• Borel determinacy
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• The complexity of mean payoff games on graphs
• Solving parity games via priority promotion
• Fixed-point logics and solitaire games
• Automata, logics, and infinite games. A guide to current research
• A superpolynomial lower bound for strategy iteration based on snare memorization
• What Makes Atl* Decidable? A Decidable Fragment of Strategy Logic
• Reasoning About Strategies
• Reasoning About Substructures and Games
• Non-oblivious Strategy Improvement
• Recursive algorithm for parity games requires exponential time
• A Deterministic Subexponential Algorithm for Solving Parity Games
• Alternating-time temporal logic
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• ATL* Satisfiability Is 2EXPTIME-Complete
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• A deterministic subexponential algorithm for solving parity games
• Satisfiability and Finite Model Property for the Alternating-Time μ-Calculus
• Solving Parity Games in Practice
• Solving Parity Games via Priority Promotion
• Deciding parity games in quasipolynomial time
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• Benchmark Graphs for Practical Graph Isomorphism
• A modal μ perspective on solving parity games in quasi-polynomial time
• Substructure Temporal Logic
• Graph isomorphism in quasipolynomial time [extended abstract]
• Solving Parity Games in Big Steps
• On model checking for the \(\mu\)-calculus and its fragments
• Alternating tree automata, parity games, and modal \(\mu\)-calculus
• Attracting tangles to solve parity games

This page was built for publication: Robust worst cases for parity games algorithms