2016/10/24 by Yong Li, Yu‐Fang Chen, Li, Yong +5 · 1 citation
Computer Science · #Machine Learning and Algorithms #semigroups and automata theory #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.1610.07380
In this paper, we propose a novel algorithm to learn a Büchi automaton from a teacher who knows an ω-regular language. The algorithm is based on learning a formalism named family of DFAs (FDFAs) recently proposed by Angluin and Fisman[10]. The main catch is that we use a classification tree structure instead of the standard observation table structure. The worst case storage space required by our algorithm is quadratically better than the table-based algorithm proposed in [10]. We implement the first publicly available library ROLL (Regular Omega Language Learning ), which consists of all ω-regular learning algorithms available in the literature and the new algorithms proposed in this paper. Experimental results show that our tree-based algorithms have the best performance among others regarding the number of solved learning tasks.