The Stevens-Stirling-algorithm for solving parity games locally requires exponential time

DOI10.1142/S0129054110007246MaRDI QIDQ3569271zbMATH OpenOpenAlexFDO

Authors Oliver Friedmann

Publication date 18 June 2010

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054110007246

zbMATH Keywords

lower boundexponential boundparity game\(\mu\)-calculus model checkingStevens-Stirling algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43)

Recommendations

• Recursive algorithm for parity games requires exponential time
• scientific article; zbMATH DE number 1962853
• A randomized subexponential algorithm for parity games
• A Deterministic Subexponential Algorithm for Solving Parity Games
• Exponential examples of solving parity games

Cited in

(2)

• An exponential lower bound for the latest deterministic strategy iteration algorithms
• Recursive algorithm for parity games requires exponential time

Describes a project that uses

Uses Software

• PGSolver

This page was built for publication: The Stevens-Stirling-algorithm for solving parity games locally requires exponential time

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