Fixed-point tile sets and their applications

Bruno Durand 1 Andrei Romashchenko 1, * Alexander Shen 1
* Auteur correspondant
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 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. This construction it 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 (any tiling is far from any periodic tiling), to give a new proof for the undecidability of the domino problem and related results, characterize effectively closed 1D subshift it terms of 2D shifts of finite type (improvement of a result by M. Hochman), to construct a tile set which 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.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2012, 78 (3), pp.731-764. 〈10.1016/j.jcss.2011.11.001〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736079
Contributeur : Andrei Romashchenko <>
Soumis le : jeudi 4 décembre 2014 - 12:21:38
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05
Document(s) archivé(s) le : samedi 15 avril 2017 - 04:02:10

Fichier

fpt-arxiv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Bruno Durand, Andrei Romashchenko, Alexander Shen. Fixed-point tile sets and their applications. Journal of Computer and System Sciences, Elsevier, 2012, 78 (3), pp.731-764. 〈10.1016/j.jcss.2011.11.001〉. 〈lirmm-00736079v3〉

Partager

Métriques

Consultations de la notice

63

Téléchargements de fichiers

257