Table of contents for Algorithmic combinatorics on partial words / Francine Blanchet-Sadri.

Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.


Counter
 
Contents
Preface 11
I BASICS 23
1 Preliminaries on Partial Words 25
1.1 Alphabets, letters, and words . . . . . . . . . . . . . . . . . . 25
1.2 Partial functions and partial words . . . . . . . . . . . . . . 27
1.3 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.4 Factorizations of partial words . . . . . . . . . . . . . . . . . 32
1.5 Recursion and induction on partial words . . . . . . . . . . . 35
1.6 Containment and compatibility . . . . . . . . . . . . . . . . . 36
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
II PERIODICITY 61
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
3.3.2 p > 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3
3.4 Graphs associated with partial words . . . . . . . . . . . . . 74
3.5 The main result . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.6 Related results . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 89
Programming exercises . . . . . . . . . . . . . . . . . . . . . 90
Websites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 91
4 Critical Factorization Theorem 93
4.1 Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2 The zero-hole case . . . . . . . . . . . . . . . . . . . . . . . . 96
4.3 The main result: First version . . . . . . . . . . . . . . . . . 98
4.4 The main result: Second version . . . . . . . . . . . . . . . . 104
4.5 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 114
Programming exercises . . . . . . . . . . . . . . . . . . . . . 115
Websites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 115
5 Guibas and Odlyzko¿s Theorem 119
5.1 The zero-hole case . . . . . . . . . . . . . . . . . . . . . . . . 119
5.2 The main result . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.3 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 155
Programming exercises . . . . . . . . . . . . . . . . . . . . . 156
Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 157
III PRIMITIVITY 159
6 Primitive Partial Words 161
6.1 Testing primitivity on partial words . . . . . . . . . . . . . . 162
6.2 Counting primitive partial words . . . . . . . . . . . . . . . . 166
6.3 Exact periods . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.4 First counting method . . . . . . . . . . . . . . . . . . . . . . 174
6.5 Second counting method . . . . . . . . . . . . . . . . . . . . 178
6.5.1 The one-hole case . . . . . . . . . . . . . . . . . . . . 182
6.5.2 The two-hole case . . . . . . . . . . . . . . . . . . . . 186
6.6 Existence of primitive partial words . . . . . . . . . . . . . . 191
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 201
Programming exercises . . . . . . . . . . . . . . . . . . . . . 202
Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 203
7 Unbordered Partial Words 205
7.1 Concatenations of prefixes . . . . . . . . . . . . . . . . . . . 206
7.2 More results on concatenations of prefixes . . . . . . . . . . . 214
7.3 Critical factorizations . . . . . . . . . . . . . . . . . . . . . . 220
7.4 Conjugates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 225
Programming exercises . . . . . . . . . . . . . . . . . . . . . 226
Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 227
IV CODING 229
8 Pcodes of Partial Words 231
8.1 Binary relations . . . . . . . . . . . . . . . . . . . . . . . . . 231
8.2 Pcodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
8.2.1 The class F . . . . . . . . . . . . . . . . . . . . . . . . 239
8.2.2 The class G . . . . . . . . . . . . . . . . . . . . . . . . 241
8.3 Pcodes and monoids . . . . . . . . . . . . . . . . . . . . . . . 242
8.4 Prefix and suffix orderings . . . . . . . . . . . . . . . . . . . 245
8.5 Border ordering . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.6 Commutative ordering . . . . . . . . . . . . . . . . . . . . . 250
8.7 Circular pcodes . . . . . . . . . . . . . . . . . . . . . . . . . 255
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 260
Programming exercises . . . . . . . . . . . . . . . . . . . . . 261
Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 262
9 Deciding the Pcode Property 263
9.1 First algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 263
9.2 Second algorithm . . . . . . . . . . . . . . . . . . . . . . . . 270
9.2.1 Domino technique on words . . . . . . . . . . . . . . . 270
9.2.2 Domino technique on partial words . . . . . . . . . . . 273
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 282
Programming exercises . . . . . . . . . . . . . . . . . . . . . 283
Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 283
V FURTHER TOPICS 285
10 Equations on Partial Words 287
10.1 The equation xm " yn . . . . . . . . . . . . . . . . . . . . . 287
10.2 The equation x2 " ymz . . . . . . . . . . . . . . . . . . . . . 293
10.3 The equation xmyn " zp . . . . . . . . . . . . . . . . . . . . 297
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 299
Programming exercises . . . . . . . . . . . . . . . . . . . . . 300
Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 301
11 Correlations of Partial Words 303
11.1 Binary and ternary correlations . . . . . . . . . . . . . . . . 303
11.2 Characterizations of correlations . . . . . . . . . . . . . . . . 305
11.3 Distributive lattices . . . . . . . . . . . . . . . . . . . . . . . 311
11.3.1 n is a distributive lattice . . . . . . . . . . . . . . . 315
11.3.2 0n is a distributive lattice . . . . . . . . . . . . . . . 315
11.4 Irreducible period sets . . . . . . . . . . . . . . . . . . . . . . 321
11.5 Counting correlations . . . . . . . . . . . . . . . . . . . . . . 324
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 328
Programming exercises . . . . . . . . . . . . . . . . . . . . . 329
Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 330
12 Unavoidable Sets of Partial Words 331
12.1 Unavoidable sets . . . . . . . . . . . . . . . . . . . . . . . . . 331
12.2 Classifying unavoidable sets of size two . . . . . . . . . . . . 334
12.3 The case where k = 1 and l = 1 . . . . . . . . . . . . . . . 336
12.4 The case where k = 1 and l = 2 . . . . . . . . . . . . . . . 337
12.5 Larger values of k and l . . . . . . . . . . . . . . . . . . . . . 345
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
Challenging exercises . . . . . . . . . . . . . . . . . . . . . . 348
Programming exercises . . . . . . . . . . . . . . . . . . . . . 348
Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . 349
Solutions to Selected Exercises 350
Bibliography 375
References 375
Index 383

Library of Congress Subject Headings for this publication:

Computer algorithms.
Computer science -- Mathematics.
Combinatorial analysis.