You are previewing Combinatorics, Automata and Number Theory.
O'Reilly logo
Combinatorics, Automata and Number Theory

Book Description

This collaborative 2010 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.

Table of Contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright
  5. Contents
  6. List of contributors
  7. Preface
  8. Acknowledgements
  9. 1. Preliminaries
    1. 1.1. Conventions
    2. 1.2. Words
    3. 1.3. Languages and machines
    4. 1.4. Associated matrices
    5. 1.5. A glimpse at numeration systems
    6. 1.6. Symbolic dynamics
    7. 1.7. Exercises
    8. 1.8. Notes
  10. 2. Number representation and finite automata
    1. 2.1. Introduction
    2. 2.2. Representation in integer base
    3. 2.3. Representation in real base
    4. 2.4. Canonical numeration systems
    5. 2.5. Representation in rational base
    6. 2.6. A primer on finite automata and transducers
    7. 2.7. Notes
  11. 3. Abstract numeration systems
    1. 3.1. Motivations
    2. 3.2. Computing numerical values and S-representations
    3. 3.3. S-recognisable sets
    4. 3.4. Automatic sequences
    5. 3.5. Representing real numbers
    6. 3.6. Exercises and open problems
    7. 3.7. Notes
  12. 4. Factor complexity
    1. 4.1. Introduction
    2. 4.2. Definitions, basic properties, and first examples
    3. 4.3. The theorem of Morse and Hedlund
    4. 4.4. High complexity
    5. 4.5. Tools for low complexity
    6. 4.6. Morphisms and complexity
    7. 4.7. The theorem of Pansiot
    8. 4.8. Complexity of automatic words
    9. 4.9. Control of bispecial factors
    10. 4.10. Examples of complexity computations for morphic words
    11. 4.11. Complexity computation for an s-adic family of words
    12. 4.12. Exercises and open problems
  13. 5. Substitutions, Rauzy fractals and tilings
    1. 5.1. Introduction
    2. 5.2. Basic definitions
    3. 5.3. Tilings
    4. 5.4. Ancestor graphs and tiling conditions
    5. 5.5. Boundary and contact graphs
    6. 5.6. Geometric coincidences
    7. 5.7. Overlap coincidences
    8. 5.8. Balanced pair algorithm
    9. 5.9. Conclusion
    10. 5.10. Exercises
    11. 5.11. Notes
  14. 6. Combinatorics on Bratteli diagrams and dynamical systems
    1. 6.1. Introduction
    2. 6.2. Cantor dynamical systems
    3. 6.3. Bratteli diagrams
    4. 6.4. The Bratteli-Vershik model theorem
    5. 6.5. Examples of BV-models
    6. 6.6. Characterisation of Strong Orbit Equivalence
    7. 6.7. Entropy
    8. 6.8. Invariant measures and Bratteli diagrams
    9. 6.9. Eigenvalues of stationary BV-models
    10. 6.10. Exercises
  15. 7. Infinite words with uniform frequencies, and invariant measures
    1. 7.1. Basic notions
    2. 7.2. Invariant measures and unique ergodicity
    3. 7.3. Combinatorial criteria
    4. 7.4. Examples
    5. 7.5. Counter-examples
    6. 7.6. Further afield
    7. 7.7. Exercises
    8. 7.8. Note: Dictionary between word combinatorics and symbolic dynamics
  16. 8. Transcendence and Diophantine approximation
    1. 8.1 The expansion of algebraic numbers in an integer base
    2. 8.2. Basics from continued fractions
    3. 8.3. Transcendental continued fractions
    4. 8.4. Simultaneous rational approximations
    5. 8.5. Explicit examples for the Littlewood conjecture
    6. 8.6. Exercises and open problems
    7. 8.7. Notes
  17. 9. Analysis of digital functions and applications
    1. 9.1. Introduction: digital functions
    2. 9.2. Asymptotic analysis of digital functions
    3. 9.3. Statistics on digital functions
    4. 9.4. Further results
  18. 10. The equality problem for purely substitutive words
    1. 10.1. Purely substitutive words and D0L systems
    2. 10.2. Substitutive words and HD0L sequences
    3. 10.3. Elementary morphisms
    4. 10.4. Nearly primitive D0L systems
    5. 10.5. Periodic and nearly periodic words
    6. 10.6. A balance property for ω-equivalent 1-systems
    7. 10.7. The equality problem for purely substitutive words
    8. 10.8. Automatic words
    9. 10.9. Complexity questions
    10. 10.10. Exercises
  19. 11. Long products of matrices
    1. 11.1. The joint spectral characteristics
    2. 11.2. Applications
    3. 11.3. The finiteness property
    4. 11.4. Approximation algorithms
    5. 11.5. Conclusions
    6. 11.6. Exercises
    7. 11.7. Notes
  20. References
  21. Notation index
  22. General index