Undecidable tiling problems in the hyperbolic plane

DOI10.1007/BF01403163zbMath0354.50006OpenAlexW2013120724MaRDI QIDQ1236791

Raphael M. Robinson

Publication date: 1978

Published in: Inventiones Mathematicae (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/142530

Mathematics Subject Classification ID

Hyperbolic and elliptic geometries (general) and generalizations (51M10) Undecidability and degrees of sets of sentences (03D35) Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items

The Domino Problem for Self-similar Structures ⋮ Strongly aperiodic subshifts of finite type on hyperbolic groups ⋮ A universal cellular automaton in the hyperbolic plane. ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE ⋮ About the Domino Problem for Subshifts on Groups ⋮ A notion of effectiveness for subshifts on finitely generated groups ⋮ The domino problem of the hyperbolic plane is undecidable ⋮ NP problems are tractable in the space of cellular automata in the hyperbolic plane ⋮ A hierarchical strongly aperiodic set of tiles in the hyperbolic plane ⋮ Regular production systems and triangle tilings ⋮ The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane ⋮ Frontier between decidability and undecidability: A survey

Cites Work

• Nonrecursive tilings of the plane. I
• Nonrecursive tilings of the plane. II
• The undecidability of the domino problem