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

1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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$.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [17 references]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01793810
Contributor : Andrei Romashchenko Connect in order to contact the contributor
Submitted on : Friday, June 28, 2019 - 12:03:46 PM
Last modification on : Friday, August 5, 2022 - 3:02:59 PM

### File

LIPIcs-STACS-2019-23.pdf
Files produced by the author(s)

### Citation

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⟩

Record views