MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A$ be a complete strongly connected automaton with $n$ states. Does always exist a word $v$ of length at most $n-1$ such that its underlying graph is connected? That is for any pair of distinct states $p,q$ exists a positive integer $k$ such that either $p.v^k = q$ or $q.v^k = p$. Additionaly we can assume that there exists a word $w$ such that its underlying graph is connected.

The statement also can be reformulated in terms of linear algebra.

share|cite|improve this question
The automaton is deterministic. Right? – Mark Sapir Apr 3 '12 at 18:26
>The automaton is deterministic. Right? right – Misha Berlinkov Apr 3 '12 at 18:26
There are some other assumptions missing otherwise the answer is obviously "no", see my answer. – Mark Sapir Apr 3 '12 at 18:43
The assumption is "Additionaly we can assume that there exists a word w such that its underlying graph is connected." and we can also assume that $w$ takes $A$ into one state, but I think it is not necessary. – Misha Berlinkov Apr 3 '12 at 18:55
Assumption that $|Aw|=1$ implies that the GCD of the lengths of cyclies in $A$ is 1 (see Trakhtman's theorem). Perhaps you should reformulate the question putting the necessary assumptions before the question itself. The question should say something like: If there exists $w$ for which $(A,w)$ is connected, then there exists such a $w$ of length at most $n-1$. – Mark Sapir Apr 3 '12 at 19:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.