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?

Improve this question
$\endgroup$
4
  • 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, 2017 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, 2017 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, 2018 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, 2018 at 15:12

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2017 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, 2017 at 10:13

Your Answer

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

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