The Descriptive Complexity of Parity Games

DOI10.1007/978-3-540-87531-4_26MaRDI QIDQ3540190zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Anuj Dawar, Erich Grädel

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

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

Recommendations

• Defining winning strategies in fixed-point logic
• Once upon a time in the West. Determinacy, definability, and complexity of path games
• Back and forth between logic and games
• Game logic is strong enough for parity games
• Parity games and automata for game logic

Cites work

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

Cited in

(15)

• Game logic is strong enough for parity games
• Fixed-point logics and solitaire games
• Entanglement and the complexity of directed graphs
• Quasipolynomial computation of nested fixpoints
• Back and forth between logic and games
• Cooking Your Own Parity Game Preorders Through Matching Plays
• The descriptive complexity of modal model-checking games
• scientific article; zbMATH DE number 7447732 (Why is no real title available?)
• Once upon a time in the West. Determinacy, definability, and complexity of path games
• A New Pebble Game that Characterizes Parallel Complexity Classes
• Defining winning strategies in fixed-point logic
• Register games
• Choice functions and well-orderings over the infinite binary tree
• A logical description of priority separable games
• The Rabin index of parity games: its complexity and approximation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3540190)