About the domino problem in the hyperbolic plane from an algorithmic point of view

DOI10.1051/ITA:2007045MaRDI QIDQ3514632zbMATH OpenOpenAlexFDO

Authors M. Margenstern

Publication date 21 July 2008

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0603093, https://eudml.org/doc/92861

zbMATH Keywords

hyperbolic planeorigin-constrained problemtiling problemtilings

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45) Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Cellular automata (computational aspects) (68Q80)

Abstract: In this paper, we prove that the general problem of tiling the hyperbolic plane with `a la Wang tiles is undecidable.

Recommendations

• The domino problem of the hyperbolic plane is undecidable
• The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane
• The Tiling Problem Revisited (Extended Abstract)
• Undecidable tiling problems in the hyperbolic plane
• THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE

Cites work

• A strongly aperiodic set of tiles in the hyperbolic plane
• Cellular automata in hyperbolic spaces. Vol 1: Theory
• scientific article; zbMATH DE number 5605129 (Why is no real title available?)
• New tools for cellular automata in the hyperbolic plane
• The undecidability of the domino problem
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(9)

• Undecidable tiling problems in the hyperbolic plane
• An algorithmic approach to tilings of hyperbolic spaces: universality results
• An algorithmic approach to tilings of hyperbolic spaces: 10 years later
• THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE
• The Tiling Problem Revisited (Extended Abstract)
• The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane
• Domino Problem Under Horizontal Constraints
• A heuristic approach to domino grid problem
• The domino problem of the hyperbolic plane is undecidable

This page was built for publication: About the domino problem in the hyperbolic plane from an algorithmic point of view

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