众所周知,某些元胞自动机的时空图具有分形结构:例如模 2 下的帕斯卡三角形生成谢尔宾斯基三角形。已有研究表明,当字母表被赋予阿贝尔群结构、元胞自动机关于该结构是同态、且初始构型具有有限支撑时,此类模式可能出现;此时时空图具有与 k-自动性相关的性质。本文表明,这些条件可被放宽:阿贝尔群可替换为交换幺半群,初始构型可为 k-自动的,而时空图仍保持相同的正则性。
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.