[{"file_date_updated":"2020-07-14T12:46:32Z","volume":13,"tmp":{"name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","image":"/image/cc_by_nd.png","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","short":"CC BY-ND (4.0)"},"pubrep_id":"956","publication_status":"published","license":"https://creativecommons.org/licenses/by-nd/4.0/","oa":1,"article_number":"26","file":[{"date_created":"2018-12-12T10:13:27Z","content_type":"application/pdf","file_id":"5010","relation":"main_file","checksum":"12d469ae69b80361333d7dead965cf5d","date_updated":"2020-07-14T12:46:32Z","access_level":"open_access","file_name":"IST-2018-956-v1+1_2017_Chatterjee_Improved_algorithms.pdf","file_size":582940,"creator":"system"}],"_id":"464","date_published":"2017-09-26T00:00:00Z","abstract":[{"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.","lang":"eng"}],"arxiv":1,"issue":"3","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-06-02T08:53:41Z","scopus_import":"1","external_id":{"arxiv":["1410.0833"]},"publication_identifier":{"issn":["1860-5974"]},"publist_id":"7357","oa_version":"Published Version","has_accepted_license":"1","year":"2017","department":[{"_id":"KrCh"}],"quality_controlled":"1","publication":"Logical Methods in Computer Science","intvolume":"        13","status":"public","publisher":"International Federation of Computational Logic","month":"09","date_created":"2018-12-11T11:46:37Z","language":[{"iso":"eng"}],"doi":"10.23638/LMCS-13(3:26)2017","ddc":["004"],"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"}],"related_material":{"record":[{"relation":"earlier_version","id":"1661","status":"public"}]},"day":"26","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"first_name":"Veronika","full_name":"Loitzenbauer, Veronika","last_name":"Loitzenbauer"}],"type":"journal_article","ec_funded":1,"citation":{"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>.","ista":"Chatterjee K, Henzinger MH, Loitzenbauer V. 2017. Improved algorithms for parity and Streett objectives. Logical Methods in Computer Science. 13(3), 26.","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.","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).","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>"},"title":"Improved algorithms for parity and Streett objectives"}]