---
_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
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. Logical Methods in Computer Science. 2017;13(3).
doi:10.23638/LMCS-13(3:26)2017
apa: Chatterjee, K., Henzinger, M. H., & Loitzenbauer, V. (2017). Improved algorithms
for parity and Streett objectives. Logical Methods in Computer Science.
International Federation of Computational Logic. https://doi.org/10.23638/LMCS-13(3:26)2017
chicago: Chatterjee, Krishnendu, Monika H Henzinger, and Veronika Loitzenbauer.
“Improved Algorithms for Parity and Streett Objectives.” Logical Methods in
Computer Science. International Federation of Computational Logic, 2017. https://doi.org/10.23638/LMCS-13(3:26)2017.
ieee: K. Chatterjee, M. H. Henzinger, and V. Loitzenbauer, “Improved algorithms
for parity and Streett objectives,” Logical Methods in Computer Science,
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.” Logical Methods in Computer Science, vol. 13, no. 3, 26, International
Federation of Computational Logic, 2017, doi:10.23638/LMCS-13(3:26)2017.
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: 2023-02-23T10:08:55Z
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'
...