Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2019

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

Abstract

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$.
Fichier principal
Vignette du fichier
LIPIcs-STACS-2019-23.pdf (535 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01793810 , version 1 (28-06-2019)

Licence

Identifiers

Cite

Andrei Romashchenko, Julien Destombes. Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts. STACS 2019 - 36th International Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.23:1--23:17, ⟨10.4230/LIPIcs.STACS.2019.23⟩. ⟨lirmm-01793810⟩
237 View
69 Download

Altmetric

Share

More