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

DOI10.4230/LIPICS.STACS.2019.23zbMath1503.68081arXiv1805.03929OpenAlexW2963959716MaRDI QIDQ5090471

Julien Destombes, Andrei Romashchenko

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1805.03929

zbMATH Keywords

Kolmogorov complexitysofic shiftsblock complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Multidimensional shifts of finite type (37B51)

Cites Work

• Tilings, substitution systems and dynamical systems generated by them
• Extender sets and multidimensional subshifts
• A sufficient condition for non-soficness of higher-dimensional subshifts
• Complex tilings
• About the Domino Problem for Subshifts on Groups
• An Introduction to Symbolic Dynamics and Coding
• A class of nonsofic multidimensional shift spaces
• Two-Tape Simulation of Multitape Turing Machines
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts