zbMATH — the first resource for mathematics

Quantifier extensions of multidimensional sofic shifts. (English) Zbl 1353.37037
Summary: We define a pair of simple combinatorial operations on subshifts, called existential and universal extensions, and study their basic properties. We prove that the existential extension of a sofic shift by another sofic shift is always sofic, and the same holds for the universal extension in one dimension. However, we also show by a construction that universal extensions of two-dimensional sofic shifts may not be sofic, even if the subshift we extend by is very simple.

37B50 Multi-dimensional shifts of finite type, tiling dynamics (MSC2010)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI arXiv
[1] Aubrun, Nathalie; Sablik, Mathieu, Simulation of effective subshifts by two-dimensional subshifts of finite type, Acta Appl. Math., 126, 35-63, (2013) · Zbl 1283.37014
[2] Berger, Robert, The undecidability of the domino problem, Mem. Amer. Math. Soc. No., 66, 72 pp., (1966) · Zbl 0199.30802
[3] Desai, Angela, Subsystem entropy for \(\mathbb{Z}^d\) sofic shifts, Indag. Math. (N.S.), 17, 3, 353-359, (2006) · Zbl 1104.37006
[4] Durand, Bruno; Romashchenko, Andrei; Shen, Alexander, Effective closed subshifts in 1D can be implemented in 2D. Fields of logic and computation, Lecture Notes in Comput. Sci. 6300, 208-226, (2010), Springer, Berlin · Zbl 1287.37012
[5] Kass, Steve; Madden, Kathleen, A sufficient condition for non-soficness of higher-dimensional subshifts, Proc. Amer. Math. Soc., 141, 11, 3803-3816, (2013) · Zbl 1358.37040
[6] Lind, Douglas; Marcus, Brian, An introduction to symbolic dynamics and coding, xvi+495 pp., (1995), Cambridge University Press, Cambridge · Zbl 1106.37301
[7] Louidor, Erez; Marcus, Brian; Pavlov, Ronnie, Independence entropy of \(\mathbb{Z}^d\)-shift spaces, Acta Appl. Math., 126, 297-317, (2013) · Zbl 1329.37021
[8] [MePa11] Tom Meyerovitch and Ronnie Pavlov, On independence and entropy for high-dimensional isotropic subshifts, ArXiv e-prints (2011). · Zbl 1358.37037
[9] Minsky, Marvin L., Computation: finite and infinite machines, xvii+317 pp., (1967), Prentice-Hall, Inc., Englewood Cliffs, N.J. · Zbl 0195.02402
[10] Pavlov, Ronnie, A class of nonsofic multidimensional shift spaces, Proc. Amer. Math. Soc., 141, 3, 987-996, (2013) · Zbl 1329.37023
[11] Salo, Ville; T\`‘orm\'’a, Ilkka, Constructions with countable subshifts of finite type, Fund. Inform., 126, 2-3, [On cover: nos. 3-4], 263-300, (2013) · Zbl 1359.68210
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.