Learning regular omega languages

详细信息    查看全文

• 作者：Dana Angluin^a ; ¹ ; Dana Fisman^b ; ² ; ^{dana.fisman@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Active learning ; Language inference ; Infinitary languages ; Membership queries ; Equivalence queries ; L⁎L⁎ ; Bü ; chi automata
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：18 October 2016
• 年：2016
• 卷：650
• 期：Complete
• 页码：57-72
• 全文大小：885 K

文摘

We provide an algorithm for learning an unknown regular set of infinite words using membership and equivalence queries. Three variations of the algorithm learn three different canonical representations of regular omega languages using the notion of families of dfas. One is of size similar to L_$$L_{\mathrm{\$}}$, a dfa representation recently learned using L^⁎$L^{⁎}$ by Farzan et al. The second is based on the syntactic forc, introduced by Maler and Staiger. The third is introduced herein. We show that the second and third can be exponentially smaller than the first, and the third is at most as large as the second, with up to a quadratic saving with respect to the second.