EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Ranks of finite semigroups of one-dimensional cellular automata

Alonso Castillo-Ramirez, Maximilien Gadouleau

Semigroup Forum · 2016-10 · 93 (2) · 347-362

DOI: 10.1007/s00233-016-9783-z ↗

Kurz gefasst

Fachartikel in der Zeitschrift Semigroup Forum, online erschienen am 03.03.2016. Verfasst von Alonso Castillo-Ramirez und 1 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 20 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tau : A^G \rightarrow A^G$$\end{document} (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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {CA}(\mathbb {Z}_n; A)$$\end{document} consisting of all cellular automata over the cyclic group Zn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {Z}_n$$\end{document} and a finite set A. In particular, we determine this rank when n is equal to p, 2k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^k$$\end{document} or 2kp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^kp$$\end{document}, for any odd prime p and k≥1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 1$$\end{document}, and we give upper and lower bounds for the general case.

Zitieren

APA

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

Vancouver

Castillo-Ramirez A, Gadouleau M. Ranks of finite semigroups of one-dimensional cellular automata. Semigroup Forum. 2016;93(2):347-362. doi:10.1007/s00233-016-9783-z

BibTeX
@article{CastilloRamirez2016,
  author = {Castillo-Ramirez, Alonso and Gadouleau, Maximilien},
  title = {Ranks of finite semigroups of one-dimensional cellular automata},
  journal = {Semigroup Forum},
  year = {2016},
  volume = {93},
  number = {2},
  pages = {347--362},
  doi = {10.1007/s00233-016-9783-z}
}
Kostenlos starten →