Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
show 9 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.