On Finite Monoids of Cellular Automata

DOI10.1007/978-3-319-39300-1_8MaRDI QIDQ3186476zbMATH OpenOpenAlexFDO

Authors Alonso Castillo-Ramirez, Maximilien Gadouleau

Publication date 10 August 2016

Published in Cellular Automata and Discrete Complex Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.05694, http://dro.dur.ac.uk/20334/1/20334.pdf

zbMATH Keywords

cellular automatonmonoidgenerating setinvertible elements

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Abstract: For any group $G$ and set $A$, a cellular automaton over $G$ and $A$ is a transformation $au:A^{G}o{A}^G$ defined via a finite neighborhood $SsubseteqG$ (called a memory set of $au$) and a local function $mu:A^{S}oA$. In this paper, we assume that $G$ and $A$ are both finite and study various algebraic properties of the finite monoid $extCA(G,A)$ consisting of all cellular automata over $G$ and $A$. Let $extICA(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 $extICA(G;A)$ in terms of direct and wreath products. In the second part, we study generating sets of $extCA(G;A)$. In particular, we prove that $extCA(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 $VsubseteqextCA(G;A)$ such that $extCA(G;A)=langleextICA(G;A)cupVangle$.

Recommendations

• Groups and Monoids of Cellular Automata
• The algebraic properties of finite cellular automata
• Generating infinite monoids of cellular automata
• Propositional logic and cellular automata on monoids
• Bounding the minimal number of generators of groups and monoids of cellular automata
• On algebraic cellular automata
• Cellular automata over algebraic structures
• On cellular automata over Galois rings
• Cellular automata and finite fields

Cites work

• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• Cellular automata and groups
• Classical finite transformation semigroups. An introduction.
• Groups and Monoids of Cellular Automata
• Idempotent rank in finite full transformation semigroups
• Large semigroups of cellular automata.
• On the ranks of certain finite semigroups of transformations
• Ranks of finite semigroups of one-dimensional cellular automata
• The minimal number of generators of a finite semigroup.
• The rank of the endomorphism monoid of a uniform partition.
• The rank of the semigroup of transformations stabilising a partition of a finite set
• Theory of cellular automata: a survey

Cited in

(16)

• A generalization of cellular automata over groups
• Generating infinite monoids of cellular automata
• Constructible functions in cellular automata and their applications to hierarchy results
• On residually finite semigroups of cellullar automata
• Propositional logic and cellular automata on monoids
• On the minimal number of generators of endomorphism monoids of full shifts
• On the minimal memory set of cellular automata
• Cellular automata over algebraic structures
• Bounding the minimal number of generators of groups and monoids of cellular automata
• Cellular automata and finite groups
• On Nilpotency and Asymptotic Nilpotency of Cellular Automata
• Ranks of finite semigroups of one-dimensional cellular automata
• Groups and Monoids of Cellular Automata
• Elementary, finite and linear vN-regular cellular automata
• Von Neumann regular cellular automata
• CELLULAR AUTOMATA OVER SEMI-DIRECT PRODUCT GROUPS: REDUCTION AND INVERTIBILITY RESULTS

This page was built for publication: On Finite Monoids of Cellular Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3186476)