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

DOI10.1016/J.ENTCS.2008.12.070zbMath1336.68286OpenAlexW2133559308MaRDI 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

algorithmscomputational complexityparity gamesabstraction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Approximation algorithms (68W25)

Related Items (4)

Improving parity games in practice ⋮ Polynomial-Time Under-Approximation of Winning Regions in Parity Games ⋮ 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

This page was built for publication: Polynomial-Time Under-Approximation of Winning Regions in Parity Games