×

zbMATH — the first resource for mathematics

A hierarchical strongly aperiodic set of tiles in the hyperbolic plane. (English) Zbl 1182.03072
Summary: We give a new construction of strongly aperiodic set of tiles in \(\mathbb H^2\), exhibiting a kind of hierarchical structure, simplifying the central framework of M. Margenstern’s proof [Theor. Comput. Sci. 407, No. 1–3, 29–84 (2008; Zbl 1152.03036)] that the Domino Problem is undecidable in the hyperbolic plane.

MSC:
03D35 Undecidability and degrees of sets of sentences
05B45 Combinatorial aspects of tessellation and tiling problems
52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
68Q80 Cellular automata (computational aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ammann, R.; Grunbaum, B.; Shepherd, G.C., Aperiodic tiles, Discrete comput. geom., 8, 1-25, (1992) · Zbl 0758.52013
[2] Berger, R., The undecidability of the domino problem, Memoirs am. math. soc., 66, (1966) · Zbl 0199.30802
[3] R. Berger, The undecidability of the domino problem, Ph.D. Dissertation, Division of Engineering and Applied Physics (Applied Mathematics), Harvard University, 1964 · Zbl 0199.30802
[4] Gardner, M., Extraordinary nonperiodic tiling that enriches the theory of tilings, Scientific American, 236, 110-121, (1977)
[5] Goodman-Strauss, C., Matching rules and substitution tilings, Ann. of math., 147, 181-223, (1998) · Zbl 0941.52018
[6] Goodman-Strauss, C., A small aperiodic set of planar tiles, Europ. J. combin., 20, 375-384, (1999) · Zbl 0947.52009
[7] Goodman-Strauss, C., A strongly aperiodic set of tiles in the hyperbolic plane, Invent. math., 159, 119-132, (2005) · Zbl 1064.52012
[8] Goodman-Strauss, C., Regular production systems and triangle tilings, Theoret. comput. sci., 410, 1534-1549, (2009) · Zbl 1162.68019
[9] Grünbaum, B.; Shepherd, G.C., Tilings and patterns, (1987), W.H. Freeman and Co. · Zbl 0601.05001
[10] Kari, J., A small aperiodic set of Wang tiles, Discrete math., 160, 259-264, (1996) · Zbl 0861.05017
[11] Kari, J., The tiling problem revisited, Lect. notes comput. sci., 4664, 72-79, (2007) · Zbl 1211.03062
[12] Mann, C., Hyperbolic regular polygons with notched edges, Discrete comput. geom., 34, 143-166, (2005) · Zbl 1079.52012
[13] Margenstern, M.; Morita, K., NP problems are tractable in the space of cellular automata in the hyperbolic plane, Theoret. comput. sci., 259, 99-128, (2001) · Zbl 0972.68119
[14] Margenstern, M., New tools for cellular automata in the hyperbolic plane, J. universal comp. sci., 6, 1226-1252, (2000) · Zbl 0967.68111
[15] M. Margenstern, Revisiting Poincaré’s theorem with the splitting method, in: Proc. of Bolyai’200, International Conf. on Geom. and Top., Cluj-Napoca, Romania, 2002
[16] Margenstern, M., The domino problem in the hyperbolic plane is undecidable, Theoret. comput. sci., 407, 29-84, (2008) · Zbl 1152.03036
[17] Margulis, G.A.; Mozes, S., Aperiodic tilings of the hyperbolic plane by convex polygons, Israel. J. math., 107, 319-325, (1998) · Zbl 0928.52012
[18] Mozes, S., Tilings, substitution systems and dynamical systems generated by them, J. D’analyse math., 53, 139-186, (1989) · Zbl 0745.52013
[19] Mozes, S., Aperiodic tilings, Invent. math., 128, 603-611, (1997) · Zbl 0879.52011
[20] Radin, C., The pinwheel tilings of the plane, Ann. of math., 139, 661-702, (1994) · Zbl 0808.52022
[21] Robinson, R.M., Undecidability and nonperiodicity of tilings in the plane, Invent. math., 12, 177-209, (1971) · Zbl 0197.46801
[22] Robinson, R.M., Undecidable tiling problems in the hyperbolic plane, Invent. math., 44, 259-264, (1978) · Zbl 0354.50006
[23] P. Schmitt, An aperiodic prototile in space, informal notes, Vienna, 1988
[24] N. Wetzler, Non-periodic uniform tilings in the hyperbolic plane, undergraduate thesis, Honors College, University of Arkansas, 2007
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.