## Automatic Sequences: Theory, Applications, GeneralizationsUniting 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Stringology | 1 |

12 Topology and Measure | 5 |

13 Languages and Regular Expressions | 7 |

14 Morphisms | 8 |

15 The Theorems of Lyndon and Schiitzenberger | 10 |

16 Repetitions in Words | 14 |

17 OverlapFree Binary Words | 16 |

18 Additional Topics on Repetitions | 23 |

Characteristic Words | 283 |

92 Geometric Interpretation of Characteristic Words | 290 |

Unusual Continued Fractions | 291 |

94 Exercises | 293 |

95 Open Problems | 295 |

Subwords | 298 |

102 Basic Properties of Subword Complexity | 300 |

103 Results for Automatic Sequences | 304 |

19 Exercises | 24 |

110 Open Problems | 30 |

111 Notes on Chapter 1 | 31 |

Number Theory and Algebra | 39 |

23 Algebraic and Transcendental Numbers | 41 |

24 Continued Fractions | 44 |

25 Basics of Diophantine Approximation | 48 |

26 The ThreeDistance Theorem | 53 |

27 Algebraic Structures | 55 |

28 Vector Spaces | 56 |

210 Polynomials Rational Functions and Formal Power Series | 58 |

211 padic Numbers | 62 |

212 Asymptotic Notation | 63 |

214 Exercises | 64 |

215 Open Problems | 67 |

Numeration Systems | 70 |

33 Block Counting and Digital Sequences | 77 |

34 Representation of Real Numbers | 84 |

35 Sums of Sums of Digits | 86 |

Representation with Alternate Digit Sets | 101 |

37 Representations in Negative Bases | 103 |

38 Fibonacci Representation | 105 |

39 Ostrowskis aNumeration System | 106 |

310 Representations in Complex Bases | 107 |

311 Exercises | 112 |

312 Open Problems | 118 |

313 Notes on Chapter 3 | 119 |

Finite Automata and Other Models of Computation | 128 |

42 Proving Languages Nonregular | 136 |

43 Finite Automata with Output | 137 |

44 ContextFree Grammars and Languages | 143 |

45 ContextSensitive Grammars and Languages | 146 |

47 Exercises | 148 |

48 Open Problems | 150 |

Automatic Sequences | 152 |

52 Robustness of the Automatic Sequence Concept | 157 |

53 TwoSided Automatic Sequences | 161 |

54 Basic Properties of Automatic Sequences | 165 |

55 Nonautomatic Sequences | 166 |

56 A Automatic Sets | 168 |

57 1Automatic Sequences | 169 |

58 Exercises | 170 |

59 Open Problems | 171 |

Uniform Morphisms and Automatic Sequences | 173 |

63 Cobhams Theorem | 174 |

65 Paperfolding and Continued Fractions | 181 |

Kernel | 185 |

67 Cobhams Theorem for k lNumeration Systems | 187 |

68 Basic Closure Properties | 189 |

69 Uniform Transduction of Automatic Sequences | 192 |

610 Sums of Digits Polynomials and Automatic Sequences | 197 |

611 Exercises | 201 |

612 Open Problems | 207 |

613 Notes on Chapter 6 | 208 |

Morphic Sequences | 212 |

72 Finite Fixed Points | 213 |

7 3 Morphic Sequences and Infinite Fixed Points | 215 |

74 TwoSided Infinite Fixed Points | 218 |

75 More on Infinite Fixed Points | 226 |

76 Closure Properties | 228 |

77 Morphic Images of Morphic Words | 231 |

78 Locally Catenative Sequences | 237 |

79 Transductions of Morphic Sequences | 240 |

710 Exercises | 242 |

711 Open Problems | 244 |

712 Notes on Chapter 7 | 245 |

Frequency of Letters | 247 |

82 The Incidence Matrix Associated with a Morphism | 248 |

83 Some Results on Nonnegative Matrices | 249 |

84 Frequencies of Letters and Words in a Morphic Sequence | 266 |

85 An Application | 276 |

86 Gaps | 278 |

87 Exercises | 280 |

88 Open Problems | 282 |

104 Subword Complexity for Morphic Words | 306 |

105 St mm i an Words | 312 |

106 Sturmian Words and AthPowerFreeness | 320 |

107 Subword Complexity of Finite Words | 323 |

108 Recurrence | 324 |

109 Uniform Recurrence | 328 |

1010 Appearance | 333 |

1011 Exercises | 334 |

1012 Open Problems | 340 |

Cobhams Theorem | 345 |

112 Proof of Cobhams Theorem | 347 |

113 Exercises | 350 |

Formal Power Series | 351 |

121 Examples | 352 |

122 Christols Theorem | 354 |

123 First Application to Transcendence Results | 359 |

125 Transcendence of Values of the CarlitzGoss Gamma Function | 362 |

126 Application to Transcendence Proofs over QX | 365 |

127 Furstenbergs Theorem | 367 |

128 Exercises | 371 |

129 Open Problems | 375 |

1210 Notes on Chapter 12 | 376 |

Automatic Real Numbers | 379 |

132 Nonclosure Properties of Lk b | 382 |

An Ad Hoc Approach | 385 |

134 Transcendence of the ThueMorse Number | 387 |

135 Transcendence of Morphic Real Numbers | 391 |

136 Transcendence of Characteristic Real Numbers | 393 |

137 The ThueMorse Continued Fraction | 394 |

138 Exercises | 400 |

139 Open Problems | 402 |

1310 Notes on Chapter 13 | 403 |

Multidimensional Automatic Sequences | 405 |

142 Formal Definitions and Basic Results | 408 |

143 Sub word Complexity | 412 |

144 Formal Power Series | 413 |

145 Automatic Sequences in Base 1 + i | 414 |

146 The Pascal Triangle Modulo d | 420 |

147 Exercises | 424 |

148 Open Problems | 425 |

149 Notes on Chapter 14 | 426 |

Automaticity | 428 |

152 Nondeterministic Automaticity | 431 |

15 3 Unary Automaticity | 433 |

154 Automaticity of Sequences | 434 |

155 Exercises | 436 |

157 Notes on Chapter 15 | 437 |

kRegular Sequences | 438 |

162 Robustness of the ARegularity Concept | 441 |

163 Further Results | 444 |

164 ARegular Power Series | 445 |

165 Additional Examples | 447 |

166 Exercises | 449 |

167 Open Problems | 453 |

168 Notes on Chapter 16 | 454 |

Physics | 455 |

171 The OneDimensional Ising Model | 457 |

172 The RudinShapiro Sequence and the OneDimensional Ising Model | 459 |

173 Distribution Results for the RudinShapiro Sequence | 462 |

174 The OneDimensional Schrodinger Operator | 464 |

175 Exercises | 466 |

176 Notes on Chapter 17 | 467 |

Hints References and Solutions for Selected Exercises | 471 |

A2 Chapter 2 | 472 |

A4 Chapter 4 | 474 |

A7 Chapter 7 | 475 |

A8 Chapter 8 | 476 |

A 11 Chapter 11 | 477 |

A14 Chapter 14 | 478 |

A17 Chapter 17 | 479 |

Bibliography | 481 |

555 | |

### Common terms and phrases

2-regular A:-automatic algebraic algorithm Allouche Amer automatic sequences automaton base base-A Berstel binary Cassaigne coding coefficients consider contains continued fraction contradiction Corollary Crochemore define denote DFAO digits Ehrenfeucht eigenvalue entries example Exercise exists an integer expansion Fibonacci word finite alphabet finite automata finite-state fixed point formal power series Fraenkel Frougny function Hence induction input iterating k-automatic Lemma letter Math matrix Mendes France morphic sequence morphism morphism h non-negative integers nonempty Number Theory numeration system occurs Open Problems overlap-free word palindromes paperfolding sequence Perron-Frobenius polynomial positive integers prefix prime number primitive Proof properties prove rational regular language regular paperfolding sequence result Rozenberg Rudin-Shapiro sequence Sbow Section Shallit Show squarefree words string Sturmian words subword complexity subword of length Suppose symbols Thue-Morse sequence Towers of Hanoi transcendental transducer two-dimensional ultimately periodic uniformly recurrent vector zeros