A4 Artikkeli konferenssijulkaisussa
A square root map on Sturmian words (Extended abstract)

Alaotsikko: (Extended abstract)
Julkaisun tekijät: Peltomäki Jarkko,Whiteland Markus
Julkaisuvuosi: 2015
Journal: Lecture Notes in Computer Science
Kirjan nimi *: Combinatorics on Words
Sarjan nimi: Lecture Notes in Computer Science
Volyymi: 9304
Sivujen määrä: 13
ISBN: 978-3-319-23659-9
eISBN: 978-3-319-23660-5

Tiivistelmä

We introduce a square root map on Sturmian words and study its properties. Given a Sturmian word of slope \$alpha\$, there exists exactly six minimal squares in its language (a minimal square does not have a square as a proper prefix). A Sturmian word \$s\$ of slope \$alpha\$ can be written as a product of these six minimal squares: \$s = X_1^2 X_2^2 X_3^2 cdots\$. The square root of \$s\$ is defined to be the word \$sqrt{s} = X_1 X_2 X_3 cdots\$. The main result of this paper is that that \$sqrt{s}\$ is also a Sturmian word of slope \$alpha\$. Moreover, we characterize the Sturmian fixed points of the square root map, and we describe how to find the intercept of \$sqrt{s}\$ and an occurrence of any prefix of \$sqrt{s}\$ in \$s\$. Related to the square root map, we characterize the solutions of the word equation \$X_1^2 X_2^2 cdots X_n^2 = (X_1 X_2 cdots X_n)^2\$ in the language of Sturmian words of slope \$alpha\$ where the words \$X_i^2\$ are minimal squares of slope \$alpha\$.

We also study the square root map in a more general setting. We explicitly construct an infinite set of non-Sturmian fixed points of the square root map. We show that the subshifts \$Omega\$ generated by these words have a curious property: for all \$w in Omega\$ either \$sqrt{w} in Omega\$ or \$sqrt{w}\$ is periodic. In particular, the square root map can map an aperiodic word to a periodic word.

Sisäiset tekijät/toimittajat

Last updated on 2019-21-08 at 22:56