Cellular automata and finite groups

30.09.2017

Erschienen in:

Verfasst von: Alonso Castillo-Ramirez; Maximilien Gadouleau
Erschienen in: Natural Computing | Ausgabe 3/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

For a finite group G and a finite set A, we study various algebraic aspects of cellular automata over the configuration space \(A^G\). In this situation, the set \(\mathrm {CA}(G;A)\) of all cellular automata over \(A^G\) is a finite monoid whose basic algebraic properties had remained unknown. First, we investigate the structure of the group of units \(\mathrm {ICA}(G;A)\) of \(\mathrm {CA}(G;A)\). We obtain a decomposition of \(\mathrm {ICA}(G;A)\) into a direct product of wreath products of groups that depends on the numbers \(\alpha _{[H]}\) of periodic configurations for conjugacy classes [H] of subgroups of G. We show how the numbers \(\alpha _{[H]}\) may be computed using the Möbius function of the subgroup lattice of G, and we use this to improve the lower bound recently found by Gao, Jackson and Seward on the number of aperiodic configurations of \(A^G\). Furthermore, we study generating sets of \(\mathrm {CA}(G;A)\); in particular, we prove that \(\mathrm {CA}(G;A)\) cannot be generated by cellular automata with small memory set, and, when all subgroups of G are normal, we determine the relative rank of \(\mathrm {ICA}(G;A)\) on \(\mathrm {CA}(G;A)\), i.e. the minimal size of a set \(V \subseteq \mathrm {CA}(G;A)\) such that \(\mathrm {CA}(G;A) = \langle \mathrm {ICA}(G;A) \cup V \rangle\).

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Jetzt einloggen Kostenlos registrieren

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriger Artikel Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models

Nächster Artikel Cellular automata on group sets and the uniform Curtis–Hedlund–Lyndon theorem

Metadaten
Literatur

Titel: Cellular automata and finite groups
Verfasst von: Alonso Castillo-Ramirez
Maximilien Gadouleau
Publikationsdatum: 30.09.2017
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 3/2019
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-017-9640-3

Dieser Inhalt ist nur sichtbar, wenn du eingeloggt bist und die entsprechende Berechtigung hast.

Springer Professional

Cellular automata and finite groups

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2019

UCNC 2018 special issue editorial

Variants of P systems with activation and blocking of rules

Computational completeness of simple semi-conditional insertion–deletion systems of degree (2,1)

Perturbations and phase transitions in swarm optimization algorithms

Enhancing particle swarm optimization with binary quantum wave modulation and joint guiding forces

A universal non-conservative reversible elementary triangular partitioned cellular automaton that shows complex behavior

Premium Partner