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
topHow 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.
- Ch. Goodman-Strauss, A strongly aperiodic set of tiles in the hyperbolic plane. Invent. Math.159 (2005) 119–132.
- M. Margenstern, New tools for cellular automata of the hyperbolic plane. J. Univ. Comput. Sci.6 (2000) 1226–1252.
- 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).
- M. Margenstern, The domino problem of the hyperbolic plane is undecidable, arXiv:0706.4161 (2007).
- M. Margenstern, Cellular Automata in Hyperbolic Spaces, Volume 1, Theory. OCP, Philadelphia (2007).
- R.M. Robinson, Undecidability and nonperiodicity for tilings of the plane. Invent. Math.12 (1971) 177–209.
- R.M. Robinson, Undecidable tiling problems in the hyperbolic plane. Invent. Math.44 (1978) 259–264.
- H. Wang, Proving theorems by pattern recognition. Bell System Tech. J.40 (1961) 1–41.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.