Solving Parity Games Using an Automata-Based Algorithm

DOI10.1007/978-3-319-40946-7_6zbMath1475.68475arXiv1910.13765OpenAlexW2494824293MaRDI QIDQ2830208

Giuseppe Perelli, Antonio Di Stasio, Moshe Y. Vardi, Aniello Murano

Publication date: 9 November 2016

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.13765

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Games involving graphs (91A43) Applications of game theory (91A80) Formal languages and automata (68Q45)

Related Items

Deciding Parity Games in Quasi-polynomial Time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improving parity games in practice ⋮ Unnamed Item ⋮ On the Way to Alternating Weak Automata

Uses Software

• CESAR
• PGSolver

Cites Work

• 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 by a reduction to SAT
• Improved model checking of hierarchical systems
• Results on the propositional \(\mu\)-calculus
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Module checking
• On Promptness in Parity Games
• Generalized Mean-payoff and Energy Games
• A Deterministic Subexponential Algorithm for Solving Parity Games
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• Admissibility in Infinite Games
• Facets of Synthesis: Revisiting Church’s Problem
• Solving Parity Games in Practice
• Polynomial-Time Under-Approximation of Winning Regions in Parity Games
• An automata-theoretic approach to branching-time model checking
• An Accelerated Algorithm for 3-Color Parity Games with an Application to Timed Games
• Solving Parity Games in Big Steps
• Alternating tree automata, parity games, and modal \(\mu\)-calculus