Ranks of finite semigroups of one-dimensional cellular automata

DOI10.1007/S00233-016-9783-ZzbMATH Open1378.20062arXiv1510.00197OpenAlexW3104722361WikidataQ59474219 ScholiaQ59474219MaRDI QIDQ343476FDOQ343476

Authors: Alonso Castillo-Ramirez, Maximilien Gadouleau 

Publication date: 28 November 2016

Published in: Semigroup Forum (Search for Journal in Brave)

Abstract: Since first introduced by John von Neumann, the notion of cellular automaton has grown into a key concept in computer science, physics and theoretical biology. In its classical setting, a cellular automaton is a transformation of the set of all configurations of a regular grid such that the image of any particular cell of the grid is determined by a fixed local function that only depends on a fixed finite neighbourhood. In recent years, with the introduction of a generalised definition in terms of transformations of the form $au:A^{G}o{A}^G$ (where $G$ is any group and $A$ is any set), the theory of cellular automata has been greatly enriched by its connections with group theory and topology. In this paper, we begin the finite semigroup theoretic study of cellular automata by investigating the rank (i.e. the cardinality of a smallest generating set) of the semigroup $extCA(mathbb{Z}_n;A)$ consisting of all cellular automata over the cyclic group $mathbb{Z}_n$ and a finite set $A$. In particular, we determine this rank when $n$ is equal to $p$, $2^k$ or $2^{k}p$, for any odd prime $p$ and $kgeq1$, and we give upper and lower bounds for the general case.

Full work available at URL: https://arxiv.org/abs/1510.00197

Recommendations

• On Finite Monoids of Cellular Automata
• Bounding the minimal number of generators of groups and monoids of cellular automata
• Large semigroups of cellular automata.
• Groups and Monoids of Cellular Automata
• Cellular automata and groups

zbMATH Keywords

cellular automatafinite semigroupssmallest generating set

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Cellular automata (computational aspects) (68Q80) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Theory of cellular automata: a survey
• Title not available (Why is that?)
• Title not available (Why is that?)
• Classical finite transformation semigroups. An introduction.
• Amenable groups and cellular automata
• Cellular automata and groups
• Gardens of Eden and amenability on cellular automata
• Computation theory of cellular automata
• The rank of the endomorphism monoid of a uniform partition.
• Idempotent rank in finite full transformation semigroups
• On the ranks of certain finite semigroups of transformations
• The minimal number of generators of a finite semigroup.
• Large semigroups of cellular automata.
• The rank of the semigroup of transformations stabilising a partition of a finite set
• Groups and Monoids of Cellular Automata
• Title not available (Why is that?)
• Witt vectors and the algebra of necklaces

Cited In (7)

• Generating infinite monoids of cellular automata
• On Finite Monoids of Cellular Automata
• On the minimal number of generators of endomorphism monoids of full shifts
• Bounding the minimal number of generators of groups and monoids of cellular automata
• Cellular automata and finite groups
• Elementary, finite and linear vN-regular cellular automata
• Large semigroups of cellular automata.

This page was built for publication: Ranks of finite semigroups of one-dimensional cellular automata

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