Minimizing local automata - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

Minimizing local automata

Résumé

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.
Fichier principal
Vignette du fichier
hal.pdf (99.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00620130 , version 1 (03-10-2011)

Identifiants

  • HAL Id : hal-00620130 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More