A4 Refereed article in a conference publication

A square root map on Sturmian words (Extended abstract)




Subtitle(Extended abstract)

AuthorsPeltomäki Jarkko,Whiteland Markus

EditorsManea Florin,Nowotka Dirk

Conference nameInternational conference on combinatorics on words

Publication year2015

JournalLecture Notes in Computer Science

Book title Combinatorics on Words : 10th International Conference, WORDS 2015 : Kiel, Germany, September 14-17, 2015 : Proceedings

Series titleLecture Notes in Computer Science

Volume9304

First page 197

Last page209

Number of pages13

ISBN978-3-319-23659-9

eISBN978-3-319-23660-5

DOIhttps://doi.org/10.1007/978-3-319-23660-5(external)


Abstract

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.



Last updated on 2024-26-11 at 16:07