Flexible toggles and symmetric invertible asynchronous elementary cellular automata

Permutations, words, matrices (05A05) Cellular automata (computational aspects) (68Q80) Graph theory (05C99) Group actions on combinatorial structures (05E18)

Abstract: A sequential dynamical system (SDS) consists of a graph

G

with vertices

v_{1}, v_{2}, l d o t s, v_{n}

, a state set

A

, a collection of "vertex functions"

{f_{v_{i}}}_{i = 1}^{n}

, and a permutation

p i i n S_{n}

that specifies how to compose these functions to yield the SDS map

[G, {f_{v_{i}}}_{i = 1}^{n}, p i] c o l o n A^{n} o A^{n}

. In this paper, we study symmetric invertible SDS defined over the cycle graph

C_{n}

using the set of states

m a t h b b F_{2}

. These are, in other words, asynchronous elementary cellular automata (ECA) defined using ECA rules 150 and 105. Each of these SDS defines a group action on the set

m a t h b b F_{2}^{n}

of

n

-bit binary vectors. Because the SDS maps are products of involutions, this relates to emph{generalized toggle groups}, which Striker recently defined. In this paper, we further generalize the notion of a generalized toggle group to that of a emph{flexible toggle group}; the SDS maps we consider are examples of Coxeter elements of flexible toggle groups. Our main result is the complete classification of the dynamics of symmetric invertible SDS defined over cycle graphs using the set of states

m a t h b b F_{2}

and the identity update order

p i = 123 c d o t s n

. More precisely, if

T

denotes the SDS map of such an SDS, then we obtain an explicit formula for

| e x t {P e r}_{r} (T) |

, the number of periodic points of

T

of period

r

, for every positive integer

r

. It turns out that if we fix

r

and vary

n

and

T

, then

| e x t {P e r}_{r} (T) |

only takes at most three nonzero values.

Recommendations

Cites work

Cited in

(1)

Dynamical algebraic combinatorics, asynchronous cellular automata, and toggling independent sets

This page was built for publication: Flexible toggles and symmetric invertible asynchronous elementary cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q724839)