Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Ranks of finite semigroups of one-dimensional cellular automata.

Castillo-Ramirez, Alonso and Gadouleau, Maximilien (2016) 'Ranks of finite semigroups of one-dimensional cellular automata.', Semigroup forum., 93 (2). pp. 347-362.

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 τ : AG → AG (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 CA(Zn; A) consisting of all cellular automata over the cyclic group Zn and a finite set A. In particular, we determine this rank when n is equal to p, 2k or 2kp, for any odd prime p and k ≥ 1, and we give upper and lower bounds for the general case.

Item Type:Article
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Advance online version)
(465Kb)
Full text:(AM) Accepted Manuscript
Download PDF
(301Kb)
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Final published version)
(449Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/s00233-016-9783-z
Publisher statement:© The Author(s) 2016 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Date accepted:22 February 2016
Date deposited:18 March 2016
Date of first online publication:03 March 2016
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar