2022/07/26 by Vincent Nesme, Nesme, Vincent
Computer Science · Mathematics · #11B85 #37B15 #Cellular Automata and Applications #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #F.1.1 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2207.13062
openalex publication_date 2022/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.