On asymptotically automatic sequences
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911835145371648 |
|---|---|
| author | Konieczny, Jakub |
| author_facet | Konieczny, Jakub |
| contents | We study the notion of an asymptotically automatic sequence, which generalises the notion of an automatic sequence. While $k$-automatic sequences are characterised by finiteness of $k$-kernels, the $k$-kernels of asymptotically $k$-automatic sequences are only required to be finite up to equality almost everywhere. We prove basic closure properties and a linear bound on asymptotic subword complexity, show that results concerning frequencies of symbols are no longer true for the asymptotic analogue, and discuss some classification problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_09885 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On asymptotically automatic sequences Konieczny, Jakub Number Theory Formal Languages and Automata Theory Combinatorics We study the notion of an asymptotically automatic sequence, which generalises the notion of an automatic sequence. While $k$-automatic sequences are characterised by finiteness of $k$-kernels, the $k$-kernels of asymptotically $k$-automatic sequences are only required to be finite up to equality almost everywhere. We prove basic closure properties and a linear bound on asymptotic subword complexity, show that results concerning frequencies of symbols are no longer true for the asymptotic analogue, and discuss some classification problems. |
| title | On asymptotically automatic sequences |
| topic | Number Theory Formal Languages and Automata Theory Combinatorics |
| url | https://arxiv.org/abs/2305.09885 |