A novel learning algorithm for Büchi automata based on family of DFAs and classification trees

In this paper, we propose a novel algorithm to learn a Büchi automaton from a teacher who knows an -regular language. The learned Büchi automaton can be a nondeterministic Büchi automaton or a limit deterministic Büchi automaton. The learning algorithm is based on learning a formalism called (FDFAs) recently proposed by Angluin and Fisman. The main catch is that we use a structure instead of the standard structure. The worst case storage space required by our algorithm is quadratically better than that required by the table-based algorithm proposed by Angluin and Fisman. We implement the proposed learning algorithms in the learning library (Regular Omega Language Learning), which also consists of other complete -regular learning algorithms available in the literature. Experimental results show that our tree-based learning algorithms have the best performance among others regarding the number of solved learning tasks.