Quantifier extensions of multidimensional sofic shifts

Törmä, Ilkka

doi:10.1090/proc/12628

Quantifier extensions of multidimensional sofic shifts
HTML articles powered by AMS MathViewer

by Ilkka Törmä PDF

Proc. Amer. Math. Soc. 143 (2015), 4775-4790 Request permission

Abstract:

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.

References

Nathalie Aubrun and Mathieu Sablik, Simulation of effective subshifts by two-dimensional subshifts of finite type, Acta Appl. Math. 126 (2013), 35–63. MR 3077943, DOI 10.1007/s10440-013-9808-5
Robert Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. 66 (1966), 72. MR 216954
Angela Desai, Subsystem entropy for $\Bbb Z^d$ sofic shifts, Indag. Math. (N.S.) 17 (2006), no. 3, 353–359. MR 2321105, DOI 10.1016/S0019-3577(06)80037-6
Bruno Durand, Andrei Romashchenko, and Alexander Shen, Effective closed subshifts in 1D can be implemented in 2D, Fields of logic and computation, Lecture Notes in Comput. Sci., vol. 6300, Springer, Berlin, 2010, pp. 208–226. MR 2756387, DOI 10.1007/978-3-642-15025-8_{1}2
Steve Kass and Kathleen Madden, A sufficient condition for non-soficness of higher-dimensional subshifts, Proc. Amer. Math. Soc. 141 (2013), no. 11, 3803–3816. MR 3091770, DOI 10.1090/S0002-9939-2013-11646-1
Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092, DOI 10.1017/CBO9780511626302
Erez Louidor, Brian Marcus, and Ronnie Pavlov, Independence entropy of $\Bbb {Z}^d$-shift spaces, Acta Appl. Math. 126 (2013), 297–317. MR 3077954, DOI 10.1007/s10440-013-9819-2
Tom Meyerovitch and Ronnie Pavlov, On independence and entropy for high-dimensional isotropic subshifts, ArXiv e-prints (2011).
Marvin L. Minsky, Computation: finite and infinite machines, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0356580
Ronnie Pavlov, A class of nonsofic multidimensional shift spaces, Proc. Amer. Math. Soc. 141 (2013), no. 3, 987–996. MR 3003690, DOI 10.1090/S0002-9939-2012-11382-6
Ville Salo and Ilkka Törmä, Constructions with countable subshifts of finite type, Fund. Inform. 126 (2013), no. 2-3, [On cover: nos. 3-4], 263–300. MR 3114801