This project was constructed from a course in combinatorics on words that I am giving for the last ten years at the University of Liège.
The goal is not to have an encyclopedic presentation of the subject, but to familiarize the reader with a series of selected topics on words (words, morphisms, factor complexity, Sturmian words, ...). The philosophy is to rigorously present the concepts being illustrated with many examples (particularly in relations to numeration systems or symbolic dynamics). The reader should be able to quickly gain access to current research problems or attend a conference on the subject. Interactions between combinatorics, arithmetic and automata theory are also highlighted.
The book requires little (or no) prerequisites and thus should be accessible to a wide audience (computer scientists/mathematicians, at Master/graduate level).
The book is published by ISTE-Wiley. The publisher has decided to present my work into two volumes containing three chapters each ISBN: 978-1-84821-615-0 and ISBN: 978-1-84821-788-1.
The first volume can be used for a course in one semester in combinatorics of words (e.g. I give regularly the first two chapters to read to my students, the last one serving as complement for the 'advanced' students). The table of contents and the introduction are available here as a pdf file.
The first chapter of volume 1 (83 pages), the index and table of contents are available online (follow the link 'Read Excerpt' on the editor's website).
Volume 1Chapter 1. Words and Sequences From Scratch
- Mathematical Background and Notation
- Structures, Words and Languages
- Examples of Infinite Words
- Bibliographic Notes and Comments
- Formal Definitions
- Parikh Vectors and Matrices Associated with a Morphism
- Constant-Length Morphisms
- Primitive Morphisms
- Arbitrary Morphisms
- Factor Complexity and Sturmian Words
- Exercises
- Bibliographic Notes and Comments
- Getting Rid of Erasing Morphisms
- Recurrence
- More Examples of Infinite Words
- Factor Graphs and Special Factors
- From the Thue-Morse Word to Pattern Avoidance
- Other Combinatorial Complexity Measures
- Bibliographic Notes and Comments
The second volume develops interactions with numeration systems and automata. Thus, automatic sequences and some of their generalizations are described in detail. It also presents many non-standard numeration systems. The last chapter deals with 'automatic' proofs in combinatorics on words. Thus, it explains how, based on a celebrated theorem of Büchi, some combinatorial properties, e.g., occurrence of a repetition, of infinite words (such as automatic sequences or Fibonacci word) can be certified algorithmically. This challenging topic is of interest both for mathematicians and computer scientists.
The first chapter of volume 2 (54 pages), the index and table of contents are available online (follow the link 'Read Excerpt' on the editor's website).
Volume 2Chapter 1. Crash Course on Regular Languages
- Automata and Regular Languages
- Adjacency Matrix
- Multi-Dimensional Alphabet
- Two Pumping Lemmas
- The Minimal Automaton
- Some Operations Preserving Regularity
- Links with Automatic Sequences and Recognizable Sets
- Polynomial Regular Languages
- Bibliographic Notes and Comments
- Substitutive Systems
- Abstract Numeration Systems
- Positional Numeration Systems
- Pisot Numeration Systems
- Back to beta-Expansions
- Miscellaneous Systems
- Bibliographical Notes and Comments
- A Glimpse at Mathematical Logic
- Decision Problems and Decidability
- Quantifier Elimination in Presburger Arithmetic
- Büchi's Theorem
- Some Applications
- Bibliographic Notes and Comments
Last modified: Thu Nov 27 17:07:03 CET 2014