On the complexity of subshifts and infinite words
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918145970667520 |
|---|---|
| author | Greenfeld, Be'eri Moreira, Carlos Gustavo Zelmanov, Efim |
| author_facet | Greenfeld, Be'eri Moreira, Carlos Gustavo Zelmanov, Efim |
| contents | We characterize the complexity functions of subshifts up to asymptotic equivalence. The complexity function of every aperiodic function is non-decreasing, submultiplicative and grows at least linearly. We prove that conversely, every function satisfying these conditions is asymptotically equivalent to the complexity function of a recurrent subshift, equivalently, a recurrent infinite word. Our construction is explicit, algorithmic in nature and is philosophically based on constructing certain 'Cantor sets of integers', whose 'gaps' correspond to blocks of zeros. We also prove that every non-decreasing submultiplicative function is asymptotically equivalent, up a linear error term, to the complexity function of a minimal subshift. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_03403 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the complexity of subshifts and infinite words Greenfeld, Be'eri Moreira, Carlos Gustavo Zelmanov, Efim Dynamical Systems Combinatorics Rings and Algebras We characterize the complexity functions of subshifts up to asymptotic equivalence. The complexity function of every aperiodic function is non-decreasing, submultiplicative and grows at least linearly. We prove that conversely, every function satisfying these conditions is asymptotically equivalent to the complexity function of a recurrent subshift, equivalently, a recurrent infinite word. Our construction is explicit, algorithmic in nature and is philosophically based on constructing certain 'Cantor sets of integers', whose 'gaps' correspond to blocks of zeros. We also prove that every non-decreasing submultiplicative function is asymptotically equivalent, up a linear error term, to the complexity function of a minimal subshift. |
| title | On the complexity of subshifts and infinite words |
| topic | Dynamical Systems Combinatorics Rings and Algebras |
| url | https://arxiv.org/abs/2408.03403 |