---
_id: '1661'
abstract:
- lang: eng
  text: 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.
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.'
article_number: '7174888'
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Veronika
  full_name: Loitzenbauer, Veronika
  last_name: Loitzenbauer
citation:
  ama: 'Chatterjee K, Henzinger M, Loitzenbauer V. Improved algorithms for one-pair
    and k-pair Streett objectives. In: <i>Proceedings - Symposium on Logic in Computer
    Science</i>. Vol 2015-July. IEEE; 2015. doi:<a href="https://doi.org/10.1109/LICS.2015.34">10.1109/LICS.2015.34</a>'
  apa: 'Chatterjee, K., Henzinger, M., &#38; Loitzenbauer, V. (2015). Improved algorithms
    for one-pair and k-pair Streett objectives. In <i>Proceedings - Symposium on Logic
    in Computer Science</i> (Vol. 2015–July). Kyoto, Japan: IEEE. <a href="https://doi.org/10.1109/LICS.2015.34">https://doi.org/10.1109/LICS.2015.34</a>'
  chicago: Chatterjee, Krishnendu, Monika Henzinger, and Veronika Loitzenbauer. “Improved
    Algorithms for One-Pair and k-Pair Streett Objectives.” In <i>Proceedings - Symposium
    on Logic in Computer Science</i>, Vol. 2015–July. IEEE, 2015. <a href="https://doi.org/10.1109/LICS.2015.34">https://doi.org/10.1109/LICS.2015.34</a>.
  ieee: K. Chatterjee, M. Henzinger, and V. Loitzenbauer, “Improved algorithms for
    one-pair and k-pair Streett objectives,” in <i>Proceedings - Symposium on Logic
    in Computer Science</i>, Kyoto, Japan, 2015, vol. 2015–July.
  ista: '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.'
  mla: Chatterjee, Krishnendu, et al. “Improved Algorithms for One-Pair and k-Pair
    Streett Objectives.” <i>Proceedings - Symposium on Logic in Computer Science</i>,
    vol. 2015–July, 7174888, IEEE, 2015, doi:<a href="https://doi.org/10.1109/LICS.2015.34">10.1109/LICS.2015.34</a>.
  short: K. Chatterjee, M. Henzinger, V. Loitzenbauer, in:, Proceedings - Symposium
    on Logic in Computer Science, IEEE, 2015.
conference:
  end_date: 2015-07-10
  location: Kyoto, Japan
  name: 'LICS: Logic in Computer Science'
  start_date: 2015-07-06
date_created: 2018-12-11T11:53:19Z
date_published: 2015-07-01T00:00:00Z
date_updated: 2025-09-23T09:20:53Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/LICS.2015.34
ec_funded: 1
external_id:
  isi:
  - '000380427100026'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprints.cs.univie.ac.at/4368/
month: '07'
oa: 1
oa_version: Submitted Version
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
publication: Proceedings - Symposium on Logic in Computer Science
publication_status: published
publisher: IEEE
publist_id: '5489'
quality_controlled: '1'
related_material:
  record:
  - id: '464'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Improved algorithms for one-pair and k-pair Streett objectives
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 2015-July
year: '2015'
...