Unambiguous Automata Inference by Means of State-Merging Methods
Abstract
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.
Cite
Text
Coste and Fredouille. "Unambiguous Automata Inference by Means of State-Merging Methods." European Conference on Machine Learning, 2003. doi:10.1007/978-3-540-39857-8_8Markdown
[Coste and Fredouille. "Unambiguous Automata Inference by Means of State-Merging Methods." European Conference on Machine Learning, 2003.](https://mlanthology.org/ecmlpkdd/2003/coste2003ecml-unambiguous/) doi:10.1007/978-3-540-39857-8_8BibTeX
@inproceedings{coste2003ecml-unambiguous,
title = {{Unambiguous Automata Inference by Means of State-Merging Methods}},
author = {Coste, François and Fredouille, Daniel},
booktitle = {European Conference on Machine Learning},
year = {2003},
pages = {60-71},
doi = {10.1007/978-3-540-39857-8_8},
url = {https://mlanthology.org/ecmlpkdd/2003/coste2003ecml-unambiguous/}
}