---
_id: '464'
abstract:
- lang: eng
  text: 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.
article_number: '26'
article_processing_charge: No
arxiv: 1
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 MH, Loitzenbauer V. Improved algorithms for parity
    and Streett objectives. <i>Logical Methods in Computer Science</i>. 2017;13(3).
    doi:<a href="https://doi.org/10.23638/LMCS-13(3:26)2017">10.23638/LMCS-13(3:26)2017</a>
  apa: Chatterjee, K., Henzinger, M. H., &#38; Loitzenbauer, V. (2017). Improved algorithms
    for parity and Streett objectives. <i>Logical Methods in Computer Science</i>.
    International Federation of Computational Logic. <a href="https://doi.org/10.23638/LMCS-13(3:26)2017">https://doi.org/10.23638/LMCS-13(3:26)2017</a>
  chicago: Chatterjee, Krishnendu, Monika H Henzinger, and Veronika Loitzenbauer.
    “Improved Algorithms for Parity and Streett Objectives.” <i>Logical Methods in
    Computer Science</i>. International Federation of Computational Logic, 2017. <a
    href="https://doi.org/10.23638/LMCS-13(3:26)2017">https://doi.org/10.23638/LMCS-13(3:26)2017</a>.
  ieee: K. Chatterjee, M. H. Henzinger, and V. Loitzenbauer, “Improved algorithms
    for parity and Streett objectives,” <i>Logical Methods in Computer Science</i>,
    vol. 13, no. 3. International Federation of Computational Logic, 2017.
  ista: Chatterjee K, Henzinger MH, Loitzenbauer V. 2017. Improved algorithms for
    parity and Streett objectives. Logical Methods in Computer Science. 13(3), 26.
  mla: Chatterjee, Krishnendu, et al. “Improved Algorithms for Parity and Streett
    Objectives.” <i>Logical Methods in Computer Science</i>, vol. 13, no. 3, 26, International
    Federation of Computational Logic, 2017, doi:<a href="https://doi.org/10.23638/LMCS-13(3:26)2017">10.23638/LMCS-13(3:26)2017</a>.
  short: K. Chatterjee, M.H. Henzinger, V. Loitzenbauer, Logical Methods in Computer
    Science 13 (2017).
date_created: 2018-12-11T11:46:37Z
date_published: 2017-09-26T00:00:00Z
date_updated: 2025-06-02T08:53:41Z
day: '26'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.23638/LMCS-13(3:26)2017
ec_funded: 1
external_id:
  arxiv:
  - '1410.0833'
file:
- access_level: open_access
  checksum: 12d469ae69b80361333d7dead965cf5d
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:13:27Z
  date_updated: 2020-07-14T12:46:32Z
  file_id: '5010'
  file_name: IST-2018-956-v1+1_2017_Chatterjee_Improved_algorithms.pdf
  file_size: 582940
  relation: main_file
file_date_updated: 2020-07-14T12:46:32Z
has_accepted_license: '1'
intvolume: '        13'
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '09'
oa: 1
oa_version: Published 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: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
publication: Logical Methods in Computer Science
publication_identifier:
  issn:
  - 1860-5974
publication_status: published
publisher: International Federation of Computational Logic
publist_id: '7357'
pubrep_id: '956'
quality_controlled: '1'
related_material:
  record:
  - id: '1661'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Improved algorithms for parity and Streett objectives
tmp:
  image: /image/cc_by_nd.png
  legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
  name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
  short: CC BY-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2017'
...