RAIRO - Theoretical Informatics and Applications

Research Article

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

Maurice Margenstern

Université Paul Verlaine - Metz, IUT de Metz; margens@univ-metz.fr


This paper is a contribution to the general tiling problem for the hyperbolic plane. It is an intermediary result between the result obtained by R. Robinson [Invent. Math. 44 (1978) 259–264] and the conjecture that the problem is undecidable.

(Online publication January 18 2008)

Key Words:

  • Tilings;
  • tiling problem;
  • hyperbolic plane;
  • origin-constrained problem

Mathematics Subject Classification:

  • 52C20;
  • 05B45