Ranks of finite semigroups of one-dimensional cellular automata

DOI10.1007/S00233-016-9783-ZMaRDI QIDQ343476zbMATH OpenOpenAlexWikidataFDO

Authors Alonso Castillo-Ramirez, Maximilien Gadouleau

Publication date 28 November 2016

Published in Semigroup Forum (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 46357 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• scientific article; zbMATH DE number 3092602 (Why is no real title available?)
• Amenable groups and cellular automata
• Cellular automata and groups
• Classical finite transformation semigroups. An introduction.
• Computation theory of cellular automata
• Gardens of Eden and amenability on cellular automata
• 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
• 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
• Witt vectors and the algebra of necklaces

Cited in

(7)

• On Finite Monoids of Cellular Automata
• 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
• Generating infinite monoids of cellular automata
• On the minimal number of generators of endomorphism monoids of full shifts
• 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)