The Descriptive Complexity of Parity Games
From MaRDI portal
Publication:3540190
DOI10.1007/978-3-540-87531-4_26zbMath1157.68032OpenAlexW1591239571WikidataQ58215591 ScholiaQ58215591MaRDI QIDQ3540190
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
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
