Algorithmic Combinatorics on Partial Words

by Francine Blanchet-Sadri

Overview

The discrete mathematics and theoretical computer science communities have recently witnessed explosive growth in the area of algorithmic combinatorics on words. The next generation of research on combinatorics of partial words promises to have a substantial impact on molecular biology, nanotechnology, data communication, and DNA computing. Delving into this emerging research area, Algorithmic Combinatorics on Partial Words presents a mathematical treatment of combinatorics on partial words designed around algorithms and explores up-and-coming techniques for solving partial word problems as well as the future direction of research.

This five-part book begins with a section on basics that covers terminology, the compatibility of partial words, and combinatorial properties of words. The book then focuses on three important concepts of periodicity on partial words: period, weak period, and local period. The next part describes a linear time algorithm to test primitivity on partial words and extends the results on unbordered words to unbordered partial words while the following'section introduces some important properties of pcodes, details a variety of ways of defining and analyzing pcodes, and shows that the pcode property is decidable using two different techniques. In the final part, the author solves various equations on partial words, presents binary and ternary correlations, and covers unavoidable sets of partial words.

Setting the tone for future research in this field, this book lucidly develops the central ideas and results of combinatorics on partial words.

Product Details

ISBN-13:	9780367388256
Publisher:	Taylor & Francis
Publication date:	09/19/2019
Pages:	392
Product dimensions:	6.12(w) x 9.19(h) x (d)

Table of Contents

Preface 13

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 71

3.4 Graphs associated with partial words 73

3.5 The main result 79

3.6 Related results 82

Exercises 86

Challenging exercises 88

Programming exercises 89

Websites 90

Bibliographic notes 90

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 112

Challenging exercises 113

Programming exercises 114

Websites 115

Bibliographic notes 115

5 Guibas and Odlyzko's Theorem 117

5.1 The zero-hole case 117

5.2 The main result 120

5.3 The algorithm 145

Exercises 151

Challenging exercises 152

Programming exercises 153

Website 153

Bibliographic notes 154

III Primitivity 155

6 Primitive Partial Words 157

6.1 Testing primitivity on partial words 158

6.2 Counting primitive partial words 162

6.3 Exact periods 164

6.4 First counting method 170

6.5 Second counting method 174

6.5.1 The one-hole case 178

6.5.2 The two-hole case 181

6.6 Existence of primitive partial words 187

Exercises 195

Challenging exercises 196

Programming exercises 196

Website 197

Bibliographic notes 197

7 Unbordered Partial Words 199

7.1 Concatenations of prefixes 200

7.2 More results on concatenations of prefixes 207

7.3 Critical factorizations 213

7.4 Conjugates 216

Exercises 217

Challenging exercises 219

Programming exercises 220

Website 220

Bibliographic notes 221

IV Coding 223

8 Pcodes of Partial Words 225

8.1 Binary relations 225

8.2 Pcodes 229

8.2.1 The class F 233

8.2.2 The class G 234

8.3 Pcodes and monoids 236

8.4 Prefix and suffix orderings 239

8.5 Border ordering 241

8.6 Commutative ordering 244

8.7 Circular pcodes 249

Exercises 253

Challenging exercises 254

Programming exercises 254

Website 255

Bibliographic notes 255

9 Deciding the Pcode Property 257

9.1 First algorithm 257

9.2 Second algorithm 264

9.2.1 Domino technique on words 264

9.2.2 Domino technique on partial words 267

Exercises 275

Challenging exercises 276

Programming exercises 277

Website 277

Bibliographic notes 277

V Further Topics 279

10 Equations on Partial Words 281

10.1 The equation x^m ↑ yⁿ 281

10.2 The equation x² ↑ y^mz 287

10.3 The equation x^myⁿ ↑ z^p 290

Exercises 292

Challenging exercises 293

Programming exercises 294

Website 294

Bibliographic notes 295

11 Correlations of Partial Words 297

11.1 Binary and ternary correlations 297

11.2 Characterizations of correlations 299

11.3 Distributive lattices 305

11.3.1 Δ_nAn is a distributive lattice 309

11.3.2 Δ_n' is a distributive lattice 309

11.4 Irreducible period sets 315

11.5 Counting correlations 318

Exercises 321

Challenging exercises 322

Programming exercises 323

Website 323

Bibliographic notes 323

12 Unavoidable Sets of Partial Words 325

12.1 Unavoidable sets 325

12.2 Classifying unavoidable sets of size two 328

12.3 The case where k = 1 and l = 1 330

12.4 The case where k - 1 and l = 2 331

12.5 Larger values of k and l 339

Exercises 340

Challenging exercises 341

Programming exercises 342

Website 342

Bibliographic notes 342

Solutions to Selected Exercises 345

References 369

Index 379