Experimental Study of the Shortest Reset Word of Random Automata

Details Experimental Study of the Shortest Reset Word of Random Automata Experimental Study of the Shortest Reset Word of Random Automata

2011-04-26

arxiv.org/abs/1105.1704v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

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}.$

Affiliated with

Also associated with

No associations

Rating

Experimental Study of the Shortest Reset Word of Random Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Experimental Study of the Shortest Reset Word of Random Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Experimental Study of the Shortest Reset Word of Random Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-297194