A Novel Learning Algorithm for Büchi Automata based on Family of DFAs and Classification Trees

Abstract

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.

Accepted by TACAS 2017