A generalization of cellular automata over groups

DOI10.1080/00927872.2023.2177663MaRDI QIDQ6039089zbMATH OpenFDO

Authors Alonso Castillo-Ramirez, Miguel Sanchez-Alvarez, Luis Angel Zaldívar-Corichi

Publication date 3 May 2023

Published in Communications in Algebra (Search for Journal in Brave)

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

zbMATH Keywords

cellular automataCurtis-Hedlund theoremmonoid of cellular automataouter automorphism group

Mathematics Subject Classification ID

Algebraic monoids (20M32) Dynamical aspects of cellular automata (37B15)

Abstract: Let $G$ be a group and let $A$ be a finite set with at least two elements. A cellular automaton (CA) over $A^G$ is a function $au:A^{G}o{A}^G$ defined via a finite memory set $SsubseteqG$ and a local function $mu:A^{S}oA$. The goal of this paper is to introduce the definition of a generalized cellular automaton (GCA) $au:A^{G}o{A}^H$, where $H$ is another arbitrary group, via a group homomorphism $phi:HoG$. Our definition preserves the essence of CA, as we prove analogous versions of three key results in the theory of CA: a generalized Curtis-Hedlund Theorem for GCA, a Theorem of Composition for GCA, and a Theorem of Invertibility for GCA. When $G=H$, we prove that the group of invertible GCA over $A^G$ is isomorphic to a semidirect product of $extAut(G{)}^{op}$ and the group of invertible CA. Finally, we apply our results to study automorphisms of the monoid $extCA(G;A)$ consisting of all CA over $A^G$. In particular, we show that every $phiinextAut(G)$ defines an automorphism of $extCA(G;A)$ via conjugation by the invertible GCA defined by $phi$, and that, when $G$ is abelian, $extAut(G)$ is embedded in the outer automorphism group of $extCA(G;A)$.

Recommendations

• On Finite Monoids of Cellular Automata
• Groups and Monoids of Cellular Automata
• Cellular automata over algebraic structures
• scientific article; zbMATH DE number 6149843
• Cellular automata on a G-set

Cites work

• An Introduction to Symbolic Dynamics and Coding
• Cellular automata and groups
• Elementary, finite and linear vN-regular cellular automata
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• scientific article; zbMATH DE number 726524 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)

Cited in

(21)

• The Pascal matroid as a home for generating sets of cellular automata configurations defined by quasigroups
• Permutive one-way cellular automata and the finiteness problem for automaton groups
• Bounding the minimal number of generators of groups and monoids of cellular automata
• Linear cellular automata over modules of finite length and stable finiteness of group rings
• Generalized Gandy-Păun-Rozenberg Machines for Tile Systems and Cellular Automata
• CELLULAR AUTOMATA OVER SEMI-DIRECT PRODUCT GROUPS: REDUCTION AND INVERTIBILITY RESULTS
• scientific article; zbMATH DE number 5343230 (Why is no real title available?)
• scientific article; zbMATH DE number 1136074 (Why is no real title available?)
• scientific article; zbMATH DE number 6149843 (Why is no real title available?)
• Cellular automata over algebraic structures
• Universal groups of cellular automata
• Generalized linear cellular automata in groups and difference Galois theory
• scientific article; zbMATH DE number 5582847 (Why is no real title available?)
• Cellular automata on a G-set
• Groups and Monoids of Cellular Automata
• A note on cellular automata
• Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption
• Further results on generalized cellular automata
• Cellular automata on group sets and the uniform Curtis-Hedlund-Lyndon theorem
• The Garden of Eden theorem over generalized cellular automata
• Categorical products of cellular automata

This page was built for publication: A generalization of cellular automata over groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6039089)