# Proof of conjecture that permutation-free automata restrict the possible states visitable from a stringset sharing prefixes and infixes

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.

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.

• 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. – Benjamin Steinberg Nov 29 '13 at 3:03
• It seems $R=\{q_0\}$ and $k=1$ yields easy counter-examples. – Denis Feb 18 '14 at 11:06