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.
Type de document :
Communication dans un congrès
Piotr Faliszewski; Anca Muscholl; Rolf Niedermeier. MFCS: Mathematical Foundations of Computer Science, Aug 2016, Cracovie, Poland. 41st International Symposium on Mathematical Foundations of Computer Science, 58, pp.40:1-40:13, 2016, Leibniz International Proceedings in Informatics (LIPIcs). 〈http://mfcs.ki.agh.edu.pl〉. 〈10.4230/LIPIcs.MFCS.2016.40〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01369373
Contributeur : Gwenaël Richomme <>
Soumis le : mardi 20 septembre 2016 - 21:15:10
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05

Fichier

LIPIcs-MFCS-2016-40.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Guilhem Gamard, Gwenaël Richomme. Determining Sets of Quasiperiods of Infinite Words. Piotr Faliszewski; Anca Muscholl; Rolf Niedermeier. MFCS: Mathematical Foundations of Computer Science, Aug 2016, Cracovie, Poland. 41st International Symposium on Mathematical Foundations of Computer Science, 58, pp.40:1-40:13, 2016, Leibniz International Proceedings in Informatics (LIPIcs). 〈http://mfcs.ki.agh.edu.pl〉. 〈10.4230/LIPIcs.MFCS.2016.40〉. 〈lirmm-01369373〉

Partager

Métriques

Consultations de la notice

88

Téléchargements de fichiers

115