Limits of Exact Algorithms for Inference of Minimum Size Finite State Machines
Abstract
We address the problem of selecting the minimum sized finite state machine consistent with given input/output samples. The problem can be solved by computing the minimum finite state machine equivalent to a finite state machine without loops obtained from the training set. We compare the performance of four algorithms for this task: two algorithms for incompletely specified finite state machine reduction, an algorithm based on a well known explicit search procedure and an algorithm based on a new implicit search procedure that is introduced in this paper.
Cite
Text
Oliveira and Edwards. "Limits of Exact Algorithms for Inference of Minimum Size Finite State Machines." International Conference on Algorithmic Learning Theory, 1996. doi:10.1007/3-540-61863-5_34Markdown
[Oliveira and Edwards. "Limits of Exact Algorithms for Inference of Minimum Size Finite State Machines." International Conference on Algorithmic Learning Theory, 1996.](https://mlanthology.org/alt/1996/oliveira1996alt-limits/) doi:10.1007/3-540-61863-5_34BibTeX
@inproceedings{oliveira1996alt-limits,
title = {{Limits of Exact Algorithms for Inference of Minimum Size Finite State Machines}},
author = {Oliveira, Arlindo L. and Edwards, Stephen},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1996},
pages = {59-66},
doi = {10.1007/3-540-61863-5_34},
url = {https://mlanthology.org/alt/1996/oliveira1996alt-limits/}
}