OASIcs.AUTOMATA.2021.11.pdf
- Filesize: 0.56 MB
- 10 pages
Document
Von Neumann Regularity, Split Epicness and Elementary Cellular Automata
Author
Ville Salo 
-
Part of:
Volume:
27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)
Series: Open Access Series in Informatics (OASIcs)
Conference: International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-28
File
Document Identifiers
Author Details
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 As Get 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)
0PDF Downloads
References
- 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.
- 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.
-
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.
-
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.
- 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.
- Douglas Lind and Brian Marcus. An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge, 1995. URL: https://doi.org/10.1017/CBO9780511626302.
-
M. Lothaire. Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2002.
- V. Salo. Von Neumann regularity, split epicness and elementary cellular automata. ArXiv e-prints, April 2018. URL: http://arxiv.org/abs/1804.03913.
- 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.
- 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.
- Stephen Wolfram. Statistical mechanics of cellular automata. Rev. Modern Phys., 55(3):601-644, 1983. URL: https://doi.org/10.1103/RevModPhys.55.601.