Solving Parity Games in Practice
From MaRDI portal
Publication:3648698
DOI10.1007/978-3-642-04761-9_15zbMath1258.68077OpenAlexW2168360220MaRDI QIDQ3648698
Martin Lange, Oliver Friedmann
Publication date: 1 December 2009
Published in: Automated Technology for Verification and Analysis (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-04761-9_15
2-person games (91A05) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items (32)
Family-Based SPL Model Checking Using Parity Games with Variability ⋮ Parity game reductions ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Robust worst cases for parity games algorithms ⋮ Index appearance record with preorders ⋮ Reachability games and parity games ⋮ Efficiently Deciding μ-Calculus with Converse over Finite Trees ⋮ The Rabin index of parity games: its complexity and approximation ⋮ HyperATL*: A Logic for Hyperproperties in Multi-Agent Systems ⋮ Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games ⋮ Solving mean-payoff games via quasi dominions ⋮ Graph operations on parity games and polynomial-time algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Automated temporal equilibrium analysis: verification and synthesis of multi-player games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis ⋮ Index Appearance Record for Transforming Rabin Automata into Parity Automata ⋮ Solving parity games via priority promotion ⋮ Solving Mean-Payoff Games via Quasi Dominions ⋮ Using the compatibility analysis of logical specifications of automata to solve game problems ⋮ A Decision Procedure for CTL* Based on Tableaux and Automata ⋮ Verification of reactive systems via instantiation of parameterised Boolean equation systems ⋮ A delayed promotion policy for parity games ⋮ Improving parity games in practice ⋮ PGSolver ⋮ Solving Parity Games Using an Automata-Based Algorithm ⋮ Recursive algorithm for parity games requires exponential time
Cites Work
- Unnamed Item
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Games for synthesis of controllers with partial observation.
- Complementation, Disambiguation, and Determinization of Büchi Automata Unified
- An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
- A deterministic subexponential algorithm for solving parity games
- Polynomial-Time Under-Approximation of Winning Regions in Parity Games
- A Multi-Core Solver for Parity Games
- Solving Parity Games in Big Steps
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: Solving Parity Games in Practice
