A Deterministic Subexponential Algorithm for Solving Parity Games

DOI10.1137/070686652zbMath1173.91326OpenAlexW2158437920MaRDI QIDQ3395043

Uri Zwick, Marcin Jurdziński, Mike S. Paterson

Publication date: 20 August 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070686652

zbMATH Keywords

games on graphsdiscrete-time gamesspecification and verification2-player gamesanalysis of algorithms and problem complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Discrete-time games (91A50) Games involving graphs (91A43)

Related Items (32)

TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES ⋮ Symmetric Strategy Improvement ⋮ The mu-calculus and Model Checking ⋮ Extending finite-memory determinacy to multi-player games ⋮ ON MODAL μ-CALCULUS OVER FINITE GRAPHS WITH SMALL COMPONENTS OR SMALL TREE WIDTH ⋮ From Parity and Payoff Games to Linear Programming ⋮ Solving parity games in big steps ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Unnamed Item ⋮ Latticed-LTL synthesis in the presence of noisy inputs ⋮ Deciding the unguarded modal -calculus ⋮ Robust worst cases for parity games algorithms ⋮ Parameterized Algorithms for Parity Games ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games ⋮ Many-one reductions and the category of multivalued functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hierarchical cost-parity games ⋮ Unnamed Item ⋮ Parity games on undirected graphs ⋮ Solving parity games via priority promotion ⋮ New deterministic algorithms for solving parity games ⋮ Unnamed Item ⋮ Mean-payoff games and propositional proofs ⋮ An accretive operator approach to ergodic zero-sum stochastic games ⋮ A delayed promotion policy for parity games ⋮ A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors ⋮ Improving parity games in practice ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ Solving Parity Games Using an Automata-Based Algorithm ⋮ Unnamed Item

This page was built for publication: A Deterministic Subexponential Algorithm for Solving Parity Games