Further results on generalized cellular automata
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909072635199488 |
|---|---|
| author | Castillo-Ramirez, Alonso Baños, Luguis de los Santos |
| author_facet | Castillo-Ramirez, Alonso Baños, Luguis de los Santos |
| contents | Given a finite set $A$ and a group homomorphism $ϕ: H \to G$, a $ϕ$-cellular automaton is a function $\mathcal{T} : A^G \to A^H$ that is continuous with respect to the prodiscrete topologies and $ϕ$-equivariant in the sense that $h \cdot \mathcal{T}(x) = \mathcal{T}( ϕ(h) \cdot x)$, for all $x \in A^G, h \in H$, where $\cdot$ denotes the shift actions of $G$ and $H$ on $A^G$ and $A^H$, respectively. When $G=H$ and $ϕ= \text{id}$, the definition of $\text{id}$-cellular automata coincides with the classical definition of cellular automata. The purpose of this paper is to expand the theory of $ϕ$-cellular automata by focusing on the differences and similarities with their classical counterparts. After discussing some basic results, we introduce the following definition: a $ϕ$-cellular automaton $\mathcal{T} : A^G \to A^H$ has the unique homomorphism property (UHP) if $\mathcal{T}$ is not $ψ$-equivariant for any group homomorphism $ψ: H \to G$, $ψ\neq ϕ$. We show that if the difference set $Δ(ϕ, ψ)$ is infinite, then $\mathcal{T}$ is not $ψ$-equivariant; it follows that when $G$ is torsion-free abelian, every non-constant $\mathcal{T}$ has the UHP. Furthermore, inspired by the theory of classical cellular automata, we study $ϕ$-cellular automata over quotient groups, as well as their restriction and induction to subgroups and supergroups, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_04926 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Further results on generalized cellular automata Castillo-Ramirez, Alonso Baños, Luguis de los Santos Group Theory Formal Languages and Automata Theory 37B15, 68Q80 Given a finite set $A$ and a group homomorphism $ϕ: H \to G$, a $ϕ$-cellular automaton is a function $\mathcal{T} : A^G \to A^H$ that is continuous with respect to the prodiscrete topologies and $ϕ$-equivariant in the sense that $h \cdot \mathcal{T}(x) = \mathcal{T}( ϕ(h) \cdot x)$, for all $x \in A^G, h \in H$, where $\cdot$ denotes the shift actions of $G$ and $H$ on $A^G$ and $A^H$, respectively. When $G=H$ and $ϕ= \text{id}$, the definition of $\text{id}$-cellular automata coincides with the classical definition of cellular automata. The purpose of this paper is to expand the theory of $ϕ$-cellular automata by focusing on the differences and similarities with their classical counterparts. After discussing some basic results, we introduce the following definition: a $ϕ$-cellular automaton $\mathcal{T} : A^G \to A^H$ has the unique homomorphism property (UHP) if $\mathcal{T}$ is not $ψ$-equivariant for any group homomorphism $ψ: H \to G$, $ψ\neq ϕ$. We show that if the difference set $Δ(ϕ, ψ)$ is infinite, then $\mathcal{T}$ is not $ψ$-equivariant; it follows that when $G$ is torsion-free abelian, every non-constant $\mathcal{T}$ has the UHP. Furthermore, inspired by the theory of classical cellular automata, we study $ϕ$-cellular automata over quotient groups, as well as their restriction and induction to subgroups and supergroups, respectively. |
| title | Further results on generalized cellular automata |
| topic | Group Theory Formal Languages and Automata Theory 37B15, 68Q80 |
| url | https://arxiv.org/abs/2310.04926 |