Computer Science – Computational Complexity
Scientific paper
2008-02-18
12th International Conference on Developments in Language Theory, Kyoto : Japan (2008)
Computer Science
Computational Complexity
v5: technical revision (positions of figures are shifted)
Scientific paper
10.1007/978-3-540-85780-8_22
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 that is based on Kleene's fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann self-reproducing automata; similar ideas were also used by P. Gacs in the context of error-correcting computations. The flexibility of this construction allows us to construct a "robust" aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. This property was not known for any of the existing aperiodic tile sets.
Durand Bruno
Romashchenko Andrei
Shen Alexander
No associations
LandOfFree
Fixed Point and Aperiodic Tilings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fixed Point and Aperiodic Tilings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fixed Point and Aperiodic Tilings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-197498