Article (Scientific journals)
Infinite self-shuffling words
Charlier, Emilie; Kamae, Teturo; Puzynina, Svetlana et al.
2014In Journal of Combinatorial Theory. Series A, 128, p. 1-40
Peer Reviewed verified by ORBi
 

Files


Full Text
SS-extended(November-22-2013).pdf
Author preprint (376.06 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Abstract :
[en] In this paper we introduce and study a new property of infinite words: An infinite word x, with values in a finite set A, is said to be k-self-shuffling (k≥2) if 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 independent of the complexity of the word as measured by the number of distinct factors of each length. Examples exist from bounded to full complexity. It is also 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 fixed by the morphism 0↦01, 1↦10. As another example we show that all Sturmian words of intercept 0<ρ<1 are self-shuffling (while those of intercept ρ=0 are not). 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 stepping stone model. One important feature of self-shuffling words stems from their morphic invariance: The morphic image of a self-shuffling word is self-shuffling. This provides a useful tool for showing that one word is not the morphic image of another. In addition to its morphic invariance, this new notion 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.
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Kamae, Teturo
Puzynina, Svetlana
Zamboni, Luca
Language :
English
Title :
Infinite self-shuffling words
Publication date :
November 2014
Journal title :
Journal of Combinatorial Theory. Series A
ISSN :
0097-3165
Publisher :
Academic Press
Volume :
128
Pages :
1-40
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 28 October 2014

Statistics


Number of views
51 (6 by ULiège)
Number of downloads
193 (1 by ULiège)

Scopus citations®
 
7
Scopus citations®
without self-citations
3
OpenCitations
 
4
OpenAlex citations
 
8

Bibliography


Similar publications



Contact ORBi