A deterministic subexponential algorithm for solving parity games

DOI10.1145/1109557.1109571zbMath1192.91013MaRDI QIDQ3581528

Uri Zwick, Marcin Jurdziński, Mike S. 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

91A43: Games involving graphs

68Q60: Specification and verification (program logics, model checking, etc.)

91-04: Software, source code, etc. for problems pertaining to game theory, economics, and finance

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Meanings of Model Checking, A Multi-Core Solver for Parity Games, Solving Parity Games in Big Steps, On canonical forms for zero-sum stochastic mean payoff games, Alternating traps in Muller and parity games, A survey of stochastic \(\omega \)-regular games, Solving parity games by a reduction to SAT, The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs, Graph operations on parity games and polynomial-time algorithms, On short paths interdiction problems: Total and node-wise limited interdiction, Cyclic games and linear programming, Parity game reductions, A convex programming-based algorithm for mean payoff stochastic games with perfect information, Solving parity games via priority promotion, Robust worst cases for parity games algorithms, A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions, A superpolynomial lower bound for strategy iteration based on snare memorization, Concurrent reachability games, Recursive algorithm for parity games requires exponential time, Graph Games and Reactive Synthesis, Cooking Your Own Parity Game Preorders Through Matching Plays, Unnamed Item, A CSP-Based Approach for Solving Parity Game, Value Iteration, The Descriptive Complexity of Parity Games, Inf-datalog, Modal Logic and Complexities, Solving μ-Calculus Parity Games by Symbolic Planning, Solving Parity Games in Practice