%0 Journal Article
%T Improved Algorithms for One-Pair and k-Pair Streett Objectives
%A Krishnendu Chatterjee
%A Monika Henzinger
%A Veronika Loitzenbauer
%J Computer Science
%D 2014
%I arXiv
%X 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 open systems, checking interface compatibility, well-formedness of specifications, the synthesis of systems from 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.
%U http://arxiv.org/abs/1410.0833v2