Skip to Main content Skip to Navigation
Conference papers

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

Andrei Romashchenko 1 Julien Destombes 1
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$.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01793810
Contributor : Andrei Romashchenko <>
Submitted on : Friday, June 28, 2019 - 12:03:46 PM
Last modification on : Wednesday, May 13, 2020 - 3:02:09 PM

File

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

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

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

Share

Metrics