Determining Sets of Quasiperiods of Infinite Words

Guilhem Gamard 1 Gwenaël Richomme 2, 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01369373
Contributor : Gwenaël Richomme <>
Submitted on : Tuesday, September 20, 2016 - 9:15:10 PM
Last modification on : Friday, June 28, 2019 - 4:08:51 PM

File

LIPIcs-MFCS-2016-40.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Guilhem Gamard, Gwenaël Richomme. Determining Sets of Quasiperiods of Infinite Words. MFCS: Mathematical Foundations of Computer Science, Aug 2016, Cracovie, Poland. pp.40:1-40:13, ⟨10.4230/LIPIcs.MFCS.2016.40⟩. ⟨lirmm-01369373⟩

Share

Metrics

Record views

215

Files downloads

264