https://scholars.lib.ntu.edu.tw/handle/123456789/362773
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Tsai, M.-H. | en_US |
dc.contributor.author | Fogarty, S. | en_US |
dc.contributor.author | Vardi, M.Y. | en_US |
dc.contributor.author | YIH-KUEN TSAY | en_US |
dc.creator | Tsai, M.-H.;Fogarty, S.;Vardi, M.Y.;Tsay, Y.-K. | - |
dc.date.accessioned | 2018-09-10T08:35:31Z | - |
dc.date.available | 2018-09-10T08:35:31Z | - |
dc.date.issued | 2011 | - |
dc.identifier.issn | 03029743 | - |
dc.identifier.uri | http://www.scopus.com/inward/record.url?eid=2-s2.0-79951668694&partnerID=MN8TOARS | - |
dc.identifier.uri | http://scholars.lib.ntu.edu.tw/handle/123456789/362773 | - |
dc.identifier.uri | 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 | - |
dc.description.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. | - |
dc.language | en | en |
dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | - |
dc.source | AH | - |
dc.subject.other | Comparative experiments; Complementation; Complementation constructions; Complexity analysis; Determinization; Optimization heuristics; Automata theory; Experiments | - |
dc.title | State of Büchi complementation | - |
dc.type | conference paper | en |
dc.identifier.doi | 10.1007/978-3-642-18098-9_28 | - |
dc.identifier.scopus | 2-s2.0-79951668694 | - |
dc.relation.pages | 261-271 | - |
dc.relation.journalvolume | 6482 LNCS | - |
item.cerifentitytype | Publications | - |
item.openairetype | conference paper | - |
item.fulltext | no fulltext | - |
item.grantfulltext | none | - |
item.openairecristype | http://purl.org/coar/resource_type/c_5794 | - |
crisitem.author.dept | Information Management | - |
crisitem.author.orcid | 0000-0002-5960-1615 | - |
crisitem.author.parentorg | College of Management | - |
顯示於: | 資訊管理學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。