Flexible toggles and symmetric invertible asynchronous elementary cellular automata |
| |
Authors: | Colin Defant |
| |
Institution: | Princeton University, Fine Hall, 304 Washington Rd., Princeton, NJ 08544, United States |
| |
Abstract: | A sequential dynamical system (SDS) consists of a graph with vertices , a state set , a collection of “vertex functions” , and a permutation that specifies how to compose these functions to yield the SDS map . In this paper, we study symmetric invertible SDS defined over the cycle graph using the set of states . 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 of -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
and the identity update order . More precisely, if denotes the SDS map of such an SDS, then we obtain an explicit formula for , the number of periodic points of of period , for every positive integer . It turns out that if we fix
and vary and , then only takes at most three nonzero values. |
| |
Keywords: | Sequential dynamical system Parity function Asynchronous cellular automaton Generalized toggle group Flexible toggle group Orbit structure |
本文献已被 ScienceDirect 等数据库收录! |
|