All reports by Author Bruno Durand:

__
TR08-030
| 16th November 2007
__

Bruno Durand, Alexander Shen, Andrei Romashchenko#### Fixed Point and Aperiodic Tilings

__
TR01-087
| 29th October 2001
__

Bruno Durand, Alexander Shen, Nikolay Vereshchagin#### Descriptive complexity of computable sequences

Bruno Durand, Alexander Shen, Andrei Romashchenko

An aperiodic tile set was first constructed by R.Berger while

proving the undecidability of the domino problem. It turned out

that aperiodic tile sets appear in many topics ranging from

logic (the Entscheidungsproblem) to physics (quasicrystals)

We present a new construction of an aperiodic tile set. The

flexibility of this ...
more >>>

Bruno Durand, Alexander Shen, Nikolay Vereshchagin

We study different notions of descriptive complexity of

computable sequences. Our main result states that if for almost all

n the Kolmogorov complexity of the n-prefix of an infinite

binary sequence x conditional to n

is less than m then there is a program of length

m^2+O(1) that for ...
more >>>