TY - CHAP

T1 - The fractal structure of cellular automata on Abelian groups

AU - Gütschow, Johannes

AU - Nesme, Vincent

AU - Werner, Reinhard F.

PY - 2010

Y1 - 2010

N2 - 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. Explaining the fractal structure of the spacetime diagrams of cellular automata is a much explored topic, but virtually all of the results revolve around a special class of automata, whose typical features include irreversibility, an alphabet with a ring structure, a global evolution that is a ring homomorphism, and a property known as (weakly) p-Fermat. The class of automata that we study in this article has none of these properties. Their cell structure is weaker, as it does not come with a multiplication, and they are far from being p-Fermat, even weakly. However, they do produce fractal spacetime diagrams, and we explain why and how.

AB - 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. Explaining the fractal structure of the spacetime diagrams of cellular automata is a much explored topic, but virtually all of the results revolve around a special class of automata, whose typical features include irreversibility, an alphabet with a ring structure, a global evolution that is a ring homomorphism, and a property known as (weakly) p-Fermat. The class of automata that we study in this article has none of these properties. Their cell structure is weaker, as it does not come with a multiplication, and they are far from being p-Fermat, even weakly. However, they do produce fractal spacetime diagrams, and we explain why and how.

M3 - Beitrag in Buch/Sammelwerk

SP - 51

EP - 70

BT - Proceedings of Automata 2010

A2 - Fatès, Nazim

A2 - Kari, Jarkko

A2 - Worsch, Thomas

ER -