Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > A Square Root Map on Sturmian ...

A Square Root Map on Sturmian Words

Jarkko Peltomäki, Markus Whiteland, A Square Root Map on Sturmian Words. In: Florin Manea, Dirk Nowotka (Eds.), Combinatorics on Words, Lecture Notes in Computer Science 9304, 197–209, Springer International Publishing, 2015.

http://dx.doi.org/10.1007/978-3-319-23660-5

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$. We prove that $\sqrt{s}$ is also a Sturmian word of slope $\alpha$. Moreover, 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_m^2 = (X_1 X_2 \cdots X_m)^2$ in the language of Sturmian words of slope $\alpha$ where the words $X_i^2$ are minimal squares of slope $\alpha$.

BibTeX entry:

@INPROCEEDINGS{inpPeWh15a,
  title = {A Square Root Map on Sturmian Words},
  booktitle = {Combinatorics on Words},
  author = {Peltomäki, Jarkko and Whiteland, Markus},
  volume = {9304},
  series = {Lecture Notes in Computer Science},
  editor = {Manea, Florin and Nowotka, Dirk},
  publisher = {Springer International Publishing},
  pages = {197–209},
  year = {2015},
  ISSN = {0302-9743},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication