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]

avoidability.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (414kB) | Preview

Abstract or Description

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:


Identification Number (DOI):


Combinatorial problems, Repetitions, Avoidability

Departments, Centres and Research Units:



30 March 2015Accepted
13 April 2015Published Online
11 July 2015Published

Item ID:


Date Deposited:

14 Jan 2020 09:18

Last Modified:

09 Jun 2021 13:45

Peer Reviewed:

Yes, this version has been peer-reviewed.


View statistics for this item...

Edit Record Edit Record (login required)