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
Additional Information
- Ilkka Törmä
- Affiliation: TUCS – Turku Centre for Computer Science, University of Turku, Finland
- Email: iatorm@utu.fi
- Received by editor(s): January 9, 2014
- Received by editor(s) in revised form: June 10, 2014, and July 23, 2014
- Published electronically: April 10, 2015
- Additional Notes: This research was supported by the Academy of Finland Grant 131558
- Communicated by: Nimish Shah
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 143 (2015), 4775-4790
- MSC (2010): Primary 37B50
- DOI: https://doi.org/10.1090/proc/12628
- MathSciNet review: 3391035