论文
arXiv
CellularAutomata
中文标题
交换幺半群上元胞自动机生成的时空图的自动性
English Title
Automaticity of spacetime diagrams generated by cellular automata on commutative monoids
Vincent Nesme
发布时间
2022/7/27 01:34:12
来源类型
preprint
语言
en
摘要
中文对照

众所周知,某些元胞自动机的时空图具有分形结构:例如,模 2 的帕斯卡三角形生成谢尔宾斯基三角形。已有研究表明,当符号集被赋予阿贝尔群结构、且该元胞自动机关于此结构是同态、初始构型具有有限支撑时,此类模式可能出现。此时,其时空图具有与 k-自动性相关的性质。我们证明这些条件可予弱化:阿贝尔群可替换为交换幺半群,初始构型可为 k-自动的,而时空图仍保持相同的正则性。

English Original

It is well-known that the spacetime diagrams of some cellular automata have a fractal structure: for instance Pascal's triangle modulo 2 generates a Sierpinski triangle. It has been shown that such patterns can occur when the alphabet is endowed with the structure of an Abelian group, provided the cellular automaton is a morphism with respect to this structure and the initial configuration has finite support. The spacetime diagram then has a property related to k-automaticity. We show that these conditions can be relaxed: the Abelian group can be a commutative monoid, the initial configuration can be k-automatic, and the spacetime diagrams still exhibit the same regularity.

我的阅读记录

正在加载阅读记录…

元数据
arXiv2207.13062v4
来源arXiv
类型论文
抽取状态raw
关键词
CellularAutomata
cs.DM
cs.FL
math.DS