Fiche du document
28 octobre 2011
- handle: 10670/1.kkiqc5
- Blondin Massé, Alexandre; Brlek, Srecko; Labbé, Sébastien et Vuillon, Laurent (2011). « Palindromic complexity of codings of rotations ». Theoretical Computer Science, 412(46), pp. 6455-6463.
Ce document est lié à :
http://archipel.uqam.ca/8430/
Ce document est lié à :
http://dx.doi.org/10.1016/j.tcs
Ce document est lié à :
doi:10.1016/j.tcs.2011.08.007
Mots-clés
Codings of rotations Sturmian Rote Return words Full wordsSujets proches
Palindromes, English Factors Agents, Manufacturers' Manufacturers' representatives Infinity Case Proof FactorsCiter ce document
Alexandre Blondin Massé et al., « Palindromic complexity of codings of rotations », UQAM Archipel : articles scientifiques, ID : 10670/1.kkiqc5
Métriques
Partage / Export
Résumé
We study the palindromic complexity of infinite words obtained by coding rotations on partitions of the unit circle by inspecting the return words. The main result is that every coding of rotations on two intervals is full, that is, it realizes the maximal palindromic complexity. As a byproduct, a slight improvement about return words in codings of rotations is obtained: every factor of a coding of rotations on two intervals has at most 4 complete return words, where the bound is realized only for a finite number of factors. We also provide a combinatorial proof for the special case of complementary-symmetric Rote sequences by considering both palindromes and antipalindromes occurring in it.