2
$\begingroup$

Let $\Sigma$ be a finite alphabet of size at least 2. A (possibly infinite) string $s$ over alphabet $\Sigma$ encounters a pattern $p \in \mathbb{N}^*$ iff there is a non-erasing morphism $f: \mathbb{N} \to \Sigma^*$ (that is, $f$ never takes an empty word value) such that $f(p)$ is a substring (or factor) of $s$. Otherwise, $s$ avoids $p$.

Clearly, if $s$ avoids $p$, then it does so under any permutation of letters in $\Sigma$. Also, a left shift of $s$ (just $s$ without the first letter) must avoid $p$ too. Let us call infinite strings $s$ and $t$ equivalent if they can be made equal after a finite sequence of left shifts (each of them may be applied to each of the strings) and/or permutation of letters in $\Sigma$ (applied only to one of the strings).

Is there an alphabet $\Sigma$ and a finite set of patterns $p_1, \ldots, p_n$ such that all infinite strings over $\Sigma$ avoiding $p_1, \ldots, p_n$ are equivalent (and of course, at least one such string exists)?

Improve this question
$\endgroup$
4
  • $\begingroup$ Is $\mathbb N=(\mathbb N,+)$? If so --- am I right that $s$ avoids $p+1$ if it avoids $p$? $\endgroup$
    – Ilya Bogdanov
    Commented Sep 28, 2017 at 4:51
  • $\begingroup$ @IlyaBogdanov No, $\mathbb{N}$ are just independent characters of the pattern. For a finite sequence $p \in \mathbb{N}^*$ $f(p)$ is just concatenation of words corresponding to characters of the pattern. $\endgroup$
    – Mikhail Tikhomirov
    Commented Sep 28, 2017 at 8:29
  • $\begingroup$ Ah, now I understand; sorry, I was confused by $\mathbb N^*$... $\endgroup$
    – Ilya Bogdanov
    Commented Sep 28, 2017 at 9:02
  • $\begingroup$ It would really help to make the question understandable if, instead of writing $\mathbb{N}$ you wrote "$\Phi$, with $\Phi$ being an arbitrary fixed countably infinite alphabet" (since apparently you don't care about operations on the naturals). Furthermore, by "$f\colon\Phi\to\Sigma^*$ a morphism" you really mean "$f\colon\Phi^*\to\Sigma^*$ the unique monoid morphism which extends $f\colon\Phi\to\Sigma^*$". Otherwise, since $\mathbb{N}$ happens to be a monoid and some people write $\mathbb{N}^*$ for nonzero natural numbers, sources of confusion abound! $\endgroup$
    – Gro-Tsen
    Commented Sep 28, 2017 at 21:27

1 Answer 1

Reset to default
2
$\begingroup$

I am not certain that examples exist for your rather strong definition of equivalence; however, if you modify the problem slightly, then there are some known results. First, consider bi-infinite words $s$ and $t$ (rather than one-way infinite words) and say that $s$ and $t$ are equivalent if they have the same set of finite factors. Then, over $\{0,1\}$, it is known that a bi-infinite word avoids the set of patterns $\{xxx, xyxyx\}$ if and only if it is equivalent to the bi-infinite Thue--Morse word (see Gottschalk and Hedlund, "A characterization of the Morse minimal set", 1964). Ochem and Rosenfeld have recently done some further work in this direction: http://www.lirmm.fr/~ochem/morphisms/main.pdf (look for "essentially avoids" in their paper).

In fact, I guess the answer to your original question should be "no". If a pattern is avoidable, then it is avoidable by a uniformly recurrent (or "almost periodic") word $s$ (this is a result of Furstenberg). However, every infinite word in the shift orbit closure of $s$ also avoids the pattern, but the shift orbit closure of an aperiodic but uniformly recurrent word is uncountable (see Section 13.7 of Lind and Marcus, Symbolic Dynamics and Coding). Since the shift orbit closure is uncountable, there must be words in it that are not equivalent up to some initial shift.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .