Algorithms for Parity Games

DOI10.1007/3-540-36387-4_7MaRDI QIDQ4412830zbMATH OpenOpenAlexFDO

Authors Hartmut Klauck

Publication date 16 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-36387-4_7

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Nonnumerical algorithms (68W05) 2-person games (91A05) Games involving graphs (91A43)

Recommendations

• Algorithms for solving parity games
• Parameterized Algorithms for Parity Games
• The fixpoint-iteration algorithm for parity games
• scientific article; zbMATH DE number 7650845
• Solving parity games using an automata-based algorithm
• scientific article; zbMATH DE number 1962853
• Solving parity games in practice
• A Deterministic Subexponential Algorithm for Solving Parity Games

Cited in

(22)

• Parity game reductions
• Complexity of tropical and MIN-plus linear prevarieties
• Game aspect of program verification
• scientific article; zbMATH DE number 1670778 (Why is no real title available?)
• Games for verification: Algorithmic issues
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Parameterized Algorithms for Parity Games
• scientific article; zbMATH DE number 5823948 (Why is no real title available?)
• Recursive algorithm for parity games requires exponential time
• scientific article; zbMATH DE number 1810492 (Why is no real title available?)
• Algorithms for solving parity games
• Alternating traps in Muller and parity games
• Memoryless Determinacy of Parity Games
• scientific article; zbMATH DE number 1962853 (Why is no real title available?)
• Polynomial-time under-approximation of winning regions in parity games
• The fixpoint-iteration algorithm for parity games
• Improvement in small progress measures
• Improved algorithms for parity and Streett objectives
• A Multi-Core Solver for Parity Games
• Generalized Parity Games
• Parallel repetition for all 3-player games over binary alphabet
• Justifications and a reconstruction of parity game solving algorithms

This page was built for publication: Algorithms for Parity Games

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