You are here

Automatic Sequences: Theory, Application, Generalizations

Jean-Paul Allouche and Jeffrey Shallit
Publisher: 
Cambridge University Press
Publication Date: 
2003
Number of Pages: 
571
Format: 
Hardcover
Price: 
50.00
ISBN: 
0521823323
Category: 
Monograph
We do not plan to review this book.
Preface page xiii
1 Stringology 1
1.1 Words 1
1.2 Topology and Measure 5
1.3 Languages and Regular Expressions 7
1.4 Morphisms 8
1.5 The Theorems of Lyndon and Schùutzenberger 10
1.6 Repetitions in Words 14
1.7 Overlap-Free Binary Words 16
1.8 Additional Topics on Repetitions 23
1.9 Exercises 24
1.10Open Problems 30
1.11 Notes on Chapter 1 31
2 Number Theory and Algebra 39
2.1 Divisibility and Valuations 39
2.2 Rational and Irrational Numbers 39
2.3 Algebraic and Transcendental Numbers 41
2.4 Continued Fractions 44
2.5 Basics of Diophantine Approximation 48
2.6 The Three-Distance Theorem 53
2.7 Algebraic Structures 55
2.8 Vector Spaces 56
2.9 Fields 56
2.10Polynomials, Rational Functions, and Formal Power Series 58
2.11 p-adic Numbers 62
2.12 Asymptotic Notation 63
2.13 Some Useful Estimates 63
2.14 Exercises 64
2.15 Open Problems 67
2.16 Notes on Chapter 2 67
vii
¸ Cambridge University Press www.cambridge.org
Cambridge University Press
0521823323 - Automatic Sequences: Theory, Applications, Generalizations
Jean-Paul Allouche and Jeffrey Shallit
Table of Contents
More information
viii Contents
3 Numeration Systems 70
3.1 Numeration Systems 70
3.2 Sums of Digits 74
3.3 Block Counting and Digital Sequences 77
3.4 Representation of Real Numbers 84
3.5 Sums of Sums of Digits 86
3.6 Base-k Representation with Alternate Digit Sets 101
3.7 Representations in Negative Bases 103
3.8 Fibonacci Representation 105
3.9 Ostrowski's a-Numeration System 106
3.10Representations in Complex Bases 107
3.11 Exercises 112
3.12 Open Problems 118
3.13 Notes on Chapter 3 119
4 Finite Automata and Other Models of Computation 128
4.1 Finite Automata 128
4.2 Proving Languages Nonregular 136
4.3 Finite Automata with Output 137
4.4 Context-Free Grammars and Languages 143
4.5 Context-Sensitive Grammars and Languages 146
4.6 Turing Machines 146
4.7 Exercises 148
4.8 Open Problems 150
4.9 Notes on Chapter 4 150
5 Automatic Sequences 152
5.1 Automatic Sequences 152
5.2 Robustness of the Automatic Sequence Concept 157
5.3 Two-Sided Automatic Sequences 161
5.4 Basic Properties of Automatic Sequences 165
5.5 Nonautomatic Sequences 166
5.6 k-Automatic Sets 168
5.7 1-Automatic Sequences 169
5.8 Exercises 170
5.9 Open Problems 171
5.10Notes on Chapter 5 171
6 Uniform Morphisms and Automatic Sequences 173
6.1 Fixed Points of Uniform Morphisms 173
6.2 The Thue-Morse Infinite Word 173
6.3 Cobham's Theorem 174
6.4 The Tower of Hanoi and Iterated Morphisms 177
6.5 Paperfolding and Continued Fractions 181
6.6 The k-Kernel 185
¸ Cambridge University Press www.cambridge.org
Cambridge University Press
0521823323 - Automatic Sequences: Theory, Applications, Generalizations
Jean-Paul Allouche and Jeffrey Shallit
Table of Contents
More information
Contents ix
6.7 Cobham's Theorem for (k, l)-Numeration Systems 187
6.8 Basic Closure Properties 189
6.9 Uniform Transduction of Automatic Sequences 192
6.10Sums of Digits, Polynomials, and Automatic Sequences 197
6.11 Exercises 201
6.12 Open Problems 207
6.13 Notes on Chapter 6 208
7 Morphic Sequences 212
7.1 The Infinite Fibonacci Word 212
7.2 Finite Fixed Points 213
7.3 Morphic Sequences and Infinite Fixed Points 215
7.4 Two-Sided Infinite Fixed Points 218
7.5 More on Infinite Fixed Points 226
7.6 Closure Properties 228
7.7 Morphic Images of Morphic Words 231
7.8 Locally Catenative Sequences 237
7.9 Transductions of Morphic Sequences 240
7.10Ex ercises 242
7.11 Open Problems 244
7.12 Notes on Chapter 7 245
8 Frequency of Letters 247
8.1 Some Examples 247
8.2 The Incidence Matrix Associated with a Morphism 248
8.3 Some Results on Non-negative Matrices 249
8.4 Frequencies of Letters and Words in a Morphic Sequence 266
8.5 An Application 276
8.6 Gaps 278
8.7 Exercises 280
8.8 Open Problems 282
8.9 Notes 282
9 Characteristic Words 283
9.1 Definitions and Basic Properties 283
9.2 Geometric Interpretation of Characteristic Words 290
9.3 Application: Unusual Continued Fractions 291
9.4 Exercises 293
9.5 Open Problems 295
9.6 Notes on Chapter 9 295
10Subw ords 298
10.1 Introduction 298
10.2 Basic Properties of Subword Complexity 300
10.3 Results for Automatic Sequences 304
10.4 Subword Complexity for Morphic Words 306
¸ Cambridge University Press www.cambridge.org
Cambridge University Press
0521823323 - Automatic Sequences: Theory, Applications, Generalizations
Jean-Paul Allouche and Jeffrey Shallit
Table of Contents
More information
x Contents
10.5 Sturmian Words 312
10.6 Sturmian Words and kth-Power-Freeness 320
10.7 Subword Complexity of Finite Words 323
10.8 Recurrence 324
10.9 Uniform Recurrence 328
10.10 Appearance 333
10.11 Exercises 334
10.12 Open Problems 340
10.13 Notes on Chapter 10 340
11 Cobham's Theorem 345
11.1 Syndetic and Right Dense Sets 345
11.2 Proof of Cobham's Theorem 347
11.3 Exercises 350
11.4 Notes on Chapter 11 350
12 Formal Power Series 351
12.1 Examples 352
12.2 Christol's Theorem 354
12.3 First Application to Transcendence Results 359
12.4 Formal Laurent Power Series and Carlitz Functions 359
12.5 Transcendence of Values of the Carlitz-Goss Gamma Function 362
12.6 Application to Transcendence Proofs over Q(X) 365
12.7 Furstenberg's Theorem 367
12.8 Exercises 371
12.9 Open Problems 375
12.10Notes on Chapter 12 376
13 Automatic Real Numbers 379
13.1 Basic Properties of the Automatic Reals 379
13.2 Non-closure Properties of L(k, b) 382
13.3 Transcendence: An Ad Hoc Approach 385
13.4 Transcendence of the Thue-Morse Number 387
13.5 Transcendence of Morphic Real Numbers 391
13.6 Transcendence of Characteristic Real Numbers 393
13.7 The Thue-Morse Continued Fraction 394
13.8 Exercises 400
13.9 Open Problems 402
13.10Notes on Chapter 13 403
14 Multidimensional Automatic Sequences 405
14.1 The Sierpiïnski Carpet 405
14.2 Formal Definitions and Basic Results 408
14.3 Subword Complexity 412
14.4 Formal Power Series 413
14.5 Automatic Sequences in Base -1 + i 414
¸ Cambridge University Press www.cambridge.org
Cambridge University Press
0521823323 - Automatic Sequences: Theory, Applications, Generalizations
Jean-Paul Allouche and Jeffrey Shallit
Table of Contents
More information
Contents xi
14.6 The Pascal Triangle Modulo d 420
14.7 Exercises 424
14.8 Open Problems 425
14.9 Notes on Chapter 14 426
15 Automaticity 428
15.1 Basic Notions 428
15.2 Nondeterministic Automaticity 431
15.3 Unary Automaticity 433
15.4 Automaticity of Sequences 434
15.5 Exercises 436
15.6 Open Problems 436
15.7 Notes on Chapter 15 437
16 k-Regular Sequences 438
16.1 Basics 438
16.2 Robustness of the k-Regular Concept 441
16.3 Further Results 444
16.4 k-Regular Power Series 445
16.5 Additional Examples 447
16.6 Exercises 449
16.7 Open Problems 453
16.8 Notes on Chapter 16 454
17 Physics 455
17.1 The One-Dimensional Ising Model 457
17.2 The Rudin-Shapiro Sequence and the One-Dimensional
Ising Model 459
17.3 Distribution Results for the Rudin-Shapiro Sequence 462
17.4 The One-Dimensional Schrùodinger Operator 464
17.5 Exercises 466
17.6 Notes on Chapter 17 467
Appendix
Hints, References, and Solutions for Selected Exercises 471
A.1 Chapter 1 471
A.2 Chapter 2 472
A.3 Chapter 3 472
A.4 Chapter 4 474
A.5 Chapter 5 474
A.6 Chapter 6 474
A.7 Chapter 7 475
A.8 Chapter 8 476
A.9 Chapter 9 476
A.10Chapter 10 476
A.11 Chapter 11 477
¸ Cambridge University Press www.cambridge.org
Cambridge University Press
0521823323 - Automatic Sequences: Theory, Applications, Generalizations
Jean-Paul Allouche and Jeffrey Shallit
Table of Contents
More information
xii Contents
A.12 Chapter 12 477
A.13 Chapter 13 477
A.14 Chapter 14 478
A.15 Chapter 15 478
A.16 Chapter 16 478
A.17 Chapter 17 479
Bibliography 481
Index
Tags: