Infinite self-shuffling words

DOI10.1016/J.JCTA.2014.07.008zbMATH Open1309.68161arXiv1302.3844OpenAlexW2050080033MaRDI QIDQ458277FDOQ458277

Authors: Émilie Charlier, Teturo Kamae, Svetlana Puzynina, Luca Q. Zamboni

Publication date: 7 October 2014

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: In this paper we introduce and study a new property of infinite words: An infinite word

x i n A^{m} a t h b b N

, with values in a finite set

A

, is said to be

k

-self-shuffling

(k g e q 2)

if

x

admits factorizations:

x = p r o d_{i = 0}^{i} n f t y U_{i}^{(1)} c d o t s U_{i}^{(k)} = p r o d_{i = 0}^{i} n f t y U_{i}^{(1)} = c d o t s = p r o d_{i = 0}^{i} n f t y U_{i}^{(k)}

. In other words, there exists a shuffle of

k

-copies of

x

which produces

x

. We are particularly interested in the case

k = 2

, in which case we say

x

is self-shuffling. This property of infinite words is shown to be an intrinsic property of the word and not of its language (set of factors). For instance, every aperiodic word contains a non self-shuffling word in its shift orbit closure. While the property of being self-shuffling is a relatively strong condition, many important words arising in the area of symbolic dynamics are verified to be self-shuffling. They include for instance the Thue-Morse word and all Sturmian words of intercept

0 < h o < 1

(while those of intercept

h o = 0

are not self-shuffling). Our characterization of self-shuffling Sturmian words can be interpreted arithmetically in terms of a dynamical embedding and defines an arithmetic process we call the {it stepping stone model}. One important feature of self-shuffling words stems from its morphic invariance, which provides a useful tool for showing that one word is not the morphic image of another. The notion of self-shuffling has other unexpected applications particularly in the area of substitutive dynamical systems. For example, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic.

Full work available at URL: https://arxiv.org/abs/1302.3844

Recommendations

zbMATH Keywords

Lyndon words Thue-Morse word Sturmian words morphic words word shuffling

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

Cited In (12)

This page was built for publication: Infinite self-shuffling words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458277)