Minimizing local automata

Abstract : We design an algorithm that minimizes irreducible deterministic local automata by a sequence of state mergings. Two states can be merged if they have exactly the same outputs. The running time of the algorithm is O(min(m(n − r + 1), m log n)), where m is the number of edges, n the number of states of the automaton, and r the number of states of the minimized automaton. In particular, the algorithm is linear when the automaton is already minimal and contrary to Hopcroft's minimisation algorithm that has a O(kn log n) running time in this case, where k is the size of the alphabet, and that applies only to complete automata. (Note that kn ≥ m.) While Hopcroft's algorithm relies on a "negative strategy", starting from a partition with a single class of all states, and partitioning classes when it is discovered that two states cannot belong to the sam class, our algorithm relies on a "positive strategy", starting from the trivial partition for which each class is a singleton. Two classes are then merged when their leaders have the same outputs. The algorithm applies to irreducible deterministic local automata, where all states are considered both initial and final. These automata, also called covers, recognize symbolic dynamical shifts of finite type. They serve to present a large class of constrained channels, the class of finite memory systems, used for channel coding purposes. The algorithm also applies to irreducible deterministic automata that are left-closing and have a synchronizing word. These automata present shifts that are called almost of finite type. Almost-of-finite-type shifts make a meaningful class of shifts, intermediate between finite type shifts and sofic shifts.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620130
Contributor : Marie-Pierre Béal <>
Submitted on : Monday, October 3, 2011 - 3:19:30 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:02 PM
Long-term archiving on : Wednesday, January 4, 2012 - 2:26:32 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620130, version 1

Collections

Citation

Marie-Pierre Béal, Maxime Crochemore. Minimizing local automata. IEEE International Symposium on Information Theory (ISIT'07), 2007, France. pp.1376-1380. ⟨hal-00620130⟩

Share

Metrics

Record views

259

Files downloads

213