Automatic Sequences : Theory, Applications, Generalizations

Combining concepts of mathematics and computer science, this book is about the sequences of symbols that can be generated by simple models of computation called ''finite automata''. Suitable for graduate students or advanced undergraduates, it starts from elementary principles and develops the basic theory. The study then progresses to show how these ideas can be applied to solve problems in number theory and physics. 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 Uniting Dozens Of Seemingly Disparate Results From Different Fields, This Book Combines Concepts From Mathematics And Computer Science To Present The First Integrated Treatment Of Sequences Generated By 'finite Automata'. The Authors Apply The Theory To The Study Of Automatic Sequences And Their Generalizations, Such As Sturmian Words And K-regular Sequences. And Further, They Provide Applications To Number Theory (particularly To Formal Power Series And Transcendence In Finite Characteristic), Physics, Computer Graphics, And Music. Starting From First Principles Wherever Feasible, Basic Results From Combinatorics On Words, Numeration Systems, And Models Of Computation Are Discussed. Thus This Book Is Suitable For Graduate Students Or Advanced Undergraduates, As Well As For Mature Researchers Wishing To Know More About This Fascinating Subject. Results Are Presented From First Principles Wherever Feasible, And The Book Is Supplemented By A Collection Of 460 Exercises, 85 Open Problems, And Over 1600 Citations To The Literature. Jean-paul Allouche, Jeffrey Shallit. Title From Publisher's Bibliographic System (viewed On 01 Jun 2016). Mode Of Access: World Wide Web. "The authors develop the theory of automatic sequences and their generalizations, such as Sturmian words and [kappa]-regular sequences. Further, they discuss applications to number theory (particularly formal power series and transcendence in finite characteristic), physics, computer graphics, and music." "Results are presented from first principles wherever feasible, and the book is supplemented by a collection of 460 exercises, 85 open problems, and more than 1600 citations to the literature. Thus, this book is suitable for graduate students or advanced undergraduates, as well as for mature researchers wishing to know more about this subject."--Jacket This is a book about the sequences of symbols that can be generated by simple models of computation called 'finite automata'. It starts from first principles and develops the basic theory, then demonstrates applications to problems in number theory and physics. Suitable for graduates or advanced undergraduates In this chapter we introduce the basic objects of interest to this book: finite and infinite words.