Slopes of multidimensional subshifts. (English) Zbl 1440.37025
Summary: In this paper we study the directions of periodicity of multidimensional subshifts of finite type (SFTs) and of multidimensional effectively closed and sofic subshifts. A configuration of a subshift has a slope of periodicity if it is periodic in exactly one direction, the slope representing that direction. In this paper, we prove that \({{\Sigma }^0_1}\) sets of non-commensurable \(\mathbb{Z}^2\) vectors are exactly the sets of slopes of 2D SFTs and that \({{\Sigma }^0_2}\) sets of non-commensurable vectors are exactly the sets of slopes of 3D SFTs, and exactly the sets of slopes of 2D and 3D sofic and effectively closed subshifts.
References:
| [1] | Aubrun, N.; Sablik, M., Simulation of effective subshifts by two-dimensional subshifts of finite type, Acta Applicandae Mathematicae, 126, 1, 35-63 (2013) · Zbl 1283.37014 · doi:10.1007/s10440-013-9808-5 |
| [2] | Ballier, A., Jeandel, E.: Structuring multi-dimensional subshifts. arXiv:1309.6289 (2013) |
| [3] | Berger, R., The Undecidability of the Domino Problem (1964), Ph.D. thesis: Harvard University, Ph.D. thesis |
| [4] | Berger, R.: The Undecidability of the Domino Problem. No. 66 in Memoirs of the American Mathematical Society. The American Mathematical Society (1966) |
| [5] | Culik, Kii; Kari, J., An aperiodic set of Wang cubes, J. Univ. Comput. Sci., 1, 10, 675-686 (1995) · Zbl 0960.68623 |
| [6] | Durand, Bruno; Romashchenko, Andrei; Shen, Alexander, Effective Closed Subshifts in 1D Can Be Implemented in 2D, Fields of Logic and Computation, 208-226 (2010), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1287.37012 |
| [7] | Durand, B.; Romashchenko, A.; Shen, A., Fixed-point tile sets and their applications, J. Comput. Syst. Sci., 78, 3, 731-764 (2012) · Zbl 1244.05049 · doi:10.1016/j.jcss.2011.11.001 |
| [8] | Grandjean, A., de Menibus, B.H., Vanier, P.: Aperiodic points in \(\mathbb{Z}^2 \)-subshifts. In: Automata, Languages, and Programming - 45st International Colloquium, ICALP 2018, Prague, Czech Republic, July 9-13, 2018, Proceedings (2018) · Zbl 1499.68109 |
| [9] | Gurevich, Yu. Sh.; Koryakov, I. O., Remarks on Berger’s paper on the domino problem, Siberian Mathematical Journal, 13, 2, 319-321 (1972) · Zbl 0248.02053 · doi:10.1007/BF00971620 |
| [10] | Hedlund, Ga, Endomorphisms and automorphisms of the shift dynamical system, Math. Syst. theory, 3, 4, 320-375 (1969) · Zbl 0182.56901 · doi:10.1007/BF01691062 |
| [11] | Hochman, M., On the dynamics and recursive properties of multidimensional symbolic systems, Inventiones mathematicae, 176, 1, 131 (2008) · Zbl 1168.37002 · doi:10.1007/s00222-008-0161-7 |
| [12] | Hochman, M.; Meyerovitch, T., A characterization of the entropies of multidimensional shifts of finite type, Ann. Math., 171, 3, 2011-2038 (2010) · Zbl 1192.37022 · doi:10.4007/annals.2010.171.2011 |
| [13] | Jeandel, E., Rao, M.: An aperiodic set of 11 wang tiles. arXiv:1506.06492 (2015) · Zbl 1478.05020 |
| [14] | Jeandel, Emmanuel; Vanier, Pascal, Periodicity in Tilings, Developments in Language Theory, 243-254 (2010), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1250.68109 |
| [15] | Jeandel, E., Vanier, P.: Slopes of tilings. In: Kari, J. (ed.) JAC, pp 145-155. Turku Center for Computer Science (2010) · Zbl 1250.68109 |
| [16] | Jeandel, E.; Vanier, P., Characterizations of periods of multi-dimensional shifts, Ergodic Theory Dyn. Syst., 35, 431-460 (2015) · Zbl 1336.37015 · doi:10.1017/etds.2013.60 |
| [17] | Kari, J., The nilpotency problem of one-dimensional cellular automata, SIAM J. Comput., 21, 3, 571-586 (1992) · Zbl 0761.68067 · doi:10.1137/0221036 |
| [18] | Kari, J., A small aperiodic set of Wang tiles, Discret. Math., 160, 259-264 (1996) · Zbl 0861.05017 · doi:10.1016/0012-365X(95)00120-L |
| [19] | Lind, Da; Marcus, B., An Introduction to Symbolic Dynamics and Coding (1995), New York: Cambridge University Press, New York · Zbl 1106.37301 |
| [20] | Meyerovitch, Tom, Growth-type invariants for ℤ d subshifts of finite type and arithmetical classes of real numbers, Inventiones mathematicae, 184, 3, 567-589 (2010) · Zbl 1246.37032 · doi:10.1007/s00222-010-0296-1 |
| [21] | Moutot, Etienne; Vanier, Pascal, Slopes of 3-Dimensional Subshifts of Finite Type, Computer Science - Theory and Applications, 257-268 (2018), Cham: Springer International Publishing, Cham · Zbl 1440.37026 |
| [22] | Myers, D., Non recursive tilings of the plane II, J. Symb. Log., 39, 2, 286-294 (1974) · Zbl 0299.02055 · doi:10.2307/2272641 |
| [23] | Ollinger, N.: Two-by-two substitution systems and the undecidability of the domino problem. In: CiE 2008, no. 5028 in Lecture Notes in Computer Science, pp. 476-485 (2008) · Zbl 1142.03357 |
| [24] | Robinson, Rm, Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12, 3, 177-209 (1971) · Zbl 0197.46801 · doi:10.1007/BF01418780 |
| [25] | Rogers, Hjr, Theory of Recursive Functions and Effective Computability (1987), Cambridge: MIT Press, Cambridge |
| [26] | 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. 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.
