THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE

DOI10.1142/S0129054108006078MaRDI QIDQ3526546zbMATH OpenOpenAlexFDO

Authors M. Margenstern

Publication date 25 September 2008

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054108006078

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• The domino problem of the hyperbolic plane is undecidable
• The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane
• Undecidable tiling problems in the hyperbolic plane
• The Tiling Problem Revisited (Extended Abstract)
• About the domino problem in the hyperbolic plane from an algorithmic point of view

Cites work

• Automata theory: Its past and future
• Cellular automata in hyperbolic spaces. Vol 1: Theory
• Reversibility and surjectivity problems of cellular automata
• The Tiling Problem Revisited (Extended Abstract)
• Undecidability and nonperiodicity for tilings of the plane
• Undecidable tiling problems in the hyperbolic plane

Cited in

(11)

• scientific article; zbMATH DE number 1421183 (Why is no real title available?)
• Hyperbolic regular polygons with notched edges
• The domino problem of the hyperbolic plane is undecidable
• Undecidable tiling problems in the hyperbolic plane
• About the domino problem in the hyperbolic plane from an algorithmic point of view
• The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane
• The Injectivity of the Global Function of a Cellular Automaton in the Hyperbolic Plane is Undecidable
• Constructing a uniform plane-filling path in the ternary heptagrid of the hyperbolic plane
• The Tiling Problem Revisited (Extended Abstract)
• The Heesch number for multiple prototiles is unbounded
• On the Undecidability of the Tiling Problem

This page was built for publication: THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE

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