Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2603.07816 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908873008349184 |
|---|---|
| author | Andrieu, Mélodie |
| author_facet | Andrieu, Mélodie |
| contents | These lecture notes provide an introduction to combinatorics on words and its interactions with dynamics, algebra, and arithmetic. The central theme is the notion of low factor complexity for infinite words. We investigate the following guiding questions: What is the minimal complexity of a non-trivial infinite word over a binary, ternary, or more generally finite alphabet? How should ''non-triviality'' be formalized? Which words achieve this minimal complexity? Are there many? Are they interesting? In exploring these questions, we introduce classical objects and tools from combinatorics on words -- such as Sturmian words and Rauzy graphs -- as well as little-known and new results. In particular, the third chapter is devoted to a theorem by R. Tijdeman from 1999, which generalizes a seminal result of M. Morse and G. Hedlund from 1938. We provide a new, algebraic proof of this theorem (due to J. Cassaigne and the author, 2022) and develop its consequences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_07816 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words Andrieu, Mélodie Combinatorics Dynamical Systems These lecture notes provide an introduction to combinatorics on words and its interactions with dynamics, algebra, and arithmetic. The central theme is the notion of low factor complexity for infinite words. We investigate the following guiding questions: What is the minimal complexity of a non-trivial infinite word over a binary, ternary, or more generally finite alphabet? How should ''non-triviality'' be formalized? Which words achieve this minimal complexity? Are there many? Are they interesting? In exploring these questions, we introduce classical objects and tools from combinatorics on words -- such as Sturmian words and Rauzy graphs -- as well as little-known and new results. In particular, the third chapter is devoted to a theorem by R. Tijdeman from 1999, which generalizes a seminal result of M. Morse and G. Hedlund from 1938. We provide a new, algebraic proof of this theorem (due to J. Cassaigne and the author, 2022) and develop its consequences. |
| title | Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words |
| topic | Combinatorics Dynamical Systems |
| url | https://arxiv.org/abs/2603.07816 |