Quasiperiodicity and Non-computability in Tilings

DOI10.1007/978-3-662-48057-1_17zbMath1465.68085arXiv1504.06130OpenAlexW2964121629MaRDI QIDQ2946338

Andrei Romashchenko, Bruno Durand

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.06130

zbMATH Keywords

fixed pointquasiperiodicitytilingcomputabilityWang tiles

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Quasicrystals and aperiodic tilings in discrete geometry (52C23) Other Turing degree structures (03D28) Other nonclassical models of computation (68Q09)

Related Items (2)

The expressiveness of quasiperiodic and minimal shifts of finite type ⋮ On the Expressive Power of Quasiperiodic SFT.

Cites Work

• Unnamed Item
• Unnamed Item
• Turing degrees of multidimensional SFTs
• Fixed-point tile sets and their applications
• Upcrossing inequalities for stationary sequences and applications
• Tilings and quasiperiodicity.
• Turing degree spectra of minimal subshifts
• Undecidability and nonperiodicity for tilings of the plane
• $\it \Pi^0_1$ Sets and Tilings
• Complex tilings
• Two-by-Two Substitution Systems and the Undecidability of the Domino Problem
• Nonrecursive tilings of the plane. I
• Nonrecursive tilings of the plane. II
• The undecidability of the domino problem
• The classical decision problem.

This page was built for publication: Quasiperiodicity and Non-computability in Tilings