Unambiguous automata inference by means of state-merging methods. (English) Zbl 1257.68087

Lavrač, Nada (ed.) et al., Machine learning: ECML 2003. 14th European conference on machine learning, Cavtat-Dubrovnik, Croatia, September 22–26, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20121-1/pbk). Lecture Notes in Computer Science 2837, 60-71 (2003).
Summary: We consider inference of automata from given data. A classical problem is to find the smallest compatible automaton, i.e. the smallest automaton accepting all examples and rejecting all counter-examples. We study unambiguous automata (UFA) inference, an intermediate framework between the hard nondeterministic automata (NFA) inference and the well known deterministic automata (DFA) inference. The search space for UFA inference is described and original theoretical results on both the DFA and the UFA inference search space are given. An algorithm for UFA inference is proposed and experimental results on a benchmark with both deterministic and nondeterministic targets are provided showing that UFA inference outperforms DFA inference.
For the entire collection see [Zbl 1024.00057].


68Q32 Computational learning theory
68Q45 Formal languages and automata


Full Text: DOI