Quasiperiodicity and non-computability in tilings

Bruno Durand 1 Andrei Romashchenko 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We study tilings of the plane that combine strong properties of different nature: combinatorial and algorithmic. We prove existence of a tile set that accepts only quasiperiodic and non-recursive tilings. Our construction is based on the fixed point construction; we improve this general technique and make it enforce the property of local regularity of tilings needed for quasiperiodicity. We prove also a stronger result: any effectively closed set can be recursively transformed into a tile set so that the Turing degrees of the resulted tilings consists exactly of the upper cone based on the Turing degrees of the later.
Type de document :
Communication dans un congrès
MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. MFCS'2015: 40th International Symposium on Mathematical Foundations of Computer Science, 2015, 〈http://mfcs2015.di.unimi.it〉. 〈10.1007/978-3-662-48057-1_17〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01165314
Contributeur : Andrei Romashchenko <>
Soumis le : jeudi 18 juin 2015 - 17:51:40
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05

Identifiants

Collections

Citation

Bruno Durand, Andrei Romashchenko. Quasiperiodicity and non-computability in tilings. MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. MFCS'2015: 40th International Symposium on Mathematical Foundations of Computer Science, 2015, 〈http://mfcs2015.di.unimi.it〉. 〈10.1007/978-3-662-48057-1_17〉. 〈lirmm-01165314〉

Partager

Métriques

Consultations de la notice

55