Minimizing incomplete automata

Marie-Pierre Béal (1) , Maxime Crochemore (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We develop a O(m log n)-time and O(k + n + m)-space algorithm for minimizing incomplete deterministic automata, where n is the number of states, m the number of edges, and k the size of the alphabet. Minimization reduces to the partial Functional coarsest partition problem. Our algorithm is a slight variant of Hopcroft's algorithm for minimizing deterministic complete automata.

Domaines: Algorithme et structure de données [cs.DS]

Marie-Pierre Béal, Maxime Crochemore. Minimizing incomplete automata. Finite-State Methods and Natural Language Processing (FSMNLP'08), 2008, United States. pp.9-16. ⟨hal-00620274⟩