pipette
ESEspañol

Idempotence criteria for lazy cellular automata

Edgar Alcal\'{a}-Arroyo, Alonso Castillo-Ramirez, Maria G. Maga\~na-Ch\'avez, Luguis de los Santos Ba\~nos

Preprint

In the authors' words

A lazy cellular automaton is determined by a finite neighborhood containing the group identity, a pattern , and a writing symbol : its local rule changes the central symbol to precisely when the neighborhood pattern equals . For a nonempty set of positions where takes the value , we introduce two compatibility conditions on along the right translates , . We show that the existence of a compatible set is necessary for to be non-idempotent over every group, and that it is also sufficient whenever every position where takes the value commutes with every position where takes the value . In particular, compatibility characterizes non-idempotence over abelian groups, replacing a search over patterns on by a search over sets of positions where takes the value . Finally, for every dihedral group with , we construct an idempotent lazy cellular automaton that admits a compatible set, showing that the commutation hypothesis cannot simply be dropped.

Main resultLimitation the authors admit

Appeared: Friday, October 9. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 10 pages