Book contents
- Frontmatter
- Contents
- Foreword
- Preface
- Preface to this edition
- Chapter 1 Words
- Chapter 2 Square-Free Words and Idempotent Semigroups
- Chapter 3 Van der Waerden's Theorem
- Chapter 4 Repetitive Mappings and Morphisms
- Chapter 5 Factorizations of Free Monoids
- Chapter 6 Subwords
- Chapter 7 Unavoidable Regularities in Words and Algebras with Polynomial Identities
- Chapter 8 The Critical Factorization Theorem
- Chapter 9 Equations in Words
- Chapter 10 Rearrangements of Words
- Chapter 11 Words and Trees
- Bibliography
- Index
Chapter 2 - Square-Free Words and Idempotent Semigroups
Published online by Cambridge University Press: 04 November 2009
- Frontmatter
- Contents
- Foreword
- Preface
- Preface to this edition
- Chapter 1 Words
- Chapter 2 Square-Free Words and Idempotent Semigroups
- Chapter 3 Van der Waerden's Theorem
- Chapter 4 Repetitive Mappings and Morphisms
- Chapter 5 Factorizations of Free Monoids
- Chapter 6 Subwords
- Chapter 7 Unavoidable Regularities in Words and Algebras with Polynomial Identities
- Chapter 8 The Critical Factorization Theorem
- Chapter 9 Equations in Words
- Chapter 10 Rearrangements of Words
- Chapter 11 Words and Trees
- Bibliography
- Index
Summary
Introduction
The investigation of words includes a series of combinatorial studies with rather surprising conclusions that can be summarized roughly by the following statement: Each sufficiently long word over a finite alphabet behaves locally in a regular fashion. That is to say, an arbitrary word, subject only to the constraint that it be sufficiently long, possesses some regularity. This claim becomes meaningful only if one specifies the kind of regularities that are intended, of course. The discovery and the analysis of these unavoidable regularities constitute a major topic in the combinatorics of words. A typical example is furnished by van der Waerden's theorem.
It should not be concluded that any sufficiently long word is globally regular. On the contrary, the existence of unavoidable regularities leads to the dual question of avoidable regularities: properties not automatically shared by all sufficiently long words. For such a property there exist infinitely many words (finiteness of the alphabet is supposed) that do not satisfy it. The present chapter is devoted mainly to the study of one such property.
A square is a word of the form uu, with u a nonempty word. A word contains a square if one of its factors is a square; otherwise, the word is called square-free. For instance, abcacbacbc contains the square acbacb, and abcacbabcb is square-free. The answer to the question of whether every sufficiently long word contains a square is no, provided the alphabet has at least three letters.
- Type
- Chapter
- Information
- Combinatorics on Words , pp. 18 - 38Publisher: Cambridge University PressPrint publication year: 1997
- 3
- Cited by