License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.40
URN: urn:nbn:de:0030-drops-64540
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6454/
Go to the corresponding LIPIcs Volume Portal

Gamard, Guilhem ; Richomme, Gwenaël

Determining Sets of Quasiperiods of Infinite Words

pdf-format:
LIPIcs-MFCS-2016-40.pdf (0.4 MB)

Abstract

A word is quasiperiodic if it can be obtained by concatenations and overlaps of a smaller word, called a quasiperiod. Based on links between quasiperiods, right special factors and square factors, we introduce a method to determine the set of quasiperiods of a given right infinite word. Then we study the structure of the sets of quasiperiods of right infinite words and, using our method, we provide examples of right infinite words with extremal sets of quasiperiods (no quasiperiod is quasiperiodic, all quasiperiods except one are quasiperiodic, ...). Our method is also used to provide a short proof of a recent characterization of quasiperiods of the Fibonacci word. Finally we extend this result to a new characterization of standard Sturmian words using a property of their sets of quasiperiods.

BibTeX - Entry

@InProceedings{gamard_et_al:LIPIcs:2016:6454,
  author =	{Guilhem Gamard and Gwena{\"e}l Richomme},
  title =	{{Determining Sets of Quasiperiods of Infinite Words}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{40:1--40:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6454},
  URN =		{urn:nbn:de:0030-drops-64540},
  doi =		{10.4230/LIPIcs.MFCS.2016.40},
  annote =	{Keywords: combinatorics on Words, quasiperiodicity, Sturmian words}
}

Keywords: combinatorics on Words, quasiperiodicity, Sturmian words
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI