On shuffling of infinite square-free words (Q2260629)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On shuffling of infinite square-free words |
scientific article |
Statements
On shuffling of infinite square-free words (English)
0 references
11 March 2015
0 references
An infinite word \(x\) is a shuffle of two infinite words \(y,z\) if there exist decompositions \(y=\prod_{i=0}^{\infty}U_{i}\), \(z=\prod_{i=0}^{\infty}V_{i}\) to finite factors such that \(x=\prod_{i=0}^{\infty}U_{i}V_{i}\). If \(x\) can be expressed as its shuffle with itself, it is called self-shuffling. An infinite word is square-free if it does not contain a factor of the form \(uu\), where \(u\) is a non-empty finite word. The shift orbit of an infinite word \(x\) consists of all infinite words whose every finite factor is a factor of \(x\). The paper provides affirmative answer to two open questions. \newline1. Does there exist a square-free self-shuffling word? [\textit{T. Harju}, Lect. Notes Comput. Sci. 8079, 154--160 (2013; Zbl 1309.68163)] The paper presents a square-free self-shuffling infinite word over a 3-letter alphabet. \newline2. Does there exist an infinite word such that its shift orbit does not contain any self-shuffling word? [\textit{É. Charlier} et al., J. Comb. Theory, Ser. A 128, 1--40 (2014; Zbl 1309.68161)] It is shown that the Hall word (obtained by infinite iteration of the morphism \(0\mapsto012\), \(1\mapsto02\), \(2\mapsto1\)) has the required property. Actually, a stronger result is obtained, stating that if \(x\) is a shuffle of two words \(y,z\) from the orbit of the Hall word then \(x,y,z\) are pairwise different.
0 references
infinite word
0 references
shuffle
0 references
self-shuffling word
0 references
square-free word
0 references
Hall word
0 references
shift orbit closure
0 references