The repetition threshold for ternary rich words
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908387017490432 |
|---|---|
| author | Currie, James D. Mol, Lucas Peltomäki, Jarkko |
| author_facet | Currie, James D. Mol, Lucas Peltomäki, Jarkko |
| contents | In 2017, Vesti proposed the problem of determining the repetition threshold for infinite rich words, i.e., for infinite words in which all factors of length $n$ contain $n$ distinct nonempty palindromic factors. In 2020, Currie, Mol, and Rampersad proved a conjecture of Baranwal and Shallit that the repetition threshold for binary rich words is $2 + \sqrt{2}/2$. In this paper, we prove a structure theorem for $16/7$-power-free ternary rich words. Using the structure theorem, we deduce that the repetition threshold for ternary rich words is $1 + 1/(3 - μ) \approx 2.25876324$, where $μ$ is the unique real root of the polynomial $x^3 - 2x^2 - 1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_12068 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The repetition threshold for ternary rich words Currie, James D. Mol, Lucas Peltomäki, Jarkko Combinatorics Discrete Mathematics Formal Languages and Automata Theory 68R15 In 2017, Vesti proposed the problem of determining the repetition threshold for infinite rich words, i.e., for infinite words in which all factors of length $n$ contain $n$ distinct nonempty palindromic factors. In 2020, Currie, Mol, and Rampersad proved a conjecture of Baranwal and Shallit that the repetition threshold for binary rich words is $2 + \sqrt{2}/2$. In this paper, we prove a structure theorem for $16/7$-power-free ternary rich words. Using the structure theorem, we deduce that the repetition threshold for ternary rich words is $1 + 1/(3 - μ) \approx 2.25876324$, where $μ$ is the unique real root of the polynomial $x^3 - 2x^2 - 1$. |
| title | The repetition threshold for ternary rich words |
| topic | Combinatorics Discrete Mathematics Formal Languages and Automata Theory 68R15 |
| url | https://arxiv.org/abs/2409.12068 |