@article{464,
  abstract     = {The computation of the winning set for parity objectives and for Streett objectives in 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-formedness of specifications, and the synthesis of reactive systems. We show how to compute the winning set on n vertices for (1) parity-3 (aka one-pair Streett) objectives in game graphs in time O(n5/2) and for (2) k-pair Streett objectives in graphs in time O(n2+nklogn). For both problems this gives faster algorithms for dense graphs and represents the first improvement in asymptotic running time in 15 years.},
  author       = {Chatterjee, Krishnendu and Henzinger, Monika H and Loitzenbauer, Veronika},
  issn         = {1860-5974},
  journal      = {Logical Methods in Computer Science},
  number       = {3},
  publisher    = {International Federation of Computational Logic},
  title        = {{Improved algorithms for parity and Streett objectives}},
  doi          = {10.23638/LMCS-13(3:26)2017},
  volume       = {13},
  year         = {2017},
}