×

zbMATH — the first resource for mathematics

The domino problem for self-similar structures. (English) Zbl 06617647
Beckmann, Arnold (ed.) et al., Pursuit of the universal. 12th conference on computability in Europe, CiE 2016, Paris, France, June 27 – July 1, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-40188-1/pbk; 978-3-319-40189-8/ebook). Lecture Notes in Computer Science 9709, 205-214 (2016).
Summary: We define the domino problem for tilings over self-similar structures of \(\mathbb {Z}^d\) given by forbidden patterns. In this setting we exhibit non-trivial families of subsets with decidable and undecidable domino problem.
For the entire collection see [Zbl 1337.68005].

MSC:
68Qxx Theory of computing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aubrun, N., Kari, J.: Tiling problems on Baumslag-Solitar groups. Preprint (2013)
[2] Ballier, A., Stein, M.: The domino problem on groups of polynomial growth. arXiv preprint (2013). arXiv:1311.4222 · Zbl 1386.37017
[3] Berger, R.: The undecidability of the domino problem. Am. Math. Soc. 66, 1–72 (1966) · Zbl 0199.30802
[4] Goodman-Strauss, C.: Matching rules and substitution tilings. Ann. Math. 147(1), 181–223 (1998) · Zbl 0941.52018 · doi:10.2307/120988
[5] Lind, D.A., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York (1995) · Zbl 1106.37301 · doi:10.1017/CBO9780511626302
[6] Margenstern, M.: The domino problem of the hyperbolic plane is undecidable. Bull. EATCS 93, 220–237 (2007) · Zbl 1169.03354
[7] Mozes, S.: Tilings, substitution systems and dynamical systems generated by them. Journal d’Analyse Mathématique 53(1), 139–186 (1989) · Zbl 0745.52013 · doi:10.1007/BF02793412
[8] Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae 12, 177–209 (1971) · Zbl 0197.46801 · doi:10.1007/BF01418780
[9] Robinson, R.M.: Undecidable tiling problems in the hyperbolic plane. Inventiones Mathematicae 44, 159–264 (1978) · Zbl 0354.50006 · doi:10.1007/BF01403163
[10] Wang, H.: Proving theorems by pattern recognition I. Commun. ACM 3(4), 220–234 (1960) · Zbl 0101.10504 · doi:10.1145/367177.367224
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.