Experimental Study of the Shortest Reset Word of Random Automata

Abstract

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.95n^{0.55}.$

References in corpus (1)

• Phase transition for Local Search on planted SAT

Cited by in corpus (4)

• Checking Whether an Automaton Is Monotonic Is NP-complete
• A New Heuristic Synchronizing Algorithm
• Using Sat solvers for synchronization issues in non-deterministic automata
• The Černý conjecture for small automata: experimental report