A Deterministic Subexponential Algorithm for Solving Parity Games
From MaRDI portal
Publication:3395043
DOI10.1137/070686652zbMath1173.91326MaRDI 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
games on graphs; discrete-time games; specification and verification; 2-player games; analysis of algorithms and problem complexity
68Q25: Analysis of algorithms and problem complexity
91A05: 2-person games
91A50: Discrete-time games
91A43: Games involving graphs
Related Items
Deciding the unguarded modal -calculus, Unnamed Item, Unnamed Item, Unnamed Item, Deciding Parity Games in Quasi-polynomial Time, Unnamed Item, Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time, Unnamed Item, Solving parity games in big steps, Parity games on undirected graphs, Mean-payoff games and propositional proofs, Extending finite-memory determinacy to multi-player games, Latticed-LTL synthesis in the presence of noisy inputs, Solving parity games via priority promotion, New deterministic algorithms for solving parity games, A delayed promotion policy for parity games, Improving parity games in practice, Robust worst cases for parity games algorithms, Hierarchical cost-parity games, An accretive operator approach to ergodic zero-sum stochastic games, A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors, Solving Parity Games Using an Automata-Based Algorithm, TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES, ON MODAL μ-CALCULUS OVER FINITE GRAPHS WITH SMALL COMPONENTS OR SMALL TREE WIDTH, Parameterized Algorithms for Parity Games, Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games, Many-one reductions and the category of multivalued functions, The mu-calculus and Model Checking, From Parity and Payoff Games to Linear Programming, Unnamed Item, Symmetric Strategy Improvement
