Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts

DOI10.1016/J.JCSS.2022.04.002OpenAlexW2802845120MaRDI QIDQ2136854

Julien Destombes, Andrei Romashchenko

Publication date: 16 May 2022

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2022.04.002

zbMATH Keywords

Kolmogorov complexitysymbolic dynamicssofic shifts

Mathematics Subject Classification ID

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

Cites Work

• On the dynamics and recursive properties of multidimensional symbolic systems
• Tilings, substitution systems and dynamical systems generated by them
• Subshifts of finite type and sofic systems
• Extender sets and multidimensional subshifts
• A sufficient condition for non-soficness of higher-dimensional subshifts
• Complex tilings
• Kolmogorov Complexity and Algorithmic Randomness
• About the Domino Problem for Subshifts on Groups
• An Introduction to Symbolic Dynamics and Coding
• A class of nonsofic multidimensional shift spaces
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• Two-Tape Simulation of Multitape Turing Machines
• An introduction to Kolmogorov complexity and its applications
• Unnamed Item
• Unnamed Item

This page was built for publication: Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts