21 citations · 60 across the 30 of their papers we have counts for
6 papers · 1 filter
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
Julien Destombes, Andrei Romashchenko
We suggest necessary conditions of soficness of multidimensional shifts formulated in termsof resource-bounded Kolmogorov complexity. Using this technique we provide examples ofeff…
The expressiveness of quasiperiodic and minimal shifts of finite type
Bruno Durand, Andrei Romashchenko
We study multidimensional minimal and quasiperiodic shifts of finite type. We prove for these classes several results that were previously known for the shifts of finite type in ge…
On the expressive power of quasiperiodic SFT
Bruno Durand, Andrei Romashchenko
In this paper we study the shifts, which are the shift-invariant and topologically closed sets of configurations over a finite alphabet in . The minimal shifts are th…
Quasiperiodicity and non-computability in tilings
Bruno Durand, Andrei Romashchenko
We study tilings of the plane that combine strong properties of different nature: combinatorial and algorithmic. We prove existence of a tile set that accepts only quasiperiodic an…
Topological arguments for Kolmogorov complexity
Alexander Shen, Andrei Romashchenko
We present several application of simple topological arguments in problems of Kolmogorov complexity. Basically we use the standard fact from topology that the disk is simply connec…
1D Effectively Closed Subshifts and 2D Tilings
Durand Bruno, Alexander Shen, Andrei Romashchenko
Michael Hochman showed that every 1D effectively closed subshift can be simulated by a 3D subshift of finite type and asked whether the same can be done in 2D. It turned out that t…