Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
Résumé
We propose necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity. Using this technique we provide examples of effective and non-sofic shifts on $\mathbb{Z}^2$ with very low block complexity: the number of admissible patterns of size $n\times n$ grows only as a polynomial in $n$.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|---|
| Licence |
Loading...