Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Experimental Study of the Shortest Reset Word of Random Automata
verfasst von : Evgeny Skvortsov, Evgeny Tipikin
Erschienen in: Implementation and Application of Automata
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
In this paper we describe an approach to finding the shortest reset word of a finite synchronizing automaton by using a SAT solver. We use this approach to perform an experimental study of the length of the shortest reset word of a finite synchronizing automaton. The largest automata we considered had 100 states. The results of the experiments allow us to formulate a hypothesis that the length of the shortest reset word of a random finite automaton with
n
states and 2 input letters with high probability is sublinear with respect to
n
and can be estimated as 1.95
n
0.55
.