Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Modifying the Upper Bound on the Length of Minimal Synchronizing Word
verfasst von : A. N. Trahtman
Erschienen in: Fundamentals of Computation Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A word
w
is called synchronizing (recurrent, reset, magic, directable) word of deterministic finite automaton (DFA) if
w
sends all states of the automaton to a unique state. In 1964 Jan Černy found a sequence of
n
-state complete DFA possessing a minimal synchronizing word of length (
n
− 1)
2
. He conjectured that it is an upper bound on the length of such words for complete DFA. Nevertheless, the best upper bound (
n
3
−
n
)/6 was found almost 30 years ago.
We reduce the upper bound on the length of the minimal synchronizing word to
n
(7
n
2
+ 6
n
− 16)/48.
An implemented algorithm for finding synchronizing word with restricted upper bound is described. The work presents the distribution of all synchronizing automata of small size according to the length of an almost minimal synchronizing word.