Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Journal of Computer and System Sciences Année : 2022

Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts

Résumé

We suggest necessary conditions of soficness of multidimensional shifts formulated in termsof resource-bounded Kolmogorov complexity. Using this technique we provide examples ofeffective and non-sofic shifts on $\mathbb{Z}^2$ with very low block complexity: the number of globally admissible patterns of size $n\times n$ grows only as a polynomial in $n$. We also show that more conventional proofs of non-soficness for multi-dimensional effective shifts can be expressed interms of Kolmogorov complexity with unbounded computational resources. We also show that more conventional proofs of non-soficness for multi-dimensional effective shifts, including the techniques of Pavlov [Proc. AMS, 141(3):987-996, 2013] and Kass and Madden [Proc. AMS, 141(11):3803-3816, 2013], can be expressed in terms of Kolmogorov complexity with unbounded computational resources.
Fichier principal
Vignette du fichier
1805.03929.pdf (699.15 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-03646717 , version 1 (11-10-2023)

Identifiants

Citer

Julien Destombes, Andrei Romashchenko. Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts. Journal of Computer and System Sciences, 2022, 128, pp.107-134. ⟨10.1016/j.jcss.2022.04.002⟩. ⟨lirmm-03646717⟩
229 Consultations
7 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More