The domino problem is undecidable on every rhombus subshift

DOI10.1007/978-3-031-33264-7_9MaRDI QIDQ6067331zbMATH OpenOpenAlexFDO

Authors Benjamin Hellouin de Menibus, Victor H. Lutfalla, Camille Noûs

Publication date 16 November 2023

Published in Developments in Language Theory (Search for Journal in Brave)

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

zbMATH Keywords

decidabilityrhombus tilingDomino problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We extend the classical Domino problem to any tiling of rhombus-shaped tiles. For any subshift X of edge-to-edge rhombus tilings, such as the Penrose subshift, we prove that the associated X-Domino problem is $P{i}_1^0$ -hard and therefore undecidable. It is $P{i}_1^0$ -complete when the subshift X is given by a computable sequence of forbidden patterns.

Cites work

• scientific article; zbMATH DE number 3968590 (Why is no real title available?)
• scientific article; zbMATH DE number 3715591 (Why is no real title available?)
• scientific article; zbMATH DE number 2158946 (Why is no real title available?)
• scientific article; zbMATH DE number 768067 (Why is no real title available?)
• About the domino problem for subshifts on groups
• Aperiodic order. Volume 1. A mathematical invitation
• Deceptions in quasicrystal growth
• Domino Problem Under Horizontal Constraints
• The domino problem for self-similar structures
• The undecidability of the domino problem
• Theory of computation.
• Tiling a polygon with parallelograms

Cited in

(1)

• The domino problem of the hyperbolic plane is undecidable

This page was built for publication: The domino problem is undecidable on every rhombus subshift

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6067331)