Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Andrei Romashchenko <>
Submitted on : Thursday, June 18, 2015 - 5:51:40 PM
Last modification on : Wednesday, May 19, 2021 - 12:38:01 PM

Links full text




Bruno Durand, Andrei Romashchenko. Quasiperiodicity and non-computability in tilings. MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. pp.218-230, ⟨10.1007/978-3-662-48057-1_17⟩. ⟨lirmm-01165314⟩



Record views