Improved algorithms for one-pair and k-pair streett objectives Conference Paper


Author(s): Chatterjee, Krishnendu; Henzinger, Monika R; Loitzenbauer, Veronika
Title: Improved algorithms for one-pair and k-pair streett objectives
Affiliation IST Austria
Abstract: The computation of the winning set for one-pair Streett objectives and for k-pair Streett objectives in (standard) graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formed ness of specifications, and the synthesis of reactive systems. We give faster algorithms for the computation of the winning set for (1) one-pair Streett objectives (aka parity-3 problem) in game graphs and (2) for k-pair Streett objectives in graphs. For both problems this represents the first improvement in asymptotic running time in 15 years.
Keywords: synthesis; Computer-aided verification; Graph games; Parity games; Graph algorithms; Streett automata
Conference Title: LICS: Logic in Computer Science
Conference Dates: July 6-10, 2015
Conference Location: Kyoto, Japan
ISBN: 978-147998875-4
Publisher: IEEE  
Date Published: 2015-07-01
Start Page: 269
End Page: 280
URL:
DOI: 10.1109/LICS.2015.34
Notes: K. C. is supported by the Austrian Science Fund (FWF): P23499-N23 and S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games), and a Microsoft Faculty Fellows Award. M. H. is supported by the Austrian Science Fund (FWF): P23499-N23 and the Vienna Science and Technology Fund (WWTF) grant ICT10-002. V. L. is supported by the Vienna Science and Technology Fund (WWTF) grant ICT10-002. The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement no. 340506.
Open access: yes (repository)
IST Austria Authors