Thomas Gawlitza and Helmut Seidl. Precise Interval Analysis vs. Parity Games. In Jorge Cuéllar, T. S. E. Maibaum and Kaisa Sere, editors, FM, volume 5014 of Lecture Notes in Computer Science, pages 342-357, Turku, Finland, May 2008. Springer.

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].

Download: PDF Reference: Bibtex The original publication is available at