Recursive algorithm for parity games requires exponential time

DOI10.1051/ita/2011124zbMath1232.91064OpenAlexW2047201474MaRDI QIDQ3117548

Oliver Friedmann

Publication date: 28 February 2012

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/222001

zbMATH Keywords

\(\mu\)-calculusparity gameslower boundmodel checkingrecursive algorithm

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (11)

Robust worst cases for parity games algorithms ⋮ Parity Games and Propositional Proofs ⋮ Reachability games and parity games ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time

Uses Software

• PGSolver

Cites Work

• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• A deterministic subexponential algorithm for solving parity games
• Solving Parity Games in Practice
• Solving Parity Games in Big Steps
• On model checking for the \(\mu\)-calculus and its fragments

This page was built for publication: Recursive algorithm for parity games requires exponential time