RAIRO - Theoretical Informatics and Applications

Table of Contents - January 2008 - Volume 42, Issue 01 (A nonstandard spirit among computer scientists:a tribute to Serge Grigorieff at the occasion of his 60th birthday)  

Research Article

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

Margenstern, Maurice

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

Abstract

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