https://scholars.lib.ntu.edu.tw/handle/123456789/362773
Title: | State of Büchi complementation | Authors: | Tsai, M.-H. Fogarty, S. Vardi, M.Y. YIH-KUEN TSAY |
Issue Date: | 2011 | Journal Volume: | 6482 LNCS | Start page/Pages: | 261-271 | Source: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Abstract: | Büchi complementation has been studied for five decades since the formalism was introduced in 1960. Known complementation constructions can be classified into Ramsey-based, determinization-based, rank-based, and slice-based approaches. For the performance of these approaches, there have been several complexity analyses but very few experimental results. What especially lacks is a comparative experiment on all the four approaches to see how they perform in practice. In this paper, we review the state of Büchi complementation, propose several optimization heuristics, and perform comparative experimentation on the four approaches. The experimental results show that the determinization-based Safra-Piterman construction outperforms the other three and our heuristics substantially improve the Safra-Piterman construction and the slice-based construction. © 2011 Springer-Verlag Berlin Heidelberg. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-79951668694&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/362773 https://www.scopus.com/inward/record.uri?eid=2-s2.0-79951668694&doi=10.1007%2f978-3-642-18098-9_28&partnerID=40&md5=0104c1ab0426594b0ea8c620c5c14120 |
ISSN: | 03029743 | DOI: | 10.1007/978-3-642-18098-9_28 | SDG/Keyword: | Comparative experiments; Complementation; Complementation constructions; Complexity analysis; Determinization; Optimization heuristics; Automata theory; Experiments |
Appears in Collections: | 資訊管理學系 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.