首页 | 本学科首页   官方微博 | 高级检索  
     


Fixed-point tile sets and their applications
Authors:Bruno Durand  Andrei Romashchenko  Alexander Shen
Affiliation:Laboratoire d?Informatique Fondamentale de Marseille, CNRS & Univ. Aix–Marseille, France
Abstract: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 fields, 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?s self-reproducing automata; similar ideas were also used by P. Gács in the context of error-correcting computations. This construction is rather flexible, so it can be used in many ways. We show how it can be used to implement substitution rules, to construct strongly aperiodic tile sets (in which any tiling is far from any periodic tiling), to give a new proof for the undecidability of the domino problem and related results, to characterize effectively closed one-dimensional subshifts in terms of two-dimensional subshifts of finite type (an improvement of a result by M. Hochman), to construct a tile set that has only complex tilings, and 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. For the latter, we develop a hierarchical classification of points in random sets into islands of different ranks. Finally, we combine and modify our tools to prove our main result: There exists a tile set such that all tilings have high Kolmogorov complexity even if (sparse enough) tiling errors are allowed. Some of these results were included in the DLT extended abstract (Durand et al., 2008 9]) and in the ICALP extended abstract (Durand et al., 2009 10]).
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号