Combinatorics on Words: Christoffel Words and Repetitions ...

Combinatorics on Words: Christoffel Words and Repetitions in Words

Jean Berstel

Aaron Lauve Christophe Reutenauer Franco Saliola

2008

Ce livre est d?edi?e `a la m?emoire de Pierre Leroux (1942?2008).

Contents

I Christoffel Words

1

1 Christoffel Words

3

1.1 Geometric definition . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Cayley graph definition . . . . . . . . . . . . . . . . . . . . . 6

2 Christoffel Morphisms

9

2.1 Christoffel morphisms . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Standard Factorization

19

3.1 The standard factorization . . . . . . . . . . . . . . . . . . . . 19

3.2 The Christoffel tree . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Palindromization

27

4.1 Christoffel words and palindromes . . . . . . . . . . . . . . . 27

4.2 Palindromic closures . . . . . . . . . . . . . . . . . . . . . . . 28

4.3 Palindromic characterization . . . . . . . . . . . . . . . . . . 36

5 Primitive Elements in the Free Group F2

41

5.1 Positive primitive elements of the free group . . . . . . . . . . 41

5.2 Positive primitive characterization . . . . . . . . . . . . . . . 43

6 Characterizations

47

6.1 The Burrows?Wheeler transform . . . . . . . . . . . . . . . . 47

6.2 Balanced1 Lyndon words . . . . . . . . . . . . . . . . . . . . . 50

6.3 Balanced2 Lyndon words . . . . . . . . . . . . . . . . . . . . . 50

6.4 Circular words . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6.5 Periodic phenomena . . . . . . . . . . . . . . . . . . . . . . . 54

i

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

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

Google Online Preview   Download