THE STEVENS-STIRLING-ALGORITHM FOR SOLVING PARITY GAMES LOCALLY REQUIRES EXPONENTIAL TIME.

Authors :: FRIEDMANN, OLIVER
Sakarovitch, Jacques
Source :: International Journal of Foundations of Computer Science; Jun2010, Vol. 21 Issue 3, p277-287, 11p, 2 Diagrams, 1 Chart
Publication Year :: 2010
Abstract: This paper presents a new lower bound for the model-checking algorithm based on solving parity games due to Stevens and Stirling. We outline a family of games of linear size on which the algorithm requires exponential time. [ABSTRACT FROM AUTHOR]

Subjects :: ALGORITHMS
EXPONENTIAL functions
LINEAR systems
COMPUTER systems
COMPUTER science

Full Text Access

Tools