Precise interval analysis vs. parity games

Thomas Gawlitza, Helmut Seidl

Research output: Contribution to journalConference articlepeer-review

6 Scopus citations


In [8], a practical algorithm for precise interval analysis is provided for which, however, no non-trivial upper complexity bound is known. Here, we present a lower bound by showing that precise interval analysis is at least as hard as computing the sets of winning positions in parity games. Our lower-bound proof relies on an encoding of parity games into systems of particular integer equations. Moreover, we present a simplification of the algorithm for integer systems from [8]. For the given encoding of parity games, the new algorithm provides another algorithm for parity games which is almost as efficient as the discrete strategy improvement algorithm by Vöge and Jurdziński [17].

Original languageEnglish
Pages (from-to)342-357
Number of pages16
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5014 LNCS
StatePublished - 2008
Event15th International Symposium on Formal Methods, FM 2008 - Turku, Finland
Duration: 26 May 200830 May 2008


Dive into the research topics of 'Precise interval analysis vs. parity games'. Together they form a unique fingerprint.

Cite this