https://scholars.lib.ntu.edu.tw/handle/123456789/338340
標題: | Extending automated compositional verification to the full class of omega-regular languages | 作者: | Farzan, A. Chen, Y.-F. Clarke, E.M. Tsay, Y.-K. Wang, B.-Y. YIH-KUEN TSAY |
公開日期: | 2008 | 卷: | 4963 LNCS | 起(迄)頁: | 2-17 | 來源出版物: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 摘要: | Recent studies have suggested the applicability of learning to automated compositional verification. However, current learning algorithms fall short when it comes to learning liveness properties. We extend the automaton synthesis paradigm for the infinitary languages by presenting an algorithm to learn an arbitrary regular set of infinite sequences (an ω-regular language) over an alphabet ∑. Our main result is an algorithm to learn a nondeterministic Büchi automaton that recognizes an unknown ω-regular language. This is done by learning a unique projection of it on ∑ * using the framework suggested by Angluin for learning regular subsets of ∑ *. © 2008 Springer-Verlag Berlin Heidelberg. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-47249127285&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/338340 https://www.scopus.com/inward/record.uri?eid=2-s2.0-47249127285&doi=10.1007%2f978-3-540-78800-3_2&partnerID=40&md5=f39ba65c9bca727b7725a44a3c0eb13a |
ISSN: | 03029743 | DOI: | 10.1007/978-3-540-78800-3_2 | SDG/關鍵字: | Compositional verification; European; Heidelberg (CO); Infinite sequences; International conferences; Languages (traditional); Liveness properties; Regular language; Algorithms; Boolean functions; Context free languages; Education; Formal languages; Learning systems; Linguistics; Query languages; Real time systems; Translation (languages); Learning algorithms |
顯示於: | 資訊管理學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。