Precise interval analysis vs. parity games

Thomas Gawlitza, Helmut Seidl

Publikation: Beitrag in FachzeitschriftKonferenzartikelBegutachtung

6 Zitate (Scopus)

Abstract

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

OriginalspracheEnglisch
Seiten (von - bis)342-357
Seitenumfang16
FachzeitschriftLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Jahrgang5014 LNCS
DOIs
PublikationsstatusVeröffentlicht - 2008
Veranstaltung15th International Symposium on Formal Methods, FM 2008 - Turku, Finnland
Dauer: 26 Mai 200830 Mai 2008

Fingerprint

Untersuchen Sie die Forschungsthemen von „Precise interval analysis vs. parity games“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren