The domino problem is undecidable on every rhombus subshift

DOI10.1007/978-3-031-33264-7_9arXiv2302.12086OpenAlexW4377081604MaRDI QIDQ6067331FDOQ6067331

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

Publication date: 16 November 2023

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

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.

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)

Cites Work

• Theory of computation.
• Aperiodic order. Volume 1. A mathematical invitation
• Title not available (Why is that?)
• Title not available (Why is that?)
• The undecidability of the domino problem
• Tiling a polygon with parallelograms
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Domino Problem for Self-similar Structures
• About the Domino Problem for Subshifts on Groups
• Deceptions in quasicrystal growth
• Domino Problem Under Horizontal Constraints

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)