Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Quantifier extensions of multidimensional sofic shifts

Author: Ilkka Törmä
Journal: Proc. Amer. Math. Soc. 143 (2015), 4775-4790
MSC (2010): Primary 37B50
Published electronically: April 10, 2015
MathSciNet review: 3391035
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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,
  • [2] Robert Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. No. 66 (1966), 72. MR 0216954 (36 #49)
  • [3] Angela Desai, Subsystem entropy for $ \mathbb{Z}^d$ sofic shifts, Indag. Math. (N.S.) 17 (2006), no. 3, 353-359. MR 2321105 (2009h:37020),
  • [4] 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 (2012k:37043),
  • [5] 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,
  • [6] Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092 (97a:58050)
  • [7] Erez Louidor, Brian Marcus, and Ronnie Pavlov, Independence entropy of $ \mathbb{Z}^d$-shift spaces, Acta Appl. Math. 126 (2013), 297-317. MR 3077954,
  • [8] Tom Meyerovitch and Ronnie Pavlov, On independence and entropy for high-dimensional isotropic subshifts, ArXiv e-prints (2011).
  • [9] Marvin L. Minsky, Computation: finite and infinite machines, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. Prentice-Hall Series in Automatic Computation. MR 0356580 (50 #9050)
  • [10] Ronnie Pavlov, A class of nonsofic multidimensional shift spaces, Proc. Amer. Math. Soc. 141 (2013), no. 3, 987-996. MR 3003690,
  • [11] 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

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 37B50

Retrieve articles in all journals with MSC (2010): 37B50

Additional Information

Ilkka Törmä
Affiliation: TUCS – Turku Centre for Computer Science, University of Turku, Finland

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
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society