21 citations · 60 across the 30 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.CC2009★ 7 cited
Fixed-point tile sets and their applications
Bruno Durand, Andrei Romashchenko, Alexander Shen
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 rangin…
cs.CC2009
Variations on Muchnik's Conditional Complexity Theorem
Daniil Musatov, Andrei Romashchenko, Alexander Shen
Muchnik's theorem about simple conditional descriptions states that for all strings and there exists a short program transforming to that has the least possible…