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]

Preview

Text 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:	Article
Identification Number (DOI):	https://doi.org/10.1016/j.tcs.2015.03.044
Keywords:	Combinatorial problems, Repetitions, Avoidability
Departments, Centres and Research Units:	Computing
Dates:	Date Event 30 March 2015 Accepted 13 April 2015 Published Online 11 July 2015 Published
Item ID:	28016
Date Deposited:	14 Jan 2020 09:18
Last Modified:	09 Jun 2021 13:45
Peer Reviewed:	Yes, this version has been peer-reviewed.
URI:	https://research.gold.ac.uk/id/eprint/28016

View statistics for this item...

Edit Record (login required)