Inference of finite automata: reducing the search space with an ordering of pairs of states


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.

in Machine Learning: ECML-98, Claire Nédellec and Céline Rouveirol (Eds.), Springer-Verlag vol.1398 in the Lecture Notes in Artificial Intelligence, April 1998.