论文标题
由蜂窝自动机产生的时空图的自动性自动化
Automaticity of spacetime diagrams generated by cellular automata on commutative monoids
论文作者
论文摘要
众所周知，某些蜂窝自动机的时空图具有分形结构：例如，帕斯卡尔的三角模量2生成了Sierpinski三角形。已经表明，只要蜂窝自动机是相对于该结构的形态，并且初始配置具有有限的支持，则可以在字母内赋予ABELIAN组的结构时发生此类模式。然后，时空图具有与K-自动性有关的属性。我们表明这些条件可以放松：阿贝尔组可以是可交换的单体，初始构型可以是k-Automation，并且时空图仍然具有相同的规律性。
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.
