Solving parity games in big steps

DOI10.1016/J.JCSS.2016.10.002MaRDI QIDQ340584zbMATH OpenOpenAlexFDO

Authors Sven Schewe

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

zbMATH Keywords

finite games of infinite durationparity games

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Applications of game theory (91A80)

Recommendations

• Solving Parity Games in Big Steps
• Solving parity games via priority promotion
• A modal \(\mu\) perspective on solving parity games in quasi-polynomial time
• Algorithms for solving parity games
• Solving parity games via priority promotion

Cites work

• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• A Deterministic Subexponential Algorithm for Solving Parity Games
• A subexponential randomized algorithm for the simple stochastic game problem
• Alternating tree automata, parity games, and modal -calculus
• Alternating-time temporal logic
• An improved algorithm for the evaluation of fixpoint expressions
• DAG-Width and Parity Games
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Fast mu-calculus model checking when tree-width is bounded.
• From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
• scientific article; zbMATH DE number 1670778 (Why is no real title available?)
• scientific article; zbMATH DE number 1223729 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• Memoryless determinacy of parity and mean payoff games: a simple proof
• Results on the propositional \(\mu\)-calculus
• Satisfiability and Finite Model Property for the Alternating-Time μ-Calculus
• Solving Parity Games in Big Steps
• Synthesis of Asynchronous Systems
• The complexity of mean payoff games on graphs
• Tighter Bounds for the Determinisation of Büchi Automata
• Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width

Cited in

(20)

• Parity game reductions
• Automata on infinite trees
• Robust worst cases for parity games algorithms
• Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games
• Solving parity games by a reduction to SAT
• Zielonka's recursive algorithm: dull, weak and solitaire games and tighter bounds
• Improvement in small progress measures
• A recursive approach to solving parity games in quasipolynomial time
• Deciding Parity Games in Quasi-polynomial Time
• scientific article; zbMATH DE number 7533361 (Why is no real title available?)
• Büchi Good-for-Games Automata Are Efficiently Recognizable
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• Solving Parity Games on the GPU
• Parity games with weights
• Mathematical Foundations of Computer Science 2003
• Solving Parity Games in Big Steps
• Improved complexity analysis of quasi-polynomial algorithms solving parity games
• Synthesizing Computable Functions from Rational Specifications Over Infinite Words
• Priority promotion with Parysian flair
• Beyond value iteration for parity games: strategy iteration with universal trees

This page was built for publication: Solving parity games in big steps

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