zbMATH — the first resource for mathematics

Hardness of conjugacy, embedding and factorization of multidimensional subshifts. (English) Zbl 1328.68074
Summary: Subshifts of finite type are sets of colorings of the plane defined by local constraints. They can be seen as a discretization of continuous dynamical systems. We investigate here the hardness of deciding factorization, conjugacy and embedding of subshifts in dimensions \(d > 1\) for subshifts of finite type and sofic shifts and in dimensions \(d \geq 1\) for effective shifts. In particular, we prove that the conjugacy, factorization and embedding problems are \(\Sigma_3^0\)-complete for sofic and effective subshifts and that they are \(\Sigma_1^0\)-complete for SFTs, except for factorization which is also \(\Sigma_3^0\)-complete.

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
37B50 Multi-dimensional shifts of finite type, tiling dynamics (MSC2010)
Full Text: DOI
[1] Aubrun, N.; Sablik, M., Simulation of effective subshifts by two-dimensional subshifts of finite type, Acta Appl. Math., (2013) · Zbl 1283.37014
[2] Berger, R., The undecidability of the domino problem, (1964), Harvard University, Ph.D. thesis
[3] Boyer, L.; Theyssier, G., On factor universality in symbolic spaces, (MFCS, (2010)), 209-220 · Zbl 1287.68115
[4] Boyle, M., Lower entropy factors of sofic systems, Ergod. Theory Dyn. Syst., 3, 541-551, (1983) · Zbl 0529.28014
[5] Boyle, M., Open problems in symbolic dynamics, Contemp. Math., 469, 69-118, (2008) · Zbl 1158.37007
[6] Hedlund, G. A., Endomorphisms and automorphisms of the shift dynamical system, Theory Comput. Syst., 3, 4, 320-375, (1969) · Zbl 0182.56901
[7] Hochman, M., A note on universality in multidimensional symbolic dynamics, Discrete Contin. Dyn. Syst., Ser. S, 2, 2, (2009) · Zbl 1175.37019
[8] Hochman, M., On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176, 1, (Apr. 2009)
[9] Jeandel, E.; Vanier, P., \(\operatorname{\Pi}_1^0\) sets and tilings, (Theory and Applications of Models of Computation, TAMC, Lecture Notes in Computer Science, vol. 6648, (2011)), 230-239 · Zbl 1333.03109
[10] Jeandel, E.; Vanier, P., Hardness of conjugacy, embedding and factorization of multidimensional subshifts of finite type, (Portier, N.; Wilke, T., STACS, LIPIcs, vol. 20, (2013), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 490-501 · Zbl 1354.68098
[11] Kozen, D., Theory of computation, (2006), Springer New York
[12] Krieger, W., On the subsystems of topological Markov chains, Ergod. Theory Dyn. Syst., 2, 02, 195-202, (1982) · Zbl 0508.54032
[13] Lind, D.; Marcus, B., An introduction to symbolic dynamics and coding, (1995), Cambridge University Press New York, NY, USA · Zbl 1106.37301
[14] Lind, D. A., Multi-dimensional symbolic dynamics, (Williams, S. G., Symbolic Dynamics and Its Applications, Proceedings of Symposia in Applied Mathematics, vol. 60, (2004), American Mathematical Society), 61-79 · Zbl 1070.37009
[15] Robinson, R. M., Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12, (1971) · Zbl 0197.46801
[16] Rogers, H., Theory of recursive functions and effective computability, (1987), MIT Press Cambridge, MA, USA · Zbl 0183.01401
[17] Wang, H., Proving theorems by pattern recognition II, Bell Syst. Tech. J., 40, 1-41, (1961)
[18] Williams, R. F., Classification of subshifts of finite type, Ann. Math., 98, 120-153, (1973) · Zbl 0282.58008
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.