Flexible toggles and symmetric invertible asynchronous elementary cellular automata

DOI10.1016/J.DISC.2018.05.018zbMATH Open1392.05107arXiv1511.06966OpenAlexW2963508112WikidataQ129723159 ScholiaQ129723159MaRDI QIDQ724839FDOQ724839

Authors: Colin Defant

Publication date: 26 July 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

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