×

About the domino problem in the hyperbolic plane from an algorithmic point of view. (English) Zbl 1237.52016

Summary: 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, 259–264 (1978; Zbl 0359.50011)] and the conjecture that the problem is undecidable.

MSC:

52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
05B45 Combinatorial aspects of tessellation and tiling problems
03D45 Theory of numerations, effectively presented structures
68Q80 Cellular automata (computational aspects)

Citations:

Zbl 0359.50011
PDFBibTeX XMLCite
Full Text: DOI arXiv EuDML

References:

[1] R. Berger, The undecidability of the domino problem. Mem. Amer. Math. Soc.66 (1966) 1-72. · Zbl 0199.30802
[2] Ch. Goodman-Strauss, A strongly aperiodic set of tiles in the hyperbolic plane. Invent. Math.159 (2005) 119-132. · Zbl 1064.52012 · doi:10.1007/s00222-004-0384-1
[3] M. Margenstern, New tools for cellular automata of the hyperbolic plane. J. Univ. Comput. Sci.6 (2000) 1226-1252. · Zbl 0967.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). · Zbl 1169.03354
[7] M. Margenstern, The domino problem of the hyperbolic plane is undecidable, arXiv:0706.4161 (2007). · Zbl 1169.03354
[8] M. Margenstern, Cellular Automata in Hyperbolic Spaces, Volume 1, Theory. OCP, Philadelphia (2007). · Zbl 1147.68583
[9] R.M. Robinson, Undecidability and nonperiodicity for tilings of the plane. Invent. Math.12 (1971) 177-209. · Zbl 0197.46801 · doi:10.1007/BF01418780
[10] R.M. Robinson, Undecidable tiling problems in the hyperbolic plane. Invent. Math.44 (1978) 259-264. · Zbl 0359.50011 · doi:10.1007/BF01403163
[11] H. Wang, Proving theorems by pattern recognition. Bell System Tech. J.40 (1961) 1-41.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.