On the image set and reversibility of shift morphisms over discrete alphabets

Authors

  • Jorge Campos Universidad Nacional Experimental Polit´ecnica Antonio Jos´e de Sucre, Departamento de Estudios B´asicos, Secci´on de Matem´atica, Barquisimeto, Venezuela
  • Neptalí Romero Universidad Centroccidental Lisandro Alvarado, Departamento de Matem´atica, Decanato de Ciencias y Tecnolog´ıa, Barquisimeto, Venezuela
  • Ramón Vivas Universidad Nacional Experimental Polit´ecnica Antonio Jos´e de Sucre, Departamento de Estudios B´asicos, Secci´on de Matem´atica, Barquisimeto, Venezuela

DOI:

https://doi.org/10.33044/revuma.1795

Abstract

 We provide sufficient conditions in order to show that the image set of a continuous and shift-commuting map defined on a shift space over an arbitrary discrete alphabet is also a shift space. Additionally, if such a map is injective, then its inverse is also continuous and shift-commuting.

Downloads

Download data is not yet available.

References

T. Ceccherini-Silberstein and M. Coornaert, Induction and restriction of cellular automata, Ergodic Theory Dynam. Systems 29 (2009), no. 2, 371–380. MR 2486775.

T. Ceccherini-Silberstein and M. Coornaert, Cellular Automata and Groups, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2010. MR 2683112.

T. Ceccherini-Silberstein and M. Coornaert, On the reversibility and the closed image property of linear cellular automata, Theoret. Comput. Sci. 412 (2011), no. 4-5, 300–306. MR 2778463.

C. A. Di Prisco and S. Todorcevic, Canonical forms of shift-invariant maps on $[N]^infty$, Discrete Math. 306 (2006), no. 16, 1862–1870. MR 2251567.

, Studies in Logic and the Foundations of Mathematics, 118, North-Holland, Amsterdam, 1986. MR 832435.

D. Gonçalves, M. Sobottka and C. Starling, Sliding block codes between shift spaces over infinite alphabets, Math. Nachr. 289 (2016), no. 17-18, 2178–2191. MR 3583264.

D. Gonçalves, M. Sobottka and C. Starling, Two-sided shift spaces over infinite alphabets, J. Aust. Math. Soc. 103 (2017), no. 3, 357–386. MR 3725178.

M. Gromov, Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc. (JEMS) 1 (1999), no. 2, 109–197. MR 1694588.

M. Gromov, Topological invariants of dynamical systems and spaces of holomorphic maps. I, Math. Phys. Anal. Geom. 2 (1999), no. 4, 323–415. MR 1742309.

G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320–375. MR 0259881.

J. Kari, Reversible cellular automata: from fundamental classical results to recent developments, New Gener. Comput. 36 (2018), 145–172.

B. P. Kitchens, Symbolic Dynamics, Universitext, Springer-Verlag, Berlin, 1998. MR 1484730.

D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995. MR 1369092.

K. Morita, Reversible computing and cellular automata—a survey, Theoret. Comput. Sci. 395 (2008), no. 1, 101–131. MR 2401003.

K. Morita, Reversible cellular automata, in Computational Complexity. Vols. 1–6, 2668–2684, Springer, New York, 2012. MR 3074639.

J. Müller and C. Spandl, A Curtis–Hedlund–Lyndon theorem for Besicovitch and Weyl spaces, Theoret. Comput. Sci. 410 (2009), no. 38-40, 3606–3615. MR 2553315.

C. St. J. A. Nash-Williams, On well-quasi-ordering transfinite sequences, Proc. Cambridge Philos. Soc. 61 (1965), 33–39. MR 0173640.

W. Ott, M. Tomforde and P. N. Willis, One-sided shift spaces over infinite alphabets, NYJM Monographs, 5, State University of New York, University at Albany, Albany, NY, 2014. MR 3207861.

D. Richardson, Tessellations with local transformations, J. Comput. System Sci. 6 (1972), 373–388. MR 0319678.

N. Romero, A. Rovella and F. Vilamajó, Remark on cellular automata and shift preserving maps, Appl. Math. Lett. 19 (2006), no. 6, 576–580. MR 2221516.

O. M. Sarig, Thermodynamic formalism for countable Markov shifts, Ergodic Theory Dynam. Systems 19 (1999), no. 6, 1565–1593. MR 1738951.

M. Sobottka and D. Gonçalves, A note on the definition of sliding block codes and the Curtis–Hedlund–Lyndon theorem, J. Cell. Autom. 12 (2017), no. 3-4, 209–215. MR 3620337.

S. Wacker, Cellular automata on group sets and the uniform Curtis–Hedlund–Lyndon theorem, in Cellular Automata and Discrete Complex Systems, 185–198, Lecture Notes in Comput. Sci., 9664, Springer, 2016. MR 3533912.

Downloads

Published

2022-05-23

Issue

Vol. 63 No. 1 (2022)

Section

Article

License

Copyright (c) 2022 Jorge Campos, Neptalí Romero, Ramón Vivas

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:

Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. The Journal may retract the paper after publication if clear evidence is found that the findings are unreliable as a result of misconduct or honest error.