Automatic Sequences: Theory, Applications, Generalizations

Front Cover
Cambridge University Press, Jul 21, 2003 - Computers - 571 pages
0 Reviews
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.
 

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
Index
555
Copyright

Common terms and phrases

References to this book

All Book Search results »

About the author (2003)

Jeffrey Shallit is Professor of the David R. Cheriton School of Computer Science at the University of Waterloo. He is the author of Algorithmic Number Theory (co-authored with Eric Bach) and Automatic Sequences: Theory, Applications, Generalizations (co-authored with Jean-Paul Allouche). He has published approximately 90 articles on number theory, algebra, automata theory, complexity theory, and the history of mathematics and computing.

Bibliographic information