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]
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.
Item Type | Article |
---|---|
Keywords | Combinatorial problems, Repetitions, Avoidability |
Departments, Centres and Research Units | Computing |
Date Deposited | 14 Jan 2020 09:18 |
Last Modified | 09 Jun 2021 13:45 |