Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts
From MaRDI portal
Publication:2136854
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
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