Combinatorics, Automata and Number Theory

This collaborative volume presents recent 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.

List of contributors	p. ix
Preface	p. xi
Acknowledgements	p. xix
Preliminaries	p. 1
Conventions	p. 1
Words	p. 3
Languages and machines	p. 13
Associated matrices	p. 22
A glimpse at numeration systems	p. 26
Symbolic dynamics	p. 27
Exercises	p. 32
Notes	p. 33
Number representation and finite automata	p. 34
Introduction	p. 34
Representation in integer base	p. 37
Representation in real base	p. 53
Canonical numeration systems	p. 77
Representation in rational base	p. 84
A primer on finite automata and transducers	p. 95
Notes	p. 103
Abstract numeration systems	p. 108
Motivations	p. 108
Computing numerical values and S-representations	p. 117
S-recognisable sets	p. 122
Automatic sequences	p. 138
Representing real numbers	p. 152
Exercises and open problems	p. 158
Notes	p. 160
Factor complexity	p. 163
Introduction	p. 163
Definitions, basic properties, and first examples	p. 163
The theorem of Morse and Hedlund	p. 166
High complexity	p. 168
Tools for low complexity	p. 171
Moiphisms and complexity	p. 181
The theorem of Pansiot	p. 185
Complexity of automatic words	p. 214
Control of bispecial factors	p. 215
Examples of complexity computations for morphic words	p. 221
Complexity computation for an s-adic family of words	p. 226
Exercises and open problems	p. 239
Substitutions, Rauzy fractals and tilings	p. 248
Introduction	p. 248
Basic definitions	p. 250
Tilings	p. 259
Ancestor graphs and tiling conditions	p. 273
Boundary and contact graphs	p. 284
Geometric coincidences	p. 290
Overlap coincidences	p. 296
Balanced pair algorithm	p. 309
Conclusion	p. 315
Exercises	p. 316
Notes	p. 317
Combinatorics on Bratteli diagrams and dynamical systems	p. 324
Introduction	p. 324
Cantor dynamical systems	p. 325
Bratteli diagrams	p. 325
The Bratteli-Vershik model theorem	p. 330
Examples of BV-models	p. 336
Characterisation of Strong Orbit Equivalence	p. 351
Entropy	p. 357
Invariant measures and Bratteli diagrams	p. 360
Eigenvalues of stationary BV-models	p. 364
Exercises	p. 370
Infinite words with uniform frequencies, and invariant measures	p. 373
Basic notions	p. 374
Invariant measures and unique ergodicity	p. 376
Combinatorial criteria	p. 383
Examples	p. 388
Counter-examples	p. 395
Further afield	p. 405
Exercises	p. 406
Note: Dictionary between word combinatorics and symbolic dynamics	p. 409
Transcendence and Diophantine approximation	p. 410
The expansion of algebraic numbers in an integer base	p. 412
Basics from continued fractions	p. 427
Transcendental continued fractions	p. 430
Simultaneous rational approximations	p. 436
Explicit examples for the Littlewood conjecture	p. 443
Exercises and open problems	p. 448
Notes	p. 449
Analysis of digital functions and applications	p. 452
Introduction: digital functions	p. 452
Asymptotic analysis of digital functions	p. 456
Statistics on digital functions	p. 480
Further results	p. 499
The equality problem for purely substitutive words	p. 505
Purely substitutive words and D0L systems	p. 505
Substitutive words and HD0L sequences	p. 507
Elementary morphisms	p. 509
Nearly primitive D0L systems	p. 512
Periodic and nearly periodic words	p. 515
A balance property for ¿-equivalent 1-systems	p. 519
The equality problem for purely substitutive words	p. 523
Automatic words	p. 525
Complexity questions	p. 526
Exercises	p. 527
Long products of matrices	p. 530
The joint spectral characteristics	p. 531
Applications	p. 541
The finiteness property	p. 550
Approximation algorithms	p. 552
Conclusions	p. 558
Exercises	p. 559
Notes	p. 561
References	p. 563
Notation index	p. 594
General index	p. 599
Table of Contents provided by Ingram. All Rights Reserved.

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Combinatorics, Automata and Number Theory

Summary

Table of Contents

Supplemental Materials