Characterization of some binary words with few squares

Badkobeh, Golnaz and Ochem, Pascal. 2015. Characterization of some binary words with few squares. Theoretical Computer Science, 588, pp. 73-80. ISSN 0304-3975 [Article]
Copy

Thue proved that the factors occurring infinitely many times in square-free words over {0,1,2} avoiding the factors in {010,212} are the factors of the fixed point of the morphism 0 → 012, 1 → 02, 2 → 1. He similarly characterized square-free words avoiding {010,020} and {121,212} as the factors of two morphic words. In this paper, we exhibit smaller morphisms to define these two square-free morphic words and we give such characterizations for six types of binary words containing few distinct squares.


picture_as_pdf
avoidability.pdf
subject
Accepted Version
Available under Creative Commons: Attribution-NonCommercial-No Derivative Works 3.0

View Download

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads