ABSTRACT
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 40 Programming exercises . . . . . . . . . . . . . . . . . . . . . 41 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 42
2 Combinatorial Properties of Partial Words 43 2.1 Conjugacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.1.1 The equation xz = zy . . . . . . . . . . . . . . . . . 43 2.1.2 The equation xz ↑ zy . . . . . . . . . . . . . . . . . . 44
2.2 Commutativity . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.2.1 The equation xy = yx . . . . . . . . . . . . . . . . . 48 2.2.2 The equation xy ↑ yx . . . . . . . . . . . . . . . . . . 48 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 57 Programming exercises . . . . . . . . . . . . . . . . . . . . . 58 Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 59
3 Fine and Wilf’s Theorem 63 3.1 The case of zero or one hole . . . . . . . . . . . . . . . . . . 63 3.2 The case of two or three holes . . . . . . . . . . . . . . . . . 64 3.3 Special partial words . . . . . . . . . . . . . . . . . . . . . . 67
3.3.1 p = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 . . . . .
