Skip to Main content Skip to Navigation
Conference papers

Minimizing incomplete automata

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00620274
Contributor : Marie-Pierre Béal <>
Submitted on : Monday, October 3, 2011 - 2:07:37 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Wednesday, January 4, 2012 - 2:26:55 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620274, version 1

Citation

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⟩

Share

Metrics

Record views

250

Files downloads

197