Displaying similar documents to “Asynchronous sliding block maps”

Computing the prefix of an automaton

Marie-Pierre Béal, Olivier Carton (2000)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Hyper-minimizing minimized deterministic finite state automata

Andrew Badr, Viliam Geffert, Ian Shipman (2009)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We present the first (polynomial-time) algorithm for reducing a given deterministic finite state automaton (DFA) into a hyper-minimized DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications,...

Two-way automaton computations

Jean-Camille Birget (1990)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity: