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

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 1, page 21-36
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMargenstern, Maurice. "About the domino problem in the hyperbolic plane from an algorithmic point of view." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 21-36. <http://eudml.org/doc/250271>.

@article{Margenstern2008,

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.
},

author = {Margenstern, Maurice},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Tilings; tiling problem; hyperbolic plane; origin-constrained problem; tilings},

language = {eng},

month = {1},

number = {1},

pages = {21-36},

publisher = {EDP Sciences},

title = {About the domino problem in the hyperbolic plane from an algorithmic point of view},

url = {http://eudml.org/doc/250271},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Margenstern, Maurice

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

JO - RAIRO - Theoretical Informatics and Applications

DA - 2008/1//

PB - EDP Sciences

VL - 42

IS - 1

SP - 21

EP - 36

AB -
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.

LA - eng

KW - Tilings; tiling problem; hyperbolic plane; origin-constrained problem; tilings

UR - http://eudml.org/doc/250271

ER -

## References

top- R. Berger, The undecidability of the domino problem. Mem. Amer. Math. Soc.66 (1966) 1–72. Zbl0199.30802
- Ch. Goodman-Strauss, A strongly aperiodic set of tiles in the hyperbolic plane. Invent. Math.159 (2005) 119–132. Zbl1064.52012
- M. Margenstern, New tools for cellular automata of the hyperbolic plane. J. Univ. Comput. Sci.6 (2000) 1226–1252. Zbl0967.68111
- M. Margenstern, About the domino problem in the hyperbolic plane from an algorithmic point of view, Technical report, 2006–101, LITA, Université Paul Verlaine - Metz (2006), available at: ~margens/hyp_dominoes.ps.gzip URIhttp://www.lita.sciences.univ-metz.fr/
- M. Margenstern, Fibonacci numbers and words in tilings of the hyperbolic plane. TUCS Gen. Publ.43 (2007) 36–41.
- M. Margenstern, About the domino problem in the hyperbolic plane, a new solution, arXiv:cs.CG/0701096 (2007). Zbl1169.03354
- M. Margenstern, The domino problem of the hyperbolic plane is undecidable, arXiv:0706.4161 (2007). Zbl1169.03354
- M. Margenstern, Cellular Automata in Hyperbolic Spaces, Volume 1, Theory. OCP, Philadelphia (2007). Zbl1147.68583
- R.M. Robinson, Undecidability and nonperiodicity for tilings of the plane. Invent. Math.12 (1971) 177–209. Zbl0197.46801
- R.M. Robinson, Undecidable tiling problems in the hyperbolic plane. Invent. Math.44 (1978) 259–264. Zbl0354.50006
- H. Wang, Proving theorems by pattern recognition. Bell System Tech. J.40 (1961) 1–41.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.