×

zbMATH — the first resource for mathematics

About the domino problem for subshifts on groups. (English) Zbl 1405.20023
Berthé, Valérie (ed.) et al., Sequences, groups, and number theory. Cham: Birkhäuser (ISBN 978-3-319-69151-0/hbk; 978-3-319-69152-7/ebook). Trends in Mathematics, 331-389 (2018).
Summary: From a classical point of view, the domino problem is the question of the existence of an algorithm which can decide whether a finite set of square tiles with colored edges can tile the plane, subject to the restriction that adjacent tiles share the same color along their adjacent edges. This question has already been settled in the negative by R. Berger [Mem. Am. Math. Soc. 66, 72 p. (1966; Zbl 0199.30802)]; however, these tilings can be reinterpreted in dynamical terms using the formalism of subshifts of finite type, and hence the same question can be formulated for arbitrary finitely generated groups. In this chapter, we present the state of the art concerning the domino problem in this extended framework. We also discuss different notions of effectiveness in subshifts defined over groups, that is, the ways in which these dynamical objects can be described through Turing machines.
For the entire collection see [Zbl 1394.05002].
MSC:
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
03D40 Word problems, etc. in computability and recursion theory
03D35 Undecidability and degrees of sets of sentences
05B45 Combinatorial aspects of tessellation and tiling problems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aubrun, N., Barbieri, S., Sablik, M.: A notion of effectiveness for subshifts on finitely generated groups. Theor. Comput. Sci. 661, 35-55 (2017) · Zbl 1356.68057
[2] Aubrun, N., Kari, J.: Tiling problems on Baumslag-Solitar groups. In: MCU’13, pp. 35-46 (2013)
[3] Aubrun, N., Sablik, M.: Multidimensional effective S-adic systems are sofic. Uniform Distribution Theory 9(2), 7-29 (2014) · Zbl 1433.37009
[4] Ballier, A., Jeandel, E.: Tilings and model theory. First Symposium on Cellular Automata Journées Automates Cellulaires (2008)
[5] Ballier, A., Jeandel, E.: Computing (or not) quasi-periodicity functions of tilings. In: Second Symposium on Cellular Automata “Journées Automates Cellulaires”, JAC 2010, Turku, Finland, December 15-17, 2010. Proceedings, pp. 54-64 (2010)
[6] Barbieri, S., Sablik, M.: A generalization of the simulation theorem for semidirect products. Ergodic Theory Dyn. Syst. (to appear) · Zbl 06617647
[7] Berger, R.: The undecidability of the Domino Problem. Ph.D. thesis, Harvard University (1964) · Zbl 0199.30802
[8] Berger, R.: The undecidability of the domino problem. Mem. Am. Math. Soc. 66, 72 (1966) · Zbl 0199.30802
[9] Blondel, V.D., Bournez, O., Koiran, P., Papadimitriou, C., Tsitsiklis, J.N.: Deciding stability and mortality of piecewise affine dynamical systems. Theor. Comput. Sci. 255(1-2), 687-696 (2001). Article dans revue scientifique avec comité de lecture · Zbl 0973.68067
[10] Büchi, J.R.: Turing-Machines and the Entscheidungsproblem. Math. Ann. 148(3), 201-213 (1962) · Zbl 0118.01602
[11] Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, New York (2010) https://books.google.cl/books?id=N-LSFFaHTKwC · Zbl 1218.37004
[12] Cenzer, D., Dashti, S.A., King, J.L.F.: Computable symbolic dynamics. Math. Log. Q. 54(5), 460-469 (2008) · Zbl 1170.03029
[13] Cohen, D.B.: The large scale geometry of strongly aperiodic subshifts of finite type. Adv. Math. 308, 599-626 (2017) · Zbl 1400.20034
[14] Delvenne, J.C., Kůrka, P., Blondel, V.D.: Computational Universality in Symbolic Dynamical Systems, pp. 104-115. Springer, Berlin/Heidelberg (2005) · Zbl 1102.03304
[15] Diestel, R.: A short proof of Halin’s grid theorem. Abh. Math. Semin. Univ. Hambg. 74, 237-242 (2004) · Zbl 1062.05138
[16] Durand, B., Romashchenko, A., Shen, A.: Effective Closed Subshifts in 1D Can Be Implemented in 2D, pp. 208-226. Springer, Berlin/Heidelberg (2010) · Zbl 1287.37012
[17] Goodman-Strauss, C.: Matching rules and substitution tilings. Ann. Math. 147(1), 181-223 (1998) · Zbl 0941.52018
[18] Goodman-Strauss, C.: A hierarchical strongly aperiodic set of tiles in the hyperbolic plane. Theor. Comput. Sci. 411(7), 1085-1093 (2010) · Zbl 1182.03072
[19] Hadamard, J.: Théorème sur les séries entières. Acta Math. 22, 55-63 (1899) · JFM 29.0210.02
[20] Hedlund, G., Morse, M.: Symbolic dynamics. Am. J. Math. 60(4), 815-866 (1938) · Zbl 0019.33502
[21] Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems. Invent. Math. 176(1), 131-167 (2009) · Zbl 1168.37002
[22] Hooper, P.K.: The undecidability of the Turing machine immortality problem. J. Symb. Log. 31(2), 219-234 (1966) · Zbl 0173.01201
[23] Jeandel, E.: Aperiodic subshifts on polycyclic groups (2015). ArXiv:1510.02360
[24] Jeandel, E.: Translation-like actions and aperiodic subshifts on groups (2015). ArXiv:1508.06419
[25] Jeandel, E., Vanier, P.: Characterizations of periods of multi-dimensional shifts. Ergodic Theory Dyn. Syst. 35(2), 431-460 (2015) · Zbl 1336.37015
[26] Kahr, A., Moore, E.F., Wang, H.: Entscheidungsproblem reduced to the ∀∃∀ case. Proc. Natl. Acad. Sci. U. S. A. 48(3), 365-377 (1962) · Zbl 0102.00801
[27] Kari, J.: The tiling problem revisited. In: MCU, pp. 72-79 (2007) · Zbl 1211.03062
[28] Kari, J.: On the undecidability of the tiling problem. In: Current Trends in Theory and Practice of Computer Science (SOFSEM), pp. 74-82 (2008) · Zbl 1133.03020
[29] Kari, J., Ollinger, N.: Periodicity and immortality in reversible computing. In: 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008). LNCS, vol. 5162, pp. 419-430 (2008) · Zbl 1173.68521
[30] Koiran, P., Cosnard, M., Garzon, M.: Computability with low-dimensional dynamical systems. Theor. Comput. Sci. 132(1), 113-128 (1994) · Zbl 0821.68053
[31] Kurka, P.: On topological dynamics of Turing machines. Theor. Comput. Sci. 174, 203-216 (1997) · Zbl 0902.68064
[32] Kuske, D., Lohrey, M.: Logical aspects of Cayley-graphs: the group case. Ann. Pure Appl. Logic 131(1-3), 263 - 286 (2005) · Zbl 1063.03005
[33] Lennox, J.C., Robinson, D.J.: The Theory of Infinite Soluble Groups. Oxford Mathematical Monographs. Oxford Science Publications, Oxford (2004)
[34] Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995) · Zbl 1106.37301
[35] Magnus, W., Karrass, A., Solitar, D.: Combinatorial Group Theory, 2nd rev. edn. Dover, Mineola (1976) · Zbl 0362.20023
[36] Markley, N.G., Paul, M.E.: Matrix subshifts for \(\(\mathbb {Z}^ν \)\) symbolic dynamics. Proc. Lond. Math. Soc. 3(43), 251-272 (1981) · Zbl 0479.54022
[37] Mozes, S.: Tilings, substitutions systems and dynamical systems generated by them. J. Anal. Math. 53, 139-186 (1989) · Zbl 0745.52013
[38] Muchnik, R., Pak, I.: Percolation on Grigorchuk Groups. Commun. Algebra 29(2), 661-671 (2001) · Zbl 1042.20035
[39] Muller, D.E., Schupp, P.E.: The theory of ends, pushdown automata, and second-order logic. Theor. Comput. Sci. 37, 51-75 (1985) · Zbl 0605.03005
[40] Myers, D.: Non recursive tilings of the plane II. J. Symb. Log. 39(2), 286-294 (1974) · Zbl 0299.02055
[41] Nasu, M.: Textile Systems for Endomorphisms and Automorphisms of the Shift. Memoirs of the American Mathematical Society, vol. 114. American Mathematical Society, Providence (1995) · Zbl 0845.54031
[42] Odifreddi, P.: Chapter XIV enumeration degrees. In: Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics, vol. 143, pp. 827-861. Elsevier, Amsterdam (1999)
[43] Pavlov, R., Schraudner, M.: Classification of sofic projective subdynamics of multidimensional shifts of finite type. Trans. Am. Math. Soc. 367, 3371-3421 (2015) · Zbl 1353.37036
[44] Rips, E.: Subgroups of small cancellation groups. Bull. Lond. Math. Soc. 14, 45-47 (1982) · Zbl 0481.20020
[45] Robertson, N., Seymour, P.: Graph minors. v. excluding a planar graph. J. Comb. Theory Ser. B 41(1), 92-114 (1986) · Zbl 0598.05055
[46] Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12, 177-209 (1971) · Zbl 0197.46801
[47] Robinson, R.M.: Undecidable tiling problems in the hyperbolic plane. Invent. Math. 44, 159-264 (1978) · Zbl 0354.50006
[48] Sablik, M., Fernique, T.: Local rules for computable planar tilings. In: Automata and Journées Automates Cellulaires, Corse, France (2012)
[49] Segal, D.: Polycyclic Groups. Cambridge Tracts in Mathematics, vol. 82. Cambridge University Press, Cambridge (1983) · Zbl 0516.20001
[50] Selman, A.L.: Arithmetical reducibilities I. Math. Log. Q. 17(1), 335-350 (1971) · Zbl 0229.02037
[51] Seward, B.: Burnside’s problem, spanning trees and tilings. Geom. Topol. 18(1), 179-210 (2014) · Zbl 1338.20041
[52] Sipser, M.: Introduction to the Theory of Computation. International Thomson Publishing (1996) · Zbl 1191.68311
[53] Tits, J.: Free subgroups in linear groups. J. Algebra 20(2), 250-270 (1972) · Zbl 0236.20032
[54] Törmä, I.: Quantifier extensions of multidimensional sofic shifts. Proc. Am. Math. Soc. 143, 4775-4790 (2015) · Zbl 1353.37037
[55] Turing, A.: On computable numbers, with an application to the entscheidungsproblem. Proc. Lond. Math. Soc. 42(2), 230265 (1936) · Zbl 0016.09701
[56] Wang, H.: Proving theorems by pattern recognition, II. Bell Syst. Tech. J. 40(1), 1-41 (1961)
[57] Whyte, K.: Amenability, Bilipschitz equivalence, and the Von Neumann Conjecture. Duke Math. J. 99(1), 93-112 (1999) · Zbl 1017.54017
[58] Woess, W.: Graphs and groups with tree-like properties. J. Comb. Theory Ser. B 47(3), 361-371 (1989) · Zbl 0696.05027
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.