pipette
ENEnglish

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

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 10 pages