文章基本信息

标题：Improved Algorithms for Parity and Streett objectives
本地全文：下载
作者：Loitzenbauer, Veronika ; Henzinger, Monika ; Chatterjee, Krishnendu 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2017
卷号：13
期号：3
语种：English
出版社：Technical University of Braunschweig
摘要：The computation of the winning set for parity objectives and for Streettobjectives in graphs as well as in game graphs are central problems incomputer-aided verification, with application to the verification of closedsystems with strong fairness conditions, the verification of open systems,checking interface compatibility, well-formedness of specifications, and thesynthesis 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 intime $O(n^{5/2})$ and for (2) k-pair Streett objectives in graphs in time$O(n^2 + nk \log n)$. For both problems this gives faster algorithms for densegraphs and represents the first improvement in asymptotic running time in 15years.
关键词：F.3.1;F.2.2;Computer Science - Logic in Computer Science;Computer Science - Data Structures and Algorithms