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

Maurice Margenstern

RAIRO - Theoretical Informatics and Applications (2008)

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

Abstract

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

How to cite

top

Margenstern, 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
  1. R. Berger, The undecidability of the domino problem. Mem. Amer. Math. Soc.66 (1966) 1–72.  Zbl0199.30802
  2. Ch. Goodman-Strauss, A strongly aperiodic set of tiles in the hyperbolic plane. Invent. Math.159 (2005) 119–132.  Zbl1064.52012
  3. M. Margenstern, New tools for cellular automata of the hyperbolic plane. J. Univ. Comput. Sci.6 (2000) 1226–1252.  Zbl0967.68111
  4. 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/
  5. M. Margenstern, Fibonacci numbers and words in tilings of the hyperbolic plane. TUCS Gen. Publ.43 (2007) 36–41.  
  6. M. Margenstern, About the domino problem in the hyperbolic plane, a new solution, arXiv:cs.CG/0701096 (2007).  Zbl1169.03354
  7. M. Margenstern, The domino problem of the hyperbolic plane is undecidable, arXiv:0706.4161 (2007).  Zbl1169.03354
  8. M. Margenstern, Cellular Automata in Hyperbolic Spaces, Volume 1, Theory. OCP, Philadelphia (2007).  Zbl1147.68583
  9. R.M. Robinson, Undecidability and nonperiodicity for tilings of the plane. Invent. Math.12 (1971) 177–209.  Zbl0197.46801
  10. R.M. Robinson, Undecidable tiling problems in the hyperbolic plane. Invent. Math.44 (1978) 259–264.  Zbl0354.50006
  11. H. Wang, Proving theorems by pattern recognition. Bell System Tech. J.40 (1961) 1–41.  

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.