1. A novel learning algorithm for Büchi automata based on family of DFAs and classification trees.
- Author
-
Li, Yong, Chen, Yu-Fang, Zhang, Lijun, and Liu, Depeng
- Subjects
- *
MACHINE learning , *ALGORITHMS , *ROBOTS , *CLASSIFICATION , *FOREIGN language education - Abstract
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 family of DFAs (FDFAs) recently proposed by Angluin and Fisman. 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 that required by the table-based algorithm proposed by Angluin and Fisman. We implement the proposed learning algorithms in the learning library ROLL (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. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF