The domino problem of the hyperbolic plane is undecidable

DOI10.1016/j.tcs.2008.04.038zbMath1152.03036OpenAlexW1998113811MaRDI QIDQ954981

Maurice Margenstern

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.04.038

zbMATH Keywords

undecidabilitytilingshyperbolic geometry

Mathematics Subject Classification ID

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

Related Items (9)

A universal cellular automaton on the heptagrid of the hyperbolic plane with four states ⋮ Monadic second-order logic and the domino problem on self-similar graphs ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ A hierarchical strongly aperiodic set of tiles in the hyperbolic plane ⋮ Unnamed Item ⋮ About the Garden of Eden Theorems for Cellular Automata in the Hyperbolic Plane ⋮ Regular production systems and triangle tilings ⋮ The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane ⋮ A strongly aperiodic shift of finite type on the discrete Heisenberg group using Robinson tilings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly aperiodic set of tiles in the hyperbolic plane
• Undecidable tiling problems in the hyperbolic plane
• Undecidability and nonperiodicity for tilings of the plane
• About the domino problem in the hyperbolic plane from an algorithmic point of view
• The Tiling Problem Revisited (Extended Abstract)
• Nonrecursive tilings of the plane. I
• Nonrecursive tilings of the plane. II
• Heesch's Tiling Problem
• Cellular Automata in the Hyperbolic Plane: Proposal for a New Environment
• The undecidability of the domino problem
• On Computable Numbers, with an Application to the Entscheidungsproblem

This page was built for publication: The domino problem of the hyperbolic plane is undecidable