https://scholars.lib.ntu.edu.tw/handle/123456789/362773
標題: | State of Büchi complementation | 作者: | Tsai, M.-H. Fogarty, S. Vardi, M.Y. Tsay, Y.-K. YIH-KUEN TSAY |
公開日期: | 2011 | 卷: | 6482 LNCS | 起(迄)頁: | 261-271 | 來源出版物: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 摘要: | 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/關鍵字: | Comparative experiments; Complementation; Complementation constructions; Complexity analysis; Determinization; Optimization heuristics; Automata theory; Experiments |
顯示於: | 資訊管理學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。