Alonso Castillo-Ramirez
Ranks of finite semigroups of one-dimensional cellular automata
Castillo-Ramirez, Alonso; Gadouleau, Maximilien
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.
Citation
Castillo-Ramirez, A., & Gadouleau, M. (2016). Ranks of finite semigroups of one-dimensional cellular automata. Semigroup Forum, 93(2), 347-362. https://doi.org/10.1007/s00233-016-9783-z
Journal Article Type | Article |
---|---|
Acceptance Date | Feb 22, 2016 |
Online Publication Date | Mar 3, 2016 |
Publication Date | Oct 1, 2016 |
Deposit Date | Mar 17, 2016 |
Publicly Available Date | Mar 18, 2016 |
Journal | Semigroup Forum |
Print ISSN | 0037-1912 |
Electronic ISSN | 1432-2137 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 93 |
Issue | 2 |
Pages | 347-362 |
DOI | https://doi.org/10.1007/s00233-016-9783-z |
Files
Published Journal Article (Advance online version)
(476 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
Advance online version © 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.
Accepted Journal Article
(308 Kb)
PDF
Published Journal Article (Final published version)
(459 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
Final published version
You might also like
Bent functions in the partial spread class generated by linear recurring sequences
(2022)
Journal Article
Expansive automata networks
(2020)
Journal Article
Fixing monotone Boolean networks asynchronously
(2020)
Journal Article
Elementary, finite and linear vN-regular cellular automata
(2020)
Journal Article
Complete Simulation of Automata Networks
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search