Polynomial-Time Under-Approximation of Winning Regions in Parity Games
From MaRDI portal
Publication:4982057
DOI10.1016/j.entcs.2008.12.070zbMath1336.68286MaRDI QIDQ4982057
Adam Antonik, Nathaniel Charlton, Michael Huth
Publication date: 23 March 2015
Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.entcs.2008.12.070
68Q25: Analysis of algorithms and problem complexity
91A05: 2-person games
91A43: Games involving graphs
68R10: Graph theory (including graph drawing) in computer science
68Q60: Specification and verification (program logics, model checking, etc.)
68W25: Approximation algorithms
Related Items
Polynomial-Time Under-Approximation of Winning Regions in Parity Games, Improving parity games in practice, Solving Parity Games Using an Automata-Based Algorithm, Solving Parity Games in Practice
Cites Work
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Results on the propositional \(\mu\)-calculus
- Local model checking in the modal mu-calculus
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Automata, logics, and infinite games. A guide to current research
- Memoryless Determinacy of Parity Games
- Algorithms for Parity Games
- Polynomial-Time Under-Approximation of Winning Regions in Parity Games
- DAG-Width and Parity Games
- Logic for Programming, Artificial Intelligence, and Reasoning