A deterministic subexponential algorithm for solving parity games

DOI10.1145/1109557.1109571MaRDI QIDQ3581528zbMATH OpenOpenAlexFDO

Authors Marcin Jurdziński, Uri Zwick, Mike Paterson

Publication date 16 August 2010

Published in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.7326

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43)

Cited in

(33)

• Recursive algorithm for parity games requires exponential time
• Inf-datalog, Modal Logic and Complexities
• A superpolynomial lower bound for strategy iteration based on snare memorization
• Meanings of model checking
• The Descriptive Complexity of Parity Games
• A survey of stochastic -regular games
• Solving parity games by a reduction to SAT
• scientific article; zbMATH DE number 7445162 (Why is no real title available?)
• The complexity of all-switches strategy improvement
• A Multi-Core Solver for Parity Games
• Solving parity games via priority promotion
• Cyclic games and linear programming
• Graph operations on parity games and polynomial-time algorithms
• Parity game reductions
• A quasi-polynomial black-box algorithm for fixed point evaluation
• Priority promotion with Parysian flair
• On short paths interdiction problems: Total and node-wise limited interdiction
• Graph Games and Reactive Synthesis
• The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
• Solving Parity Games in Big Steps
• Concurrent reachability games
• Cooking Your Own Parity Game Preorders Through Matching Plays
• A convex programming-based algorithm for mean payoff stochastic games with perfect information
• Solving μ-Calculus Parity Games by Symbolic Planning
• Robust worst cases for parity games algorithms
• On canonical forms for zero-sum stochastic mean payoff games
• A CSP-Based Approach for Solving Parity Game
• Improvement in small progress measures
• Solving parity games in practice
• Value Iteration
• Partial solvers for parity games: effective polynomial-time composition
• The complexity of rational synthesis for concurrent games
• Alternating traps in Muller and parity games

This page was built for publication: A deterministic subexponential algorithm for solving parity games

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