Efficient Algorithms for the Inference of Minimum Size DFAs
Abstract
This work describes algorithms for the inference of minimum size deterministic automata consistent with a labeled training set. The algorithms presented represent the state of the art for this problem, known to be computationally very hard. In particular, we analyze the performance of algorithms that use implicit enumeration of solutions and algorithms that perform explicit search but incorporate a set of techniques known as dependency directed backtracking to prune the search tree effectively. We present empirical results that show the comparative efficiency of the methods studied and discuss alternative approaches to this problem, evaluating their advantages and drawbacks.
Cite
Text
Oliveira and Silva. "Efficient Algorithms for the Inference of Minimum Size DFAs." Machine Learning, 2001. doi:10.1023/A:1010828029885Markdown
[Oliveira and Silva. "Efficient Algorithms for the Inference of Minimum Size DFAs." Machine Learning, 2001.](https://mlanthology.org/mlj/2001/oliveira2001mlj-efficient/) doi:10.1023/A:1010828029885BibTeX
@article{oliveira2001mlj-efficient,
title = {{Efficient Algorithms for the Inference of Minimum Size DFAs}},
author = {Oliveira, Arlindo L. and Silva, João P. Marques},
journal = {Machine Learning},
year = {2001},
pages = {93-119},
doi = {10.1023/A:1010828029885},
volume = {44},
url = {https://mlanthology.org/mlj/2001/oliveira2001mlj-efficient/}
}