The asymptotic repetition threshold of sequences rich in palindromes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917772859015168 |
|---|---|
| author | Dvořáková, Lubomíra Klouda, Karel Pelantová, Edita |
| author_facet | Dvořáková, Lubomíra Klouda, Karel Pelantová, Edita |
| contents | The asymptotic critical exponent measures for a sequence the maximum repetition rate of factors of growing length. The infimum of asymptotic critical exponents of sequences of a certain class is called the asymptotic repetition threshold of that class. On the one hand, if we consider the class of all d-ary sequences with d greater than one, then the asymptotic repetition threshold is equal to one, independently of the alphabet size. On the other hand, for the class of episturmian sequences, the repetition threshold depends on the alphabet size. We focus on rich sequences, i.e., sequences whose factors contain the maximum possible number of distinct palindromes. The class of episturmian sequences forms a subclass of rich sequences. We prove that the asymptotic repetition threshold for the class of rich recurrent d-ary sequences, with d greater than one, is equal to two, independently of the alphabet size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06849 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The asymptotic repetition threshold of sequences rich in palindromes Dvořáková, Lubomíra Klouda, Karel Pelantová, Edita Combinatorics 68R15 The asymptotic critical exponent measures for a sequence the maximum repetition rate of factors of growing length. The infimum of asymptotic critical exponents of sequences of a certain class is called the asymptotic repetition threshold of that class. On the one hand, if we consider the class of all d-ary sequences with d greater than one, then the asymptotic repetition threshold is equal to one, independently of the alphabet size. On the other hand, for the class of episturmian sequences, the repetition threshold depends on the alphabet size. We focus on rich sequences, i.e., sequences whose factors contain the maximum possible number of distinct palindromes. The class of episturmian sequences forms a subclass of rich sequences. We prove that the asymptotic repetition threshold for the class of rich recurrent d-ary sequences, with d greater than one, is equal to two, independently of the alphabet size. |
| title | The asymptotic repetition threshold of sequences rich in palindromes |
| topic | Combinatorics 68R15 |
| url | https://arxiv.org/abs/2409.06849 |