Overlap-Free Words and Generalizations

[Pages:123]Overlap-Free Words and Generalizations

by

Narad Rampersad

A thesis presented to the University of Waterloo

in fulfillment of the thesis requirement for the degree of

Doctor of Philosophy in

Computer Science

Waterloo, Ontario, Canada, 2007

c Narad Rampersad 2007

I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public.

ii

Abstract

The study of combinatorics on words dates back at least to the beginning of the 20th century and the work of Axel Thue. Thue was the first to give an example of an infinite word over a three letter alphabet that contains no squares (identical adjacent blocks) xx. This result was eventually used to solve some longstanding open problems in algebra and has remarkable connections to other areas of mathematics and computer science as well.

This thesis will consider several different generalizations of Thue's work. In particular we shall study the properties of infinite words avoiding various types of repetitions.

In Chapter 1 we introduce the theory of combinatorics on words. We present the basic definitions and give an historical survey of the area.

In Chapter 2 we consider the work of Thue in more detail. We present various well-known properties of the Thue?Morse word and give some generalizations. We examine Fife's characterization of the infinite overlap-free words and give a simpler proof of this result. We also present some applications to transcendental number theory, generalizing a classical result of Mahler.

In Chapter 3 we generalize a result of S?e?ebold by showing that the only infinite 7/3-power-free binary words that can be obtained by iterating a morphism are the Thue?Morse word and its complement.

In Chapter 4 we continue our study of overlap-free and 7/3-power-free words. We discuss the squares that can appear as subwords of these words. We also show that it is possible to construct infinite 7/3-power-free binary words containing infinitely many overlaps.

In Chapter 5 we consider certain questions of language theory. In particular, we examine the context-freeness of the set of words containing overlaps. We show that over a three-letter alphabet, this set is not context-free, and over a two-letter alphabet, we show that this set cannot be unambiguously context-free.

In Chapter 6 we construct infinite words over a four-letter alphabet that avoid squares in any arithmetic progression of odd difference. Our constructions are based on properties of the paperfolding words. We use these infinite words to construct non-repetitive tilings of the integer lattice.

In Chapter 7 we consider approximate squares rather than squares. We give constructions of infinite words that avoid such approximate squares.

In Chapter 8 we conclude the work and present some open problems.

iii

Acknowledgments I would like to express my gratitude to my advisor Jeffrey Shallit for his guidance and support over the years. I would particularly like to thank him for introducing me to the area of combinatorics on words and for providing me with many interesting research problems on which to work. I would like to thank the members of my examining committee, Daniel Brown, Jonathan Buss, Kevin Hare, and Tero Harju, for having generously agreed to review the current work. It was a particular honour to have Tero Harju as the external examiner for this thesis. I would also like to thank my co-authors: Boris Adamczewski, Shandy Brown, James Currie, Jui-Yi Kao, Dalia Krieger, Pascal Ochem, Manuel Silva, and Troy Vasiga. Special thanks to Dalia: it was a pleasure to have her as, not only an officemate and a colleague, but also as a friend. I also thank Nicolae Santean for many interesting discussions on automata and other subjects. The research presented here was supported financially by the Natural Sciences and Engineering Research Council of Canada (NSERC).

iv

Contents

1 Combinatorics on Words

1

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.4 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.5 Morphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.6 Repetitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.7 Fractional repetitions . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.8 Some algorithmic results . . . . . . . . . . . . . . . . . . . . . . . . 6

1.9 Repetition-free morphisms . . . . . . . . . . . . . . . . . . . . . . . 7

1.10 Avoiding arbitrarily large repetitions . . . . . . . . . . . . . . . . . 7

1.11 Abelian repetitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.12 Circular words and unbordered words . . . . . . . . . . . . . . . . . 9

1.13 Enumerative combinatorics on words . . . . . . . . . . . . . . . . . 10

1.14 Letter frequencies in words . . . . . . . . . . . . . . . . . . . . . . . 12

1.15 Subword complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 The Thue?Morse Word and Overlap-Free Words

15

2.1 The standard definitions . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 A connection to squarefree words . . . . . . . . . . . . . . . . . . . 16

2.3 Properties of the Thue?Morse word . . . . . . . . . . . . . . . . . . 17

2.4 Squares in the Thue?Morse word . . . . . . . . . . . . . . . . . . . 18

2.5 Subword complexity of the Thue?Morse word . . . . . . . . . . . . 19

2.6 Finite modifications of the Thue?Morse word . . . . . . . . . . . . . 20

2.7 Fife's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.8 Generalizing Fife's Theorem . . . . . . . . . . . . . . . . . . . . . . 26

2.9 Transcendence of overlap-free base-b expansions . . . . . . . . . . . 28

v

3 Words Avoiding 7/3-powers and the Thue?Morse Morphism

33

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.2 Preliminary lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3 Main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.4 The constant 7/3 is best possible . . . . . . . . . . . . . . . . . . . 40

4 Binary Words Containing Infinitely Many Overlaps

43

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.2 Properties of the Thue-Morse morphism . . . . . . . . . . . . . . . 43

4.3 Overlap-free squares . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.4 7/3-power-free squares . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.5 Words containing infinitely many overlaps . . . . . . . . . . . . . . 48

5 Applications to the Theory of Context-free Languages

53

5.1 Definition of the context-free languages . . . . . . . . . . . . . . . . 53

5.2 Historical background . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.3 Languages derived from infinite words . . . . . . . . . . . . . . . . . 56

5.4 Sparse context-free languages . . . . . . . . . . . . . . . . . . . . . 57

5.5 The language Cosub(w) . . . . . . . . . . . . . . . . . . . . . . . . 58

5.6 The Chomsky?Schu?tzenberger Theorem . . . . . . . . . . . . . . . . 59

5.7 Techniques from analysis . . . . . . . . . . . . . . . . . . . . . . . . 60

5.8 Binary words containing overlaps . . . . . . . . . . . . . . . . . . . 61

6 Words Avoiding Repetitions in Arithmetic Progressions

65

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6.2 Van der Waerden and Carpi . . . . . . . . . . . . . . . . . . . . . . 65

6.3 Definitions and notation . . . . . . . . . . . . . . . . . . . . . . . . 66

6.4 Paperfolding words . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6.5 Perturbed symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.6 The Toeplitz construction . . . . . . . . . . . . . . . . . . . . . . . 68

6.7 Repetitions in the paperfolding words . . . . . . . . . . . . . . . . . 69

6.8 An application to -expansions . . . . . . . . . . . . . . . . . . . . 71

6.9 A language-theoretic result . . . . . . . . . . . . . . . . . . . . . . . 73

6.10 Avoiding repetitions in arithmetic progressions . . . . . . . . . . . . 73

6.11 Avoiding repetitions in higher dimensions . . . . . . . . . . . . . . . 77

vi

7 Avoiding Approximate Squares

79

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

7.2 Words of low similarity . . . . . . . . . . . . . . . . . . . . . . . . . 80

7.3 Words avoiding c-approximate squares . . . . . . . . . . . . . . . . 86

8 Conclusion and Open Problems

91

A Prouhet's Memoir

95

vii

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download