Arithmetical subword complexity of automatic sequences
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910320425959424 |
|---|---|
| author | Konieczny, Jakub Müllner, Clemens |
| author_facet | Konieczny, Jakub Müllner, Clemens |
| contents | We fully classify automatic sequences $a$ over a finite alphabet $Ω$ with the property that each word over $Ω$ appears is $a$ along an arithmetic progression. Using the terminology introduced by Avgustinovich, Fon-Der-Flaass and Frid, these are the automatic sequences with the maximal possible arithmetical subword complexity. More generally, we obtain an asymptotic formula for arithmetical (and even polynomial) subword complexity of a given automatic sequence $a$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_03180 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Arithmetical subword complexity of automatic sequences Konieczny, Jakub Müllner, Clemens Number Theory Formal Languages and Automata Theory Combinatorics We fully classify automatic sequences $a$ over a finite alphabet $Ω$ with the property that each word over $Ω$ appears is $a$ along an arithmetic progression. Using the terminology introduced by Avgustinovich, Fon-Der-Flaass and Frid, these are the automatic sequences with the maximal possible arithmetical subword complexity. More generally, we obtain an asymptotic formula for arithmetical (and even polynomial) subword complexity of a given automatic sequence $a$. |
| title | Arithmetical subword complexity of automatic sequences |
| topic | Number Theory Formal Languages and Automata Theory Combinatorics |
| url | https://arxiv.org/abs/2309.03180 |