%0 Conference Proceedings
%T On Finite Monoids of Cellular Automata
%+ Durham University
%A Castillo-Ramirez, Alonso
%A Gadouleau, Maximilien
%Z Part 2: Regular Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Zurich, Switzerland
%Y Matthew Cook
%Y Turlough Neary
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-9664
%P 90-104
%8 2016-06-15
%D 2016
%R 10.1007/978-3-319-39300-1_8
%K Cellular automata
%K Invertible cellular automata
%K Monoids
%K Generating sets
%Z Computer Science [cs]Conference papers
%X For any group <i>G</i> and set<i> A</i>, a cellular automaton over <i>G</i> and <i>A</i> is a transformation <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>&#x03C4;<!-- τ --></mi> <mo>:</mo> <msup> <mi>A</mi> <mi>G</mi> </msup> <mo stretchy="false">&#x2192;<!-- → --></mo> <msup> <mi>A</mi> <mi>G</mi> </msup></math> defined via a finite neighbourhood <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>S</mi> <mo>&#x2286;<!-- ⊆ --></mo> <mi>G</mi></math> (called a memory set of <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>&#x03C4;<!-- τ --></mi></math>) and a local function <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>&#x03BC;<!-- μ --></mi> <mo>:</mo> <msup> <mi>A</mi> <mi>S</mi> </msup> <mo stretchy="false">&#x2192;<!-- → --></mo> <mi>A</mi></math>. In this paper, we assume that <i>G</i> and <i>A</i> are both finite and study various algebraic properties of the finite monoid <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> <mi mathvariant="normal">A</mi> </mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>A</mi> <mo stretchy="false">)</mo></math> consisting of all cellular automata over <i>G</i> and <i>A</i>. Let <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">I</mi> <mi mathvariant="normal">C</mi> <mi mathvariant="normal">A</mi> </mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi>A</mi> <mo stretchy="false">)</mo></math be the group of invertible cellular automata over <i>G</i> and <i>A</i>. In the first part, using information on the conjugacy classes of subgroups of <i>G</i>, we give a detailed description of the structure of <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">I</mi> <mi mathvariant="normal">C</mi> <mi mathvariant="normal">A</mi> </mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi>A</mi> <mo stretchy="false">)</mo></math> in terms of direct and wreath products. In the second part, we study generating sets of <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> <mi mathvariant="normal">A</mi> </mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi>A</mi> <mo stretchy="false">)</mo></math>. In particular, we prove that <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> <mi mathvariant="normal">A</mi> </mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>A</mi> <mo stretchy="false">)</mo></math> cannot be generated by cellular automata with small memory set, and, when <i>G</i> is finite abelian, we determine the minimal size of a set <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>V</mi> <mo>&#x2286;<!-- ⊆ --></mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> <mi mathvariant="normal">A</mi> </mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi>A</mi> <mo stretchy="false">)</mo></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">C</mi> <mi mathvariant="normal">A</mi> </mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi>A</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo fence="false" stretchy="false">&#x27E8;<!-- ⟨ --></mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">I</mi> <mi mathvariant="normal">C</mi> <mi mathvariant="normal">A</mi> </mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>;</mo> <mi>A</mi> <mo stretchy="false">)</mo> <mo>&#x222A;<!-- ∪ --></mo> <mi>V</mi> <mo fence="false" stretchy="false">&#x27E9;<!-- ⟩ --></mo></math>.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-01435036/document
%2 https://inria.hal.science/hal-01435036/file/395687_1_En_8_Chapter.pdf
%L hal-01435036
%U https://inria.hal.science/hal-01435036
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-9664
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA