Automatic sequences: theory, applications, generalizations

Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Goals of This Book......Page 15
Prerequisites......Page 16
Acknowledgments......Page 17
1.1 Alpha Words......Page 19
1.2 Topology and Measure......Page 23
1.3 Languages and Regular Expressions......Page 25
1.4 Morphisms......Page 26
1.5 The Theorems of Lyndon and Schützenberger......Page 28
1.6 Repetitions in Words......Page 32
1.7 Overlap-Free Binary Words......Page 34
1.8 Additional Topics on Repetitions......Page 41
1.9 Exercises......Page 42
1.10 Open Problems......Page 48
1.11 Notes on Chapter 1......Page 49
2.2 Rational and Irrational Numbers......Page 57
2.3 Algebraic and Transcendental Numbers......Page 59
2.4 Continued Fractions......Page 62
2.5 Basics of Diophantine Approximation......Page 66
2.6 The Three-Distance Theorem......Page 71
2.7 Algebraic Structures......Page 73
2.9 Fields......Page 74
2.10 Polynomials, Rational Functions, and Formal Power Series......Page 76
2.11 Rho-adic Numbers......Page 80
2.13 Some Useful Estimates......Page 81
2.14 Exercises......Page 82
2.16 Notes on Chapter 2......Page 85
3.1 Numeration Systems......Page 88
3.2 Sums of Digits......Page 92
3.3 Block Counting and Digital Sequences......Page 95
3.4 Representation of Real Numbers......Page 102
3.5 Sums of Sums of Digits......Page 104
3.6 Base-k Representation with Alternate Digit Sets......Page 119
3.7 Representations in Negative Bases......Page 121
3.8 Fibonacci Representation......Page 123
3.9 Ostrowski’s Alpha-Numeration System......Page 124
3.10 Representations in Complex Bases......Page 125
3.11 Exercises......Page 130
3.12 Open Problems......Page 136
3.13 Notes on Chapter 3......Page 137
4.1 Finite Automata......Page 146
4.2 Proving Languages Nonregular......Page 154
4.3 Finite Automata with Output......Page 155
4.4 Context-Free Grammars and Languages......Page 161
4.6 Turing Machines......Page 164
4.7 Exercises......Page 166
4.9 Notes on Chapter 4......Page 168
5.1 Automatic Sequences......Page 170
5.2 Robustness of the Automatic Sequence Concept......Page 175
5.3 Two-Sided Automatic Sequences......Page 179
5.4 Basic Properties of Automatic Sequences......Page 183
5.5 Nonautomatic Sequences......Page 184
5.6 Kappa-Automatic Sets......Page 186
5.7 1-Automatic Sequences......Page 187
5.8 Exercises......Page 188
5.10 Notes on Chapter 5......Page 189
6.2 The Thue–Morse Infinite Word......Page 191
6.3 Cobham’s Theorem......Page 192
6.4 The Tower of Hanoi and Iterated Morphisms......Page 195
6.5 Paperfolding and Continued Fractions......Page 199
6.6 The Kappa-Kernel......Page 203
6.7 Cobham’s Theorem for (Kappa, lota)-Numeration Systems......Page 205
6.8 Basic Closure Properties......Page 207
6.9 Uniform Transduction of Automatic Sequences......Page 210
6.10 Sums of Digits, Polynomials, and Automatic Sequences......Page 215
6.11 Exercises......Page 219
6.12 Open Problems......Page 225
6.13 Notes on Chapter 6......Page 226
7.1 The Infinite Fibonacci Word......Page 230
7.2 Finite Fixed Points......Page 231
7.3 Morphic Sequences and Infinite Fixed Points......Page 233
7.4 Two-Sided Infinite Fixed Points......Page 236
7.5 More on Infinite Fixed Points......Page 244
7.6 Closure Properties......Page 246
7.7 Morphic Images of Morphic Words......Page 249
7.8 Locally Catenative Sequences......Page 255
7.9 Transductions of Morphic Sequences......Page 258
7.10 Exercises......Page 260
7.11 Open Problems......Page 262
7.12 Notes on Chapter 7......Page 263
8.1 Some Examples......Page 265
8.2 The Incidence Matrix Associated with a Morphism......Page 266
8.3 Some Results on Non-negative Matrices......Page 267
8.4 Frequencies of Letters and Words in a Morphic Sequence......Page 284
8.5 An Application......Page 294
8.6 Gaps......Page 296
8.7 Exercises......Page 298
8.9 Notes......Page 300
9.1 Definitions and Basic Properties......Page 301
9.2 Geometric Interpretation of Characteristic Words......Page 308
9.3 Application: Unusual Continued Fractions......Page 309
9.4 Exercises......Page 311
9.6 Notes on Chapter 9......Page 313
10.1 Introduction......Page 316
10.2 Basic Properties of Subword Complexity......Page 318
10.3 Results for Automatic Sequences......Page 322
10.4 Subword Complexity for Morphic Words......Page 324
10.5 Sturmian Words......Page 330
10.6 Sturmian Words and kappath-Power-Freeness......Page 338
10.7 Subword Complexity of Finite Words......Page 341
10.8 Recurrence......Page 342
10.9 Uniform Recurrence......Page 346
10.10 Appearance......Page 351
10.11 Exercises......Page 352
10.13 Notes on Chapter 10......Page 358
11.1 Syndetic and Right Dense Sets......Page 363
11.2 Proof of Cobham’s Theorem......Page 365
11.4 Notes on Chapter 11......Page 368
12 Formal Power Series......Page 369
12.1 Examples......Page 370
12.2 Christol’s Theorem......Page 372
12.4 Formal Laurent Power Series and Carlitz Functions......Page 377
12.5 Transcendence of Values of the Carlitz–Goss Gamma Function......Page 380
12.6 Application to Transcendence Proofs over Q(X)......Page 383
12.7 Furstenberg’s Theorem......Page 385
12.8 Exercises......Page 389
12.9 Open Problems......Page 393
12.10 Notes on Chapter 12......Page 394
13.1 Basic Properties of the Automatic Reals......Page 397
13.2 Non-closure Properties of lota(kappa, b)......Page 400
13.3 Transcendence: An Ad Hoc Approach......Page 403
13.4 Transcendence of the Thue–Morse Number......Page 405
13.5 Transcendence of Morphic Real Numbers......Page 409
13.6 Transcendence of Characteristic Real Numbers......Page 411
13.7 The Thue–Morse Continued Fraction......Page 412
13.8 Exercises......Page 418
13.9 Open Problems......Page 420
13.10 Notes on Chapter 13......Page 421
14.1 The Sierpinski Carpet......Page 423
14.2 Formal Definitions and Basic Results......Page 426
14.3 Subword Complexity......Page 430
14.4 Formal Power Series......Page 431
14.5 Automatic Sequences in Base – 1 + i......Page 432
14.6 The Pascal Triangle Modulo d......Page 438
14.7 Exercises......Page 442
14.8 Open Problems......Page 443
14.9 Notes on Chapter 14......Page 444
15.1 Basic Notions......Page 446
15.2 Nondeterministic Automaticity......Page 449
15.3 Unary Automaticity......Page 451
15.4 Automaticity of Sequences......Page 452
15.6 Open Problems......Page 454
15.7 Notes on Chapter 15......Page 455
16.1 Basics......Page 456
16.2 Robustness of the kappa-Regularity Concept......Page 459
16.3 Further Results......Page 462
16.4 kappa-Regular Power Series......Page 463
16.5 Additional Examples......Page 465
16.6 Exercises......Page 467
16.7 Open Problems......Page 471
16.8 Notes on Chapter 16......Page 472
17 Physics......Page 473
17.1 The One-Dimensional Ising Model......Page 475
17.2 The Rudin–Shapiro Sequence and the One-Dimensional Ising Model......Page 477
17.3 Distribution Results fo the Rudin–Shapiro Sequence......Page 480
17.4 The One-Dimensional Schrödinger Operator......Page 482
17.5 Exercises......Page 484
17.6 Notes on Chapter 17......Page 485
A.1 Chapter 1......Page 489
A.3 Chapter 3......Page 490
A.6 Chapter 6......Page 492
A.7 Chapter 7......Page 493
A.10 Chapter 10......Page 494
A.13 Chapter 13......Page 495
A.16 Chapter 16......Page 496
A.17 Chapter 17......Page 497
Bibliography......Page 499
Index......Page 573