Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints
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_ | 1866915529279668224 |
|---|---|
| author | Callard, Antonin Salomon, Léo Paviet Vanier, Pascal |
| author_facet | Callard, Antonin Salomon, Léo Paviet Vanier, Pascal |
| contents | Subshifts are sets of colorings of $\mathbb{Z}^d$ defined by families of forbidden patterns. In a given subshift, the extender set of a finite pattern is the set of all its admissible completions. Since soficity of $\mathbb{Z}$ subshifts is equivalent to having a finite number of extender sets, it had been conjectured that the number of extender sets could provide a way to separate the classes of sofic and effective subshifts in higher dimensions. We investigate some computational characterizations of extender sets in multidimensional subshifts, and in particular their growth, in terms of extender entropies (arXiv:1711.07515) and extender entropy dimensions. We prove here that sofic and effective subshifts have the same possible extender entropies (exactly the $Π_3$-computable real numbers of $[0,+\infty)$) and extender entropy dimensions, and investigate the computational complexity of these growth-type quantities under various dynamical and combinatorial constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_07549 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints Callard, Antonin Salomon, Léo Paviet Vanier, Pascal Discrete Mathematics Computational Complexity Logic in Computer Science Dynamical Systems Subshifts are sets of colorings of $\mathbb{Z}^d$ defined by families of forbidden patterns. In a given subshift, the extender set of a finite pattern is the set of all its admissible completions. Since soficity of $\mathbb{Z}$ subshifts is equivalent to having a finite number of extender sets, it had been conjectured that the number of extender sets could provide a way to separate the classes of sofic and effective subshifts in higher dimensions. We investigate some computational characterizations of extender sets in multidimensional subshifts, and in particular their growth, in terms of extender entropies (arXiv:1711.07515) and extender entropy dimensions. We prove here that sofic and effective subshifts have the same possible extender entropies (exactly the $Π_3$-computable real numbers of $[0,+\infty)$) and extender entropy dimensions, and investigate the computational complexity of these growth-type quantities under various dynamical and combinatorial constraints. |
| title | Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints |
| topic | Discrete Mathematics Computational Complexity Logic in Computer Science Dynamical Systems |
| url | https://arxiv.org/abs/2401.07549 |