Earlier Version

Improved algorithms for one-pair and k-pair Streett objectives

K. Chatterjee, M. Henzinger, V. Loitzenbauer, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015, p. 7174888.


Conference Paper | Published | English
Author
; ;
Department
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.
Publishing Year
Date Published
2015-07-01
Proceedings Title
Proceedings - Symposium on Logic in Computer Science
Acknowledgement
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.
Volume
2015-July
Article Number
7174888
Conference
LICS: Logic in Computer Science
Conference Location
Kyoto, Japan
Conference Date
2015-07-06 – 2015-07-10
IST-REx-ID

Cite this

Chatterjee K, Henzinger M, Loitzenbauer V. Improved algorithms for one-pair and k-pair Streett objectives. In: Proceedings - Symposium on Logic in Computer Science. Vol 2015-July. IEEE; 2015:7174888. doi:10.1109/LICS.2015.34
Chatterjee, K., Henzinger, M., & Loitzenbauer, V. (2015). Improved algorithms for one-pair and k-pair Streett objectives. In Proceedings - Symposium on Logic in Computer Science (Vol. 2015–July, p. 7174888). Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.34
Chatterjee, Krishnendu, Monika Henzinger, and Veronika Loitzenbauer. “Improved Algorithms for One-Pair and k-Pair Streett Objectives.” In Proceedings - Symposium on Logic in Computer Science, 2015–July:7174888. IEEE, 2015. https://doi.org/10.1109/LICS.2015.34.
K. Chatterjee, M. Henzinger, and V. Loitzenbauer, “Improved algorithms for one-pair and k-pair Streett objectives,” in Proceedings - Symposium on Logic in Computer Science, Kyoto, Japan, 2015, vol. 2015–July, p. 7174888.
Chatterjee K, Henzinger M, Loitzenbauer V. 2015. Improved algorithms for one-pair and k-pair Streett objectives. Proceedings - Symposium on Logic in Computer Science. LICS: Logic in Computer Science vol. 2015–July. 7174888.
Chatterjee, Krishnendu, et al. “Improved Algorithms for One-Pair and k-Pair Streett Objectives.” Proceedings - Symposium on Logic in Computer Science, vol. 2015–July, IEEE, 2015, p. 7174888, doi:10.1109/LICS.2015.34.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar