1 citations · 2 across the 5 of their papers we have counts for
5 papers
Algorithmic tests and randomness with respect to a class of measures
Laurent Bienvenu, Peter Gacs, Mathieu Hoyrup +2
The paper considers quantitative versions of different randomness notions: algorithmic test measures the amount of non-randomness (and is infinite for non-random sequences). We sta…
Kolmogorov complexity as a language
Alexander Shen
The notion of Kolmogorov complexity (=the minimal length of a program that generates some object) is often useful as a kind of language that allows us to reformulate some notions a…
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…
Decomposition Complexity
Alexander Shen
We consider a problem of decomposition of a ternary function into a composition of binary ones from the viewpoint of communication complexity and algorithmic information theory as…
A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
Laurent Bienvenu, Adam Day, Mathieu Hoyrup +2
A theorem of Kučera states that given a Martin-Löf random infinite binary sequence ω and an effectively open set A of measure less than 1, some tail of ω is not in A. We first prov…