4
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ The automaton is deterministic. Right? $\endgroup$
    – user6976
    Apr 3, 2012 at 18:26
  • $\begingroup$ >The automaton is deterministic. Right? right $\endgroup$ Apr 3, 2012 at 18:26
  • $\begingroup$ There are some other assumptions missing otherwise the answer is obviously "no", see my answer. $\endgroup$
    – user6976
    Apr 3, 2012 at 18:43
  • $\begingroup$ 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. $\endgroup$ Apr 3, 2012 at 18:55
  • $\begingroup$ 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$. $\endgroup$
    – user6976
    Apr 3, 2012 at 19:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.