Fast algorithm finding the shortest reset words

Details Fast algorithm finding the shortest reset words Fast algorithm finding the shortest reset words

2012-03-13

arxiv.org/abs/1203.2822v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

In this paper we present a new fast algorithm finding minimal reset words for finite synchronizing automata. The problem is know to be computationally hard, and our algorithm is exponential. Yet, it is faster than the algorithms used so far and it works well in practice. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare resulted subsets. We give both theoretical and practical arguments showing that the branching factor is reduced efficiently. As a practical test we perform an experimental study of the length of the shortest reset word for random automata with $n$ states and 2 input letters. We follow Skvorsov and Tipikin, who have performed such a study using a SAT solver and considering automata up to $n=100$ states. With our algorithm we are able to consider much larger sample of automata with up to $n=300$ states. In particular, we obtain a new more precise estimation of the expected length of the shortest reset word $\approx 2.5\sqrt{n-5}$.

Affiliated with

Also associated with

No associations

Rating

Fast algorithm finding the shortest reset words 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 Fast algorithm finding the shortest reset words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast algorithm finding the shortest reset words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-144363