Parametrized complexity of relations between multidimensional subshifts
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910021344821248 |
|---|---|
| author | Carrasco-Vargas, Nicanor de Menibus, Benjamin Hellouin Pallen, Rémi |
| author_facet | Carrasco-Vargas, Nicanor de Menibus, Benjamin Hellouin Pallen, Rémi |
| contents | We study the parametrized complexity of fundamental relations between multidimensional subshifts, such as equality, conjugacy, inclusion, and embedding, for subshifts of finite type (SFTs) and effective subshifts. We build on previous work of E. Jeandel and P. Vanier on the complexity of these relations as two-input problems, by fixing one subshift as parameter and taking the other subshift as input. We study the impact of various dynamical properties related to periodicity, minimality, finite type, etc. on the computational properties of the parameter subshift, which reveals interesting differences and asymmetries.
Among other notable results, we find choices of parameter that reach the maximum difficulty for each problem; we find nontrivial decidable problems for multidimensional SFT, where most properties are undecidable; and we find connections with recent work relating having computable language and being minimal for some property, showing in particular that this property may not always be chosen conjugacy-invariant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24343 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parametrized complexity of relations between multidimensional subshifts Carrasco-Vargas, Nicanor de Menibus, Benjamin Hellouin Pallen, Rémi Dynamical Systems Information Theory Logic 37B10, 68Q15, 03D05 We study the parametrized complexity of fundamental relations between multidimensional subshifts, such as equality, conjugacy, inclusion, and embedding, for subshifts of finite type (SFTs) and effective subshifts. We build on previous work of E. Jeandel and P. Vanier on the complexity of these relations as two-input problems, by fixing one subshift as parameter and taking the other subshift as input. We study the impact of various dynamical properties related to periodicity, minimality, finite type, etc. on the computational properties of the parameter subshift, which reveals interesting differences and asymmetries. Among other notable results, we find choices of parameter that reach the maximum difficulty for each problem; we find nontrivial decidable problems for multidimensional SFT, where most properties are undecidable; and we find connections with recent work relating having computable language and being minimal for some property, showing in particular that this property may not always be chosen conjugacy-invariant. |
| title | Parametrized complexity of relations between multidimensional subshifts |
| topic | Dynamical Systems Information Theory Logic 37B10, 68Q15, 03D05 |
| url | https://arxiv.org/abs/2509.24343 |