The Descriptive Complexity of Parity Games

DOI10.1007/978-3-540-87531-4_26zbMath1157.68032OpenAlexW1591239571WikidataQ58215591 ScholiaQ58215591MaRDI QIDQ3540190

Erich Grädel, Anuj Dawar

Publication date: 20 November 2008

Published in: Computer Science Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-87531-4_26

Mathematics Subject Classification ID

Games involving graphs (91A43) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)

Related Items (7)

Cooking Your Own Parity Game Preorders Through Matching Plays ⋮ Choice functions and well-orderings over the infinite binary tree ⋮ Entanglement and the complexity of directed graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quasipolynomial computation of nested fixpoints ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Finite model theory and its applications.
• The modal mu-calculus alternation hierarchy is strict
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Fixed-point logics and solitaire games
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Computing with first-order logic
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• A deterministic subexponential algorithm for solving parity games
• DAG-width
• Clique-Width and Parity Games
• Fixpoint logics, relational machines, and computational complexity
• Fixed Point Logics
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• Positional Determinacy of Games with Infinitely Many Priorities
• DAG-Width and Parity Games
• Logic for Programming, Artificial Intelligence, and Reasoning
• Back and forth between guarded and modal logics
• Computer Aided Verification

This page was built for publication: The Descriptive Complexity of Parity Games