ML Anthology

Inference of Finite Automata: Reducing the Search Space with an Ordering of Pairs of States

François Coste, Jacques Nicolas
ECML-PKDD 1998 pp. 37-42
doi:10.1007/BFB0026669 /ecmlpkdd/1998/coste1998ecml-inference/

Abstract

We investigate the set of all minimal deterministic finite automata accepting a given set of words and rejecting another given set of words. We present several criteria to order the exploration of the corresponding search space. Three criteria are shown to have a very good behavior with respect to the pruning they imply in the search space. Best results have been obtained for the prefix ordering. We have also worked on a new dynamic ordering based on an entropy computation.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Coste and Nicolas. "Inference of Finite Automata: Reducing the Search Space with an Ordering of Pairs of States." European Conference on Machine Learning, 1998. doi:10.1007/BFB0026669

Markdown

[Coste and Nicolas. "Inference of Finite Automata: Reducing the Search Space with an Ordering of Pairs of States." European Conference on Machine Learning, 1998.](https://mlanthology.org/ecmlpkdd/1998/coste1998ecml-inference/) doi:10.1007/BFB0026669

BibTeX

@inproceedings{coste1998ecml-inference,
  title     = {{Inference of Finite Automata: Reducing the Search Space with an Ordering of Pairs of States}},
  author    = {Coste, François and Nicolas, Jacques},
  booktitle = {European Conference on Machine Learning},
  year      = {1998},
  pages     = {37-42},
  doi       = {10.1007/BFB0026669},
  url       = {https://mlanthology.org/ecmlpkdd/1998/coste1998ecml-inference/}
}