Active Learning Infinite-Word Automata

Regular languages can be actively learned with membership and equivalence queries in polynomial time. The learning algorithm, called the L^* algorithm, constructs iteratively the right congruence relation of a given regular language L, and returns the minimal DFA recognizing L. The L^* algorithm has been adapted to various types of automata: tree automata, weighted automata, nominal automata. However, an extension to infinite-word automata has been elusive. I will discuss why extending L^* to infinite-word automata is difficlut. Next, I will present an alternative approach, in which we learn the automaton rather than its language. That is, we consider a hidden target automaton T and the learning algorithm asks queries about the language of T and its structure. The learning algorithm returns an automaton equivalent to T and structurally similar to T. We consider T to be either a Deterministic Buechi Automaton or a LimAvg-automaton.

Authors

• Jan Otop

Keywords

No keywords are indexed for this paper.