What is the Search Space for the Inference of Non Deterministic, Unambiguous and Deterministic Automata ?

François Coste 1 Daniel Fredouille 1
1 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : A classical problem in inferring automata from data is to find the smallest compatible automaton, i.e. the smallest automaton accepting all examples and rejecting all counter-examples. We are interested in Non-deterministic Finite Automata (NFA) inference which is better suited to Occam's razor optimization principle than Deterministic Finite Automata (DFA). We revisit the existing results on the search space in the state-merging framework, focusing on nondeterminism. We introduce unambiguous automata (UFA) inference, an intermediate between the difficult NFA inference framework and the weaker DFA inference framework. The UFA search space, though containing nondeterministic automata, shares many properties with the DFA search space. Our conclusion is that the search spaces of UFA and DFA are lattices when using adequate operators.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00071673
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:29:33 PM
Last modification on : Friday, November 16, 2018 - 1:22:22 AM
Long-term archiving on : Sunday, April 4, 2010 - 10:32:35 PM

Identifiers

  • HAL Id : inria-00071673, version 1

Citation

François Coste, Daniel Fredouille. What is the Search Space for the Inference of Non Deterministic, Unambiguous and Deterministic Automata ?. [Research Report] RR-4907, INRIA. 2003. ⟨inria-00071673⟩

Share

Metrics

Record views

258

Files downloads

116