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]

[img]
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:

DateEvent
16 March 2015Accepted
13 April 2015Published Online
11 July 2015Published

Item ID:

28016

Date Deposited:

14 Jan 2020 09:18

Last Modified:

15 Jan 2020 17:44

Peer Reviewed:

Yes, this version has been peer-reviewed.

URI:

http://research.gold.ac.uk/id/eprint/28016

View statistics for this item...

Edit Record Edit Record (login required)