Von Neumann Regularity, Split Epicness and Elementary Cellular Automata

Author Ville Salo



PDF
Thumbnail PDF

File

OASIcs.AUTOMATA.2021.11.pdf
  • Filesize: 0.56 MB
  • 10 pages

Document Identifiers

Author Details

Ville Salo
  • University of Turku, Finland

Acknowledgements

We thank Jarkko Kari for observing that Proposition 12 works in all dimensions. We thank Johan Kopra for pointing out that Lemma 11 is easier to prove than to find in [Lind and Marcus, 1995].

Cite AsGet BibTex

Ville Salo. Von Neumann Regularity, Split Epicness and Elementary Cellular Automata. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 11:1-11:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.AUTOMATA.2021.11

Abstract

We show that a cellular automaton on a mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from [S.-Törmä, 2015] that von Neumann regularity is decidable condition, and we decide it for all elementary CA.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
Keywords
  • cellular automata
  • elementary cellular automata
  • von Neumann regularity
  • split epicness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Alonso Castillo-Ramirez and Maximilien Gadouleau. Elementary, finite and linear vN-regular cellular automata. Inform. and Comput., 274:104533, 12, 2020. URL: https://doi.org/10.1016/j.ic.2020.104533.
  2. T. Ceccherini-Silberstein and M. Coornaert. Cellular Automata and Groups. Springer Monographs in Mathematics. Springer-Verlag Berlin Heidelberg, 2010. URL: https://books.google.cl/books?id=N-LSFFaHTKwC.
  3. Walter Gottschalk. Some general dynamical notions. In Recent advances in topological dynamics (Proc. Conf. Topological Dynamics, Yale Univ., New Haven, Conn., 1972; in honor of Gustav Arnold Hedlund), pages 120-125. Lecture Notes in Math., Vol. 318, 1973. Google Scholar
  4. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006. Google Scholar
  5. Jarkko Kari. Rice’s theorem for the limit sets of cellular automata. Theoret. Comput. Sci., 127(2):229-254, 1994. URL: https://doi.org/10.1016/0304-3975(94)90041-8.
  6. Douglas Lind and Brian Marcus. An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge, 1995. URL: https://doi.org/10.1017/CBO9780511626302.
  7. M. Lothaire. Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2002. Google Scholar
  8. V. Salo. Von Neumann regularity, split epicness and elementary cellular automata. ArXiv e-prints, April 2018. URL: http://arxiv.org/abs/1804.03913.
  9. Ville Salo and Ilkka Törmä. Category theory of symbolic dynamics. Theor. Comput. Sci., 567:21-45, 2015. URL: https://doi.org/10.1016/j.tcs.2014.10.023.
  10. Benjamin Weiss. Sofic groups and dynamical systems. Sankhyā: The Indian Journal of Statistics, Series A (1961-2002), 62(3):350-359, 2000. URL: http://www.jstor.org/stable/25051326.
  11. Stephen Wolfram. Statistical mechanics of cellular automata. Rev. Modern Phys., 55(3):601-644, 1983. URL: https://doi.org/10.1103/RevModPhys.55.601.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail