Solving parity games in big steps
From MaRDI portal
Publication:340584
DOI10.1016/j.jcss.2016.10.002zbMath1353.68180OpenAlexW2531928804MaRDI QIDQ340584
Publication date: 14 November 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2016.10.002
Applications of game theory (91A80) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items
Deciding Parity Games in Quasi-polynomial Time, Unnamed Item, Robust worst cases for parity games algorithms, Improved complexity analysis of quasi-polynomial algorithms solving parity games, Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games, Synthesizing Computable Functions from Rational Specifications Over Infinite Words, Unnamed Item, Büchi Good-for-Games Automata Are Efficiently Recognizable, Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time, Automata on infinite trees
Cites Work
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Results on the propositional \(\mu\)-calculus
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Infinite games played on finite graphs
- The complexity of mean payoff games on graphs
- An improved algorithm for the evaluation of fixpoint expressions
- Memoryless determinacy of parity and mean payoff games: a simple proof
- A subexponential randomized algorithm for the simple stochastic game problem
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Alternating-time temporal logic
- Synthesis of Asynchronous Systems
- Satisfiability and Finite Model Property for the Alternating-Time μ-Calculus
- Tighter Bounds for the Determinisation of Büchi Automata
- Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width
- From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
- DAG-Width and Parity Games
- Solving Parity Games in Big Steps
- Computer Aided Verification
- Alternating tree automata, parity games, and modal \(\mu\)-calculus
- Unnamed Item
- Unnamed Item
- Unnamed Item
