Combinatorics, automata, and number theory

This collaborative volume presents trends arising from the fruitful interaction between the themes of combinatorics on words, automata and formal language theory, and number theory. Presenting several important tools and concepts, the authors also reveal some of the exciting and important relationships that exist between these different fields. Topics include numeration systems, word complexity function, morphic words, Rauzy tilings and substitutive dynamical systems, Bratelli diagrams, frequencies and ergodicity, Diophantine approximation and transcendence, asymptotic properties of digital functions, decidability issues for D0L systems, matrix products and joint spectral radius. Topics are presented in a way that links them to the three main themes, but also extends them to dynamical systems and ergodic theory, fractals, tilings and spectral properties of matrices. Graduate students, research mathematicians and computer scientists working in combinatorics, theory of computation, number theory, symbolic dynamics, fractals, tilings and stringology will find much of interest in this book.

V. Berthé and M. RigoCh. Frougny and J. SakarovitchP. Lecomte and M. RigoJ. Cassaigne and F. NicolasV. Berthé and A. Siegel and J. ThuswaldnerF.DurandS. Ferenczi and T. MonteilB. Adamczewski and Y. BugeaudM. Drmota and P. J. GrabnerJ. HonkalaV. D. Blondel and R. M. Jungers

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

Available:*

On Order

Summary

Summary

Table of Contents