Polynomial-Time Under-Approximation of Winning Regions in Parity Games

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

zbMATH Keywords

algorithms; computational complexity; parity games; abstraction

Mathematics Subject Classification ID

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