论文
arXiv
CellularAutomata
中文标题
群-字母表元胞自动机的函子分析
English Title
Functorial Analysis of Group-Alphabet Cellular Automata
François Huard, Nathan Dion Larivière
发布时间
2026/10/30 05:46:30
来源类型
preprint
语言
en
摘要
中文对照

设 $G$ 为一个群,$n \in \mathbb{N}$。我们考虑长度为 $n$、字母表为 $G$ 的一维元胞自动机,其具有周期性边界条件,且局部规则 $\varphi$ 由字(words)给出。我们构造了一个从 $\mathbf{Grp}$(群范畴或任何类似的代数结构范畴)到带基点有向图范畴的函子 $F$,并证明了其忠实性。我们引入了所有此类群-字母表元胞自动机的状态转移图的像范畴 $\mathcal{C}_{n,\varphi}$,并证明 $F$ 是该范畴上的等价。因此,我们研究了 $\mathbf{Grp}$ 中的范畴结构在元胞自动机语境下的转化,并给出了如何将同调代数的标准方法应用于元胞自动机的示例。此外,还给出了 $\mathcal{C}_{n,\varphi}$ 中积的图论构造,以及该积中环长度和重数的公式。当 $G$ 为阿贝尔群时,可得出状态转移图的进一步结构性质,我们将这些结果与非阿贝尔情形的反例进行了对比。

English Original

Let $G$ be a group and let $n\in\mathbb N$. We consider one-dimensional cellular automata of length $n$ over the alphabet $G$, with periodic boundary conditions and with local rules $φ$ given by words. We construct a functor $F$ from $\mathbf{Grp}$, the category of groups (or any similar algebraic structure), to the category of pointed digraphs, and show its faithfulness. We introduce the image category $\mathcal C_{n,φ}$ of state transition graphs of all such group-alphabet cellular automata, and show $F$ is an equivalence onto this category. Consequently we investigate the translation of categorical structures in $\mathbf{Grp}$ in terms of automata, and give examples of how standard methods of homological algebra may now be applied to automata. Additionally, a graph-theoretical construction of the product in $\mathcal C_{n,φ}$ is given, together with a formula for cycle lengths and multiplicities in this product. When $G$ is abelian, further structural properties of state transition graphs follow, and we contrast these results with non-abelian counterexamples.

我的阅读记录

正在加载阅读记录…

元数据
arXiv2610.41013v1
来源arXiv
类型论文
抽取状态raw
关键词
CellularAutomata
math.GR
cs.FL
math.CO
math.CT
math.DS