Table of Contents
List of contributors ix
Preface xi
Acknowledgements xix
1 Preliminaries V. Berthé M. Rigo 1
1.1 Conventions 1
1.2 Words 3
1.3 Languages and machines 13
1.4 Associated matrices 22
1.5 A glimpse at numeration systems 26
1.6 Symbolic dynamics 27
1.7 Exercises 32
1.8 Notes 33
2 Number representation and finite automata Ch. Frougny J. Sakarovitch 34
2.1 Introduction 34
2.2 Representation in integer base 37
2.3 Representation in real base 53
2.4 Canonical numeration systems 77
2.5 Representation in rational base 84
2.6 A primer on finite automata and transducers 95
2.7 Notes 103
3 Abstract numeration systems P. Lecomte M. Rigo 108
3.1 Motivations 108
3.2 Computing numerical values and S-representations 117
3.3 S-recognisable sets 122
3.4 Automatic sequences 138
3.5 Representing real numbers 152
3.6 Exercises and open problems 158
3.7 Notes 160
4 Factor complexity J. Cassaigne F. Nicolas 163
4.1 Introduction 163
4.2 Definitions, basic properties, and first examples 163
4.3 The theorem of Morse and Hedlund 166
4.4 High complexity 168
4.5 Tools for low complexity 171
4.6 Moiphisms and complexity 181
4.7 The theorem of Pansiot 185
4.8 Complexity of automatic words 214
4.9 Control of bispecial factors 215
4.10 Examples of complexity computations for morphic words 221
4.11 Complexity computation for an s-adic family of words 226
4.12 Exercises and open problems 239
5 Substitutions, Rauzy fractals and tilings V. Berthé A. Siegel J. Thuswaldner 248
5.1 Introduction 248
5.2 Basic definitions 250
5.3 Tilings 259
5.4 Ancestor graphs and tiling conditions 273
5.5 Boundary and contact graphs 284
5.6 Geometric coincidences 290
5.7 Overlap coincidences 296
5.8 Balanced pair algorithm 309
5.9 Conclusion 315
5.10 Exercises 316
5.11 Notes 317
6 Combinatorics on Bratteli diagrams and dynamical systems F.Durand 324
6.1 Introduction 324
6.2 Cantor dynamical systems 325
6.3 Bratteli diagrams 325
6.4 The Bratteli-Vershik model theorem 330
6.5 Examples of BV-models 336
6.6 Characterisation of Strong Orbit Equivalence 351
6.7 Entropy 357
6.8 Invariant measures and Bratteli diagrams 360
6.9 Eigenvalues of stationary BV-models 364
6.10 Exercises 370
7 Infinite words with uniform frequencies, and invariant measures S. Ferenczi T. Monteil 373
7.1 Basic notions 374
7.2 Invariant measures and unique ergodicity 376
7.3 Combinatorial criteria 383
7.4 Examples 388
7.5 Counter-examples 395
7.6 Further afield 405
7.7 Exercises 406
7.8 Note: Dictionary between word combinatorics and symbolic dynamics 409
8 Transcendence and Diophantine approximation B. Adamczewski Y. Bugeaud 410
8.1 The expansion of algebraic numbers in an integer base 412
8.2 Basics from continued fractions 427
8.3 Transcendental continued fractions 430
8.4 Simultaneous rational approximations 436
8.5 Explicit examples for the Littlewood conjecture 443
8.6 Exercises and open problems 448
8.7 Notes 449
9 Analysis of digital functions and applications M. Drmota P. J. Grabner 452
9.1 Introduction: digital functions 452
9.2 Asymptotic analysis of digital functions 456
9.3 Statistics on digital functions 480
9.4 Further results 499
10 The equality problem for purely substitutive words J. Honkala 505
10.1 Purely substitutive words and D0L systems 505
10.2 Substitutive words and HD0L sequences 507
10.3 Elementary morphisms 509
10.4 Nearly primitive D0L systems 512
10.5 Periodic and nearly periodic words 515
10.6 A balance property for ω-equivalent 1-systems 519
10.7 The equality problem for purely substitutive words 523
10.8 Automatic words 525
10.9 Complexity questions 526
10.10 Exercises 527
11 Long products of matrices V. D. Blondel R. M. Jungers 530
11.1 The joint spectral characteristics 531
11.2 Applications 541
11.3 The finiteness property 550
11.4 Approximation algorithms 552
11.5 Conclusions 558
11.6 Exercises 559
11.7 Notes 561
References 563
Notation index 594
General index 599
