Synchronizing Automata on Quasi Eulerian Digraph

Details Synchronizing Automata on Quasi Eulerian Digraph Synchronizing Automata on Quasi Eulerian Digraph

2012-03-15

arxiv.org/abs/1203.3402v1

Computer Science

Formal Languages and Automata Theory

8 pages, 1 figure

Scientific paper

In 1964 \v{C}ern\'{y} conjectured that each $n$-state synchronizing automaton posesses a reset word of length at most $(n-1)^2$. From the other side the best known upper bound on the reset length (minimum length of reset words) is cubic in $n$. Thus the main problem here is to prove quadratic (in $n$) upper bounds. Since 1964, this problem has been solved for few special classes of \sa. One of this result is due to Kari \cite{Ka03} for automata with Eulerian digraphs. In this paper we introduce a new approach to prove quadratic upper bounds and explain it in terms of Markov chains and Perron-Frobenius theories. Using this approach we obtain a quadratic upper bound for a generalization of Eulerian automata.

Affiliated with

Also associated with

No associations

Rating

Synchronizing Automata on Quasi Eulerian Digraph 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 Synchronizing Automata on Quasi Eulerian Digraph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Synchronizing Automata on Quasi Eulerian Digraph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-31359