Alonso Castillo-Ramirez
On Finite Monoids of Cellular Automata
Castillo-Ramirez, Alonso; Gadouleau, Maximilien
Authors
Dr Maximilien Gadouleau m.r.gadouleau@durham.ac.uk
Associate Professor
Contributors
Matthew Cook
Editor
Turlough Neary
Editor
Abstract
For any group G and set A, a cellular automaton over G and A is a transformation τ:AG→AGτ:AG→AG defined via a finite neighbourhood S⊆GS⊆G (called a memory set of ττ) and a local function μ:AS→Aμ:AS→A. In this paper, we assume that G and A are both finite and study various algebraic properties of the finite monoid CA(G,A)CA(G,A) consisting of all cellular automata over G and A. Let ICA(G;A)ICA(G;A) be the group of invertible cellular automata over G and A. In the first part, using information on the conjugacy classes of subgroups of G, we give a detailed description of the structure of ICA(G;A)ICA(G;A) in terms of direct and wreath products. In the second part, we study generating sets of CA(G;A)CA(G;A). In particular, we prove that CA(G,A)CA(G,A) cannot be generated by cellular automata with small memory set, and, when G is finite abelian, we determine the minimal size of a set V⊆CA(G;A)V⊆CA(G;A) such that CA(G;A)=⟨ICA(G;A)∪V⟩CA(G;A)=⟨ICA(G;A)∪V⟩.
Citation
Castillo-Ramirez, A., & Gadouleau, M. (2016). On Finite Monoids of Cellular Automata. In M. Cook, & T. Neary (Eds.), Cellular automata and discrete complex systems : 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016. Proceedings (90-104). https://doi.org/10.1007/978-3-319-39300-1_8
Conference Name | International workshop on cellular automata and discrete complex systems |
---|---|
Conference Location | Zurich, Switzerland |
Start Date | Jun 15, 2016 |
End Date | Jun 17, 2016 |
Acceptance Date | Mar 20, 2016 |
Online Publication Date | Jun 2, 2016 |
Publication Date | Jun 2, 2016 |
Deposit Date | Nov 28, 2016 |
Publicly Available Date | Jun 2, 2017 |
Pages | 90-104 |
Series Title | Lecture notes in computer science |
Series Number | 9664 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Cellular automata and discrete complex systems : 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016. Proceedings. |
ISBN | 9783319392998 |
DOI | https://doi.org/10.1007/978-3-319-39300-1_8 |
Public URL | https://durham-repository.worktribe.com/output/1149278 |
Files
Accepted Conference Proceeding
(171 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/978-3-319-39300-1_8
You might also like
Bent functions in the partial spread class generated by linear recurring sequences
(2022)
Journal Article
Expansive automata networks
(2020)
Journal Article
Fixing monotone Boolean networks asynchronously
(2020)
Journal Article
Elementary, finite and linear vN-regular cellular automata
(2020)
Journal Article
Complete Simulation of Automata Networks
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search