A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Self-Shuffling Words
Tekijät: E Charlier, T Kamae, S Puzynina, L Zamboni
Toimittaja: F V Fomin, R Freivalds, M Z Kwiatkowska, D Peleg
Julkaisuvuosi: 2013
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II
Sarjan nimi: Lecture Notes in Compure Science
Aloitussivu: 113
Lopetussivu: 124
ISBN: 978-3-642-39211-5
eISBN: 978-3-642-39212-2
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-642-39212-2_13
Tiivistelmä
In this paper we introduce and study a new property of infinite words: An infinite word x is said to be self-shuffling if there exists a shuffle of two copies of x which produces x. 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 uniformly recurrent 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 greater than 0 (while those of intercept 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 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.
In this paper we introduce and study a new property of infinite words: An infinite word x is said to be self-shuffling if there exists a shuffle of two copies of x which produces x. 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 uniformly recurrent 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 greater than 0 (while those of intercept 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 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.
Turun yliopiston Tutkimustietojärjestelmän portaali