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

DOI10.1142/S0129054110007246zbMATH Open1188.91044OpenAlexW2147642428MaRDI QIDQ3569271FDOQ3569271

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

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

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)

Cited In (1)

• Recursive algorithm for parity games requires exponential time

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)