Flexible toggles and symmetric invertible asynchronous elementary cellular automata

A sequential dynamical system (SDS) consists of a graph with vertices v(1),...,v(n), a state set A, a collection of vertex functions {f(vi)}(i=1)(n), and a permutation pi is an element of S-n that specifies how to compose these functions to yield the SDS map [G, {f(vi)}(i=1)(n), pi] : A(n)-> A(n). In this paper, we study symmetric invertible SDS defined over the cycle graph C-n using the set of states 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 F-2(n) of n-bit binary vectors. Because the SDS maps are products of involutions, this relates to generalized toggle groups, which Striker recently introduced. In this paper, we further generalize the notion of a generalized toggle group to that of a 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 F-2 and the identity update order pi = 123...n. More precisely, if T denotes the SDS map of such an SDS, then we obtain an explicit formula for vertical bar Per(r)(T)vertical bar, 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 vertical bar Per(r)(T)vertical bar only takes at most three nonzero values. (C) 2018 Elsevier B.V. All rights reserved.