Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-02T22:37:08.011Z Has data issue: false hasContentIssue false

About the domino problem in the hyperbolic plane from an algorithmicpoint of view

Published online by Cambridge University Press:  18 January 2008

Maurice Margenstern*
Affiliation:
Université Paul Verlaine - Metz, IUT de Metz; [email protected]
Get access

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.

Type
Research Article
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Berger, R., The undecidability of the domino problem. Mem. Amer. Math. Soc. 66 (1966) 172.
Ch. Goodman-Strauss, A strongly aperiodic set of tiles in the hyperbolic plane. Invent. Math. 159 (2005) 119132. CrossRef
Margenstern, M., New tools for cellular automata of the hyperbolic plane. J. Univ. Comput. Sci. 6 (2000) 12261252.
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: http://www.lita.sciences.univ-metz.fr/ ~margens/hyp_dominoes.ps.gzip
Margenstern, M., Fibonacci numbers and words in tilings of the hyperbolic plane. TUCS Gen. Publ. 43 (2007) 3641.
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).
Robinson, R.M., Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12 (1971) 177209. CrossRef
Robinson, R.M., Undecidable tiling problems in the hyperbolic plane. Invent. Math. 44 (1978) 259264. CrossRef
Wang, H., Proving theorems by pattern recognition. Bell System Tech. J. 40 (1961) 141. CrossRef