A randomized subexponential algorithm for parity games

MaRDI QIDQ2765924zbMATH OpenFDO

Authors Viktor Petersson, Sergei Vorobyov

Publication date 24 January 2002

Published in Nordic Journal of Computing (Search for Journal in Brave)

zbMATH Keywords

mu-calculus model checkingparity games

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Game theory (91A99)

Recommendations

• scientific article; zbMATH DE number 1962853
• A Deterministic Subexponential Algorithm for Solving Parity Games
• A subexponential lower bound for the random facet algorithm for parity games
• Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games
• A subexponential randomized algorithm for the simple stochastic game problem
• Parameterized Algorithms for Parity Games
• Subexponential algorithms for unique games and related problems
• Combinatorial structure and randomized subexponential algorithms for infinite games
• The fixpoint-iteration algorithm for parity games
• A recursive approach to solving parity games in quasipolynomial time

Cited in

(15)

• Parity game reductions
• A subexponential randomized algorithm for the simple stochastic game problem
• A sublinear-time randomized approximation algorithm for matrix games
• Recursive algorithm for parity games requires exponential time
• scientific article; zbMATH DE number 7445162 (Why is no real title available?)
• A Deterministic Subexponential Algorithm for Solving Parity Games
• The Stevens-Stirling-algorithm for solving parity games locally requires exponential time
• Derandomized parallel repetition theorems for free games
• scientific article; zbMATH DE number 1962853 (Why is no real title available?)
• Deciding Parity Games in Quasi-polynomial Time
• A subexponential lower bound for the random facet algorithm for parity games
• An Accelerated Algorithm for 3-Color Parity Games with an Application to Timed Games
• Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games
• Combinatorial structure and randomized subexponential algorithms for infinite games
• The Rabin index of parity games: its complexity and approximation

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

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