1 citations · 1 across the 3 of their papers we have counts for
4 papers
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…
The axiomatic power of Kolmogorov complexity
Laurent Bienvenu, Andrei Romashchenko, Alexander Shen +2
The famous Gödel incompleteness theorem states that for every consistent sufficiently rich formal theory T there exist true statements that are unprovable in T. Such statements wo…
On the Non-robustness of Essentially Conditional Information Inequalities
Tarik Kaced, Andrei Romashchenko
We show that two essentially conditional linear inequalities for Shannon's entropies (including the Zhang-Yeung'97 conditional inequality) do not hold for asymptotically entropic p…
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…