Cellular automata over algebraic structures

Abstract: Let

G

be a group and

A

a set equipped with a collection of finitary operations. We study cellular automata

a u : A^{G} o A^{G}

that preserve the operations of

A^{G}

induced componentwise from the operations of

A

. We show that

a u

is an endomorphism of

A^{G}

if and only if its local function is a homomorphism. When

A

is entropic (i.e. all finitary operations are homomorphisms), we establish that the set

e x t E n d C A (G; A)

, consisting of all such cellular automata, is isomorphic to the direct limit of

e x t H o m (A^{S}, A)

, where

S

runs among all finite subsets of

G

. In particular, when

A

is an

R

-module, we show that

e x t E n d C A (G; A)

is isomorphic to the group algebra

e x t E n d (A) [G]

. Moreover, when

A

is a finite Boolean algebra, we establish that the number of endomorphic cellular automata over

A^{G}

admitting a memory set

S

is precisely

(k v e r t S v e r t)^{k}

, where

k

is the number of atoms of

A

.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Cellular automata over algebraic structures