An automaton $\mathcal A = (X, Q, \delta, q_0)$ is called permutation-free iff no word $w \in X^*$ induces a nontrivial permutation of a subset of the states of $\mathcal A$. More formally for any $R \subseteq Q$ and any $w \in X^*$, $\delta(R, w) = R$ implies $\delta(r, w) = r$ for all $r \in R$.

Let $\mathcal A = (X, Q, \delta, q_0)$ be a complete permutation-free automata. Let $\xi \in X^{\mathbb N}$ an infinite word, and let $R \subseteq Q$ be the set of words visited by $\xi$ in $\mathcal A$. Also let $k$ be such that the first $k$ symbols considered as a finite word visit all states from $\mathcal R$ and choose $k$ so that it is minimal. Also let $\eta \in X^*$ be a second infinite word with the property that the first $k$ symbols of $\eta$ and $\xi$ coincide (so that $\eta$ visits at least the states from $\mathcal R$) and that all infixes up to a length of $k$ are the same. I conjecture that $\eta$ visits exactly the states from $\mathcal R$, i.e. there is no state outside of $\mathcal R$ visited by $\eta$. Any ideas how to proof that?

(btw I specify no final states because they are not relevant to the problem at hand). To clarify the definition of permutation-free automata, I append a picture.

enter image description here

Furthermore, if $\mathcal A$ is not permutation-free than there exists a word $w$ and $n > 1$ states $\{ s_1, s_2, \ldots, s_n \}$ with $\delta(s_1, w) = s_2, \delta(s_2, w) = s_3, \ldots, \delta(s_n, w) = s_1$. Meaning $\delta(s_1, w^n) = s_1$, so in an permutation-free automaton $\delta(q, w^n) = q$ always implies $\delta(q, w) = q$, meaing that if $w^n$ has a loop, then already $w$ has a loop.

  • $\begingroup$ You are talking about counter-free or aperiodic automata. These can keep track of much more info than prefixes and infixes of fixed sizes so most likely your conjecture is false. $\endgroup$ – Benjamin Steinberg Nov 29 '13 at 3:03
  • $\begingroup$ It seems $R=\{q_0\}$ and $k=1$ yields easy counter-examples. $\endgroup$ – Denis Feb 18 '14 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.