Skip to Main content Skip to Navigation
Conference papers

On Finite Monoids of Cellular Automata

Abstract : For any group G and set A, a cellular automaton over G and A is a transformation τ : A G A G defined via a finite neighbourhood S G (called a memory set of τ ) and a local function μ : A S A . In this paper, we assume that G and A are both finite and study various algebraic properties of the finite monoid C A ( G , A ) consisting of all cellular automata over G and A. Let I C A ( G ; A ) 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 I C A ( G ; A ) in terms of direct and wreath products. In the second part, we study generating sets of C A ( G ; A ) . In particular, we prove that C A ( 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 C A ( G ; A ) such that C A ( G ; A ) = I C A ( G ; A ) V .
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01435036
Contributor : Hal Ifip <>
Submitted on : Friday, January 13, 2017 - 3:24:12 PM
Last modification on : Thursday, July 19, 2018 - 4:58:10 PM
Document(s) archivé(s) le : Friday, April 14, 2017 - 8:30:52 PM

File

395687_1_En_8_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Alonso Castillo-Ramirez, Maximilien Gadouleau. On Finite Monoids of Cellular Automata. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. pp.90-104, ⟨10.1007/978-3-319-39300-1_8⟩. ⟨hal-01435036⟩

Share

Metrics

Record views

184

Files downloads

163