4
$\begingroup$

Let $X$ be a subshift on a finite alphabet. I'm interested in the following property: there exist words $s,t\in\mathcal L(X)$ (the language of $X$) such that $\{s,t\}^*\subset \mathcal L(X)$. That is, $s^{k_1}t^{m_1}\dots s^{k_n}t^{m_n}\in \mathcal L(X)$ for all $n\ge1$ and all non-negative $k_j$ and $m_j$.

Question. What natural property of $X$ will guarantee the existence of such a free semigroup? (Apart from positive topological entropy, which $X$ must have, of course.)

For instance, if $X$ is an irreducible sofic subshift, does it always hold?

$\endgroup$
  • 1
    $\begingroup$ Are you perhaps missing a condition? If $X$ contains a periodic points with periodic word $u$, then just set $s=u$ and $t=uu$. I guess you want something like $s^\infty \neq t^\infty$? (some kind of 'independence' condition on $s$ and $t$) $\endgroup$ – Dan Rust Sep 27 '17 at 0:33
  • 1
    $\begingroup$ Even still, for irreducible sofic subshifts, it's enough to find two distinct loops in the corresponding right resolved graph which have the same 'root'. I think all you need for that is to have two distinct periodic orbits and irreducibility? $\endgroup$ – Dan Rust Sep 27 '17 at 0:37
  • $\begingroup$ The precise characterization for sofic shifts to have the property is that they contain uncountably many points, or equivalently have positive entropy. $\endgroup$ – Ville Salo Jun 8 '18 at 14:53
  • $\begingroup$ If you want that all the words obtained by concatenating are distinct, that is, e.g. s and t are distinct and have the same length. Otherwise take a periodic point w^\omega and pick s = t = w. $\endgroup$ – Ville Salo Jun 8 '18 at 15:12
4
$\begingroup$

For an irreducible sofic shift which is not periodic you will have this property. The Fischer cover gives a strongly connected deterministic partial automaton with all states initial and final recognizing the $\mathcal L(X)$. For any vertex v, the set of words labeling a loop at v is a free monoid on the words labeling a loop at v that do not visit v except at the beginning and end. If the strongly connected graph is not a cycle you have at least two such words.

More generally you just need that in the Krieger cover some strongly connected component is not a cycle.

$\endgroup$
  • $\begingroup$ Thank you for your answer, Benjamin. I'm not that familiar with this area so could you provide more details (or a reference), please? $\endgroup$ – Nikita Sidorov Sep 27 '17 at 9:34
  • 1
    $\begingroup$ For the Krieger and Fischer cover you can look at the book of Lind and Marcus. What I call a partial deterministic automaton they call right resolving. For the fact that the language of labels of loops on an automaton is free is an exercise. Each loop can be uniquely factored so that each factor never visits the base vertex in the middle. $\endgroup$ – Benjamin Steinberg Sep 27 '17 at 10:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.