{'fraction_non_alphanumeric': 0.044153990741063034, 'fraction_numerical': 0.0337986007170455, 'mean_word_length': 3.5182826138240153, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 73, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dynamics Groups of Asynchronous Cellular Automata

We say that a finite asynchronous cellular automaton (or more generally, any sequential dynamical system) is pi-independent if its set of periodic points are independent of the order that the local functions are applied. In this case, the local functions permute the periodic points, and these permutations generate the dynamics group. We have previously shown that exactly 104 of the possible 256 cellular automaton rules are pi-independent. In this article, we classify the periodic states of these systems and describe their dynamics groups, which are quotients of Coxeter groups. The dynamics groups provide information about permissible dynamics as a function of update sequence and, as such, connect discrete dynamical systems, group theory, and algebraic combinatorics in a new and interesting way. We conclude with a discussion of numerous open problems and directions for future research.

A cellular automaton, or CA, is a classical discrete dynamical system defined over a regular grid of cells. Every cell takes on one of a finite number of states and has an update rule that only depends on its state and the states of its neighbors. At every discrete time step, the update rules are simultaneously applied. More recent work has investigated sequential dynamical systems defined over arbitrary finite graphs where the update rules are applied asynchronously. (See [3] for a detailed bibliography.) The special case where Y is a circular graph, there are only two vertex states, and the update rules are all the same is the class of elementary asynchronous cellular automata or ACAs. There are 256 possible update rules. In an earlier article ( [2]) we proved that exactly 104 of these give rise to an ACA whose periodic states are independent of the update order, a property independent of the size of the underlying graph. In this article we describe the periodic states and the dynamics group for each ω-independent ACA identified in [2].
The article is structured as follows. Sections 1, 2 and 3 contain background definitions, notations, and results. Section 4 studies ACAs whose dynamics groups are trivial, Section 5 focuses on Wolfram rules that are invertible, and Section 6 investigates the remaining cases. The results are summarized in Tables 1, 3, and 5.

Sequential Dynamical Systems
A sequential dynamical system, or SDS, is a discrete dynamical system with three components: an undirected graph Y , a list of update rules F Y , and an update order ω. Definition 1.1 (Graph conventions). Let Y be a simple undirected graph with n vertices labeled from 1 to n, and recall that the neighbors of a vertex are those vertices connected to it by an edge. If F is a finite field and every vertex is assigned a value from F, then a global state of the system is described by an n-tuple y whose i th coordinate indicates the current state of the vertex i. The set of all possible states is the vector space F n . Definition 1.2 (Local functions). A function F : F n → F n is called Y -local at i if for each y ∈ F n (1) F (y) only alters the i th coordinate of y and (2) the new value of the i th coordinate only depends on the coordinates of y corresponding to i and its neighbors in Y .
Other names for such a function are a local function or an update rule. We use F Y to denote a list with one local function for each vertex of Y . More precisely, F Y = (F 1 , F 2 , . . . , F n ) where F i is a function that is Y -local at i. Definition 1.3 (Restricted local functions). If i is a vertex with k neighbors in Y , then corresponding to each function F that is Y -local at i, we define a function f : F k+1 → F where the domain is restricted to the coordinates corresponding to i and its neighbors, and the output is the new value F would assign to the i th coordinate under these conditions. The functions F and f contain the same information packaged differently and each determines the other. Both have their uses. Functions such as F can be readily composed, but functions such as f are easier to explicitly describe. Definition 1.4 (Update orders). An update order ω is a finite sequence of numbers chosen from the set {1, . . . , n}. If every number 1 ≤ i ≤ n occurs at least once, we say it is fair and if every number occurs exactly once, then it is simple. We use the notation ω = (ω 1 , ω 2 , . . . , ω m ) with m = |ω|. Of course, m ≥ n when ω is fair and m = n when ω is simple. Let W Y denote the collection of all update orders and let S Y denote the subset of simple update orders. The subscript Y indicates that we are thinking of the numbers in these sequences as vertices in the graph Y . Definition 1.5 (Sequential dynamical systems). A sequential dynamical system, or SDS, is a triple (Y, F Y , ω) consisting of an undirected graph Y , a list of local functions F Y , and a fair update order ω ∈ W Y . If ω is the sequence (ω 1 , ω 2 , . . . , ω m ), then we construct the SDS map [F Y , ω] : F n → F n as the composition [F Y , ω] := F ωm • · · · • F ω 1 .
The main goal is to understand the dynamics of the SDS map, i.e., its behavior under iteration. for all simple update orders π, π ′ ∈ S Y . When F Y is ω-independent, we write Per(F Y ) instead of Per[F Y , ω].
In the case of ω-independence we may -by abuse of notation -let the list of Y -local functions F Y stand for the entire SDS. When F Y is ω-independent, its local functions permute the elements of Per(F Y ). Proposition 1.7 (Permuting periodic states). If F Y is ω-independent and P = Per(F Y ), then for each i, F i (P ) = P . In particular, the restriction of F i to P is a permutation.
Proof. Let ω = (ω 1 , ω 2 , . . . , ω m ) be a fair update order with ω 1 = i and let σ be the modified update order with ω 1 moved from the first to last: σ = (ω 2 , ω 3 , . . . , ω m , ω 1 ). Since for all k, and by hypothesis [F Y , ω] k (F n ) = [F Y , σ] k (F n ) = P for all sufficiently large k, we find that F i (P ) ⊂ P . More explicitly, for large enough k, Moreover, since [F Y , ω](P ) = P , the restriction of F i to P is injective, and F i (P ) = P .
When F Y is ω-independent, we write F * i and [F Y , ω] * to denote the restrictions of these maps to Per(F Y ). By Proposition 1.7 all such maps are permutations. Note that ωindependence focuses on the periodic states as a set rather than how these states are permuted. In particular, when an ω-independent F Y is paired with two different update orders ω and σ, the permutations [F Y , ω] * and [F Y , σ] * are often distinct. These various permutations can be used to construct a group encoding all of the possible dynamics [3].
It should be clear that when U and V are sets of update orders and U is contained in , are special cases of particular interest. Note that DG(F Y ) contains and is generated by the bijections F * i .

Asynchronous Cellular Automata
The SDSs we focus on are defined over circular graphs, they have only two possible vertex states, and all the local functions are identically defined. These asynchronous cellular automata, or ACAs, are an asynchronous version of the classical finite elementary cellular automata. Even in such a restrictive situation there are many interesting dynamical behaviors.
Definition 2.1 (Circular graphs and vertex states). Let Y = Circ n denote the circular graph with vertex set {1, . . . , n} (viewed as residue classes mod n) and edges connecting i and i + 1 mod n. To avoid trivialities, we always assume n > 3. Each vertex has two possible states that we identify with F 2 = {0, 1}, the field of size 2.
Definition 2.2 (Wolfram rules). Let F i : F n 2 → F n 2 be a function Circ n -local at i and let f i : F 3 2 → F 2 be its restricted form. Because the neighbors of i are i − 1 and i + 1, it is conventional to list these coordinates in ascending order in the domain of f i , keeping in mind that all subscripts are viewed mod n. The function F i , henceforth referred to as a Wolfram rule, updates the value of y i based on the value of the triple (y i−1 , y i , y i+1 ) and it is completely determined by how the i th coordinate is updated in these eight possible situations. In other words, F i is completely described by the following table.
y i−1 y i y i+1 111 110 101 100 011 010 001 000 f i (y i−1 , y i , y i+1 ) a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 More concisely, the 2 8 = 256 possible Wolfram rules can be indexed by an 8-digit binary number a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 , or by its decimal equivalent k = a i 2 i . There is thus a Wolfram rule k for each integer 0 ≤ k ≤ 255. Definition 2.3 (Asynchronous cellular automata). We write Wolf (k) i to denote the update rule F i : F n → F n corresponding to k and Wolf (k) n for the list (Wolf 2 , . . . , Wolf (k) n ) of update rules. For each fair update order ω the SDS (Circ n , Wolf (k) n , ω) is called an asynchronous cellular automaton, or ACA. If Wolf (k) n is ω-independent for all n > 3, we say Wolfram rule k is ω-independent.
When Wolf (k) n is ω-independent, let P n,k = Per(Wolf (k) n ) denote its periodic states and let G n,k = DG(Wolf (k) n ) denote its dynamics group. We usually suppress the dependence on n and write simply P k and G k . In this notation, our goal is to describe the set P k and the group G k for each ω-independent Wolfram rule. In [2] we proved the following result. 1, 4, 5, 8, 9, 12, 13, 28, 29, 32, 40, 51, 54, 57, 60, 64, 65, 68, 69, 70, 71, 72, 73, 76, 77, 78, 79, 92, 93, 94, 95, 96, 99, 102, 105, 108, 109, 110, 111, 124, 125, 126, 127, 128, 129, 132, 133, 136, 137, 140, 141, 147, 150, 152, 153, 156, 157, 160, 164, 168, 172, 184, 188, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 204, 205, 206, 207, 216, 218, 220, 221, 222, 223, 224, 226, 228, 230, 232, 234, 235, 236, 237, 238, 239, 248, 249, 250, 251, 252, 253, 254, 255}. In [2] we also defined the inversion, reflection, and inversion-reflection of an ACA. Loosely speaking, inversion systematically swaps the roles of 0 and 1, reflection systematically switches left and right, and inversion-reflection does both at once. The inversion, reflection, or inversion-reflection of an ω-independent Wolfram rule is still ω-independent, it has a corresponding set of periodic states and an isomorphic dynamics group. This should not be surprising since all we have done is relabel the underlying states on which the local functions act. Rules related in this manner are dynamically equivalent. When the 256 Wolfram rules are partitioned into classes of rules related by reflection, inversion or both, there are 88 equivalence classes. The 104 rules listed in Theorem 2.4 belong to 41 such classes and thus we only need to describe P k and G k for 41 representative values of k.  Finally, because the binary notation is cumbersome and the decimal notation is opaque, we introduce (as in [2]) a concise symbolic tag for each Wolfram rule. Definition 2.6 (Tags). The four functions from F 2 to F 2 can be described by their behavior: the value never changes, the value always changes, both elements go to 0, or both elements go to 1. We refer to these functions by the evocative symbols -, x, 0, and 1, respectively. The restricted local form of Wolfram rule k is completely determined by the four functions from F 2 to F 2 that result when the values of y i−1 and y i+1 are held constant. Let t 0 , t 1 , t 2 and t 3 be the symbols for these functions in the four cases y i−1 = y i+1 = 0, y i−1 = 0 and y i+1 = 1, y i−1 = 1 and y i+1 = 0, and y i−1 = y i+1 = 1, respectively. The tag of k is the string t 3 t 2 t 1 t 0 . Note that t 0 depends on the values of a 0 and a 2 , t 1 depends on a 1 and a 3 , t 2 depends on a 4 and a 6 , and t 3 depends on a 5 and a 7 . The numbering and the order of the t i 's has been chosen to match the traditional binary representation as closely as possible, easing the transition between the two. As an illustration, the reader can verify that Wolfram rule 29 has binary notation 00011101 and tag 0x-1.
Patterns among the Wolfram rules are easier to discern when using tags.
Remark 2.7 (Tags and dynamic equivalence). On the level of tags, reflections switch the order of t 1 and t 2 . For example, the reflection of rule 0-1x is 01-x. To describe the effect that inversion has on tags, we define a map ι : {1, 0, −, x} → {1, 0, −, x} that fixesand x while switching 0 and 1. When Wolfram rule k has tag t 3 t 2 t 1 t 0 , its inversion has tag ι(t 0 )ι(t 1 )ι(t 2 )ι(t 3 ). For example, the inversion of rule 0-1x is x0-1. See [2] for a more detailed explanation.
Remark 2.8 (Tags and other SDSs). If (Y, F Y , ω) is an SDS with only two vertex states, then each update rule F i can be described be a set of symbols similar to the tag used to describe Wolfram rules. More specifically, if vertex i has exactly k neighbors, then the restricted local form of F i is a function f i : F k+1 2 → F 2 and this function is determined by the 2 k functions from F 2 to F 2 that result when the values of the neighbors of i are held constant. In particular, the behavior of F i is determined by the corresponding 2 k symbols, selected from {1, 0, −, x}.

Groups
In preparation for our investigation of dynamics groups we recall a few basic facts about group actions and Coxeter groups.  Faithful actions). Let G be a group acting on a set X. The action is called faithful if nontrivial elements act nontrivially. When this is the case, we can view G as a subgroup of Sym X . Note that groups generated by permutations act faithfully on their underlying sets almost by definition. In particular, for any ω-independent SDS F Y , the action of its dynamics group DG(F Y ) on its periodic states Per(F Y ) is faithful.
One of the key features of a group acting on a set is its orbit structure. Definition 3.2 (Orbits). Let G be a group acting on a finite set X. The orbit of a point x ∈ X is the subset of points to which it can be sent by an element of G. Thus the orbit of x is Gx = {g · x | g ∈ G}. Because two orbits are either identical or disjoint, the collection of all orbits {Gx | x ∈ X} partitions X into equivalence classes X = X 1 ⊔ X 2 ⊔ . . . ⊔ X ℓ . When there is only one orbit we say the action is transitive.
As we investigate the faithful action of G n,k on P n,k , we use o n,k to denote the number of orbits under this action. And, as with G k and P k , we usually suppress the dependence on n and write o k instead. The orbit structure is of interest because distinct orbits provide information about the structure of the group. Definition 3.3 (Subdirect products). If G acts faithfully on a finite set X with orbits X 1 , X 2 , . . . , X ℓ then G can be viewed as a subgroup of Sym X 1 × Sym X 2 × · · · × Sym X ℓ . To see this note that when an element of G is written in disjoint cycle notation, each cycle must permute elements within a single orbit. Thus every g ∈ G can be viewed as a ℓ-tuple g = (g 1 , g 2 , . . . , g ℓ ) where g i ∈ Sym(X i ). Even better, we can replace each Sym X i with G i , the image of G under the projection to the i th factor. As a result G embeds in a direct product G 1 × G 2 × · · · × G ℓ , where the projection to each factor is onto. We call G a subdirect product of G 1 , G 2 ,. . . , and G ℓ , and the G i s are called the orbit groups of G.
For an illustration of these concepts, consider a group generated by a single permutation.
Example 3.4 (Cyclic groups). The permutation (1, 2)(3, 4, 5)(6, 7, 8, 9) generates a cyclic group G of order 12. It naively belongs to Sym 9 , a group of size 362880, but based on its orbit structure it lives inside the much smaller group Sym 2 ×Sym 3 ×Sym 4 of size 288. And if we cut down each factor to the image under projection, then G embeds in Z 2 × Z 3 × Z 4 , a noncyclic group of order 24 that contains G as an index 2 subgroup.
One caution is that G can be a subdirect product of groups without splitting as a direct product. Consider the cyclic group G generated by (1, 2, 3)(4, 5, 6). The procedure described above embeds G as a subdirect product of Z 3 and Z 3 , but G itself is simple. The second set of results we need to recall are about Coxeter groups. A Coxeter group is a group generated by involutions with a presentation of a particularly simple form.
Definition 3.5 (Coxeter groups). Let W be a group generated by a finite subset S = {s 1 , . . . , s n } and let m ij ∈ N ∪ {∞} denote the order of the product s i s j . The pair (W, S) is called a Coxeter system if the elements of S are involutions (i.e., m ii = 1) and the presentation s 1 , . . . , s n | (s i s j ) m ij = 1 is a presentation of W . Note that when m ij = ∞, no relation is included for this pair of indices and that trivially m ij = m ji ≥ 2 for all i = j.
The letters W and S are those traditionally used for a Coxeter group and its Coxeter generators. Coxeter groups have an incredibly rich theory and close connections with many areas of mathematics. By comparison, the results we need are fairly modest. Before listing these results, we first establish the relevance of Coxeter groups to our investigation of dynamics groups.

Proposition 3.6 (Coxeter quotients). Every group generated by a finite set of involutions can be viewed as a quotient of a Coxeter group in a natural way.
Proof. Let G be a group and let S = {s 1 , . . . , s n } be a subset of involutions that generate G. If we define m ij as the order of s i s j in G and we define W as the group with presentation s 1 , . . . , s n | (s i s j ) m ij = 1 then there is a natural surjective homomorphism from W to G sending s i to s i . Theorem 3.7 (Dynamics groups as Coxeter quotients). If F Y is an ω-independent SDS with only two possible vertex states, then F * i , the restriction of a local function to the periodic states Per(F Y ), is either trivial or an involution. As a consequence, the dynamics group DG(F Y ) is either trivial or a quotient of a Coxeter group.
Proof. The key observation is that because F * i can only change the i th coordinate, the size of the cycles in its cycle structure are bounded by the number of possible vertex states. For the second assertion, note that when the dynamics group DG(F Y ) is nontrivial, it is generated by the nontrivial F * i and then apply Proposition 3.6. The case when DG(F Y ) is trivial can be recognized by its fixed points.
Definition 3.8 (Fixed points). If y ∈ Per(F Y ) is fixed under some simple update order π, then y must be fixed by each local function F i . This is because a change to the i th coordinate cannot be corrected by the other local functions in the composition that produces [F Y , π]. As a consequence, y is fixed under all update orders ω. We write Fix(F Y ) to denote the set of periodic states fixed by some simple update order, or equivalently, the set of periodic states fixed by all local functions F i (and thus fixed by all update orders).

Proposition 3.9 (Trivial groups and fixed points). An
then there is a periodic state y and a local function F i such that F i (y) = y. For this i, F * i is nontrivial and thus DG(F Y ) is nontrivial. When the dynamics group DG(F Y ) is nontrivial, the graph Y can be used to describe the Coxeter group of which it is a quotient. Definition 3.10 (Coxeter diagrams). The presentation of a Coxeter group is often summarized in graphical form as follows. Given a Coxeter system (W, S) we construct a graph with vertices indexed by S and an edge labeled m ij connecting vertex i and j whenever m ij > 2. The Coxeter presentation of W can be easily reconstructed from this edge-labeled graph called the Coxeter diagram of W . Definition 3.11 (Coxeter diagrams for dynamics groups). If F Y is an ω-independent SDS with only two possible vertex states and a nontrivial dynamics group DG(F Y ), then the Coxeter diagram for the Coxeter group of which DG(F Y ) is a quotient can be obtained from Y in three easy steps. First remove every vertex i (and the edges connected to it) for which F * i is trivial. Next, remove the edges between i and j when m ij = 2 (or equivalently when F * i and F * j commute). And finally, add the label m ij to each remaining edge. Finally, we note that because F * i and F * j can only alter coordinates i and j, the cycles of F * i • F * j have size at most 4. Thus each m ij divides 12, the gcd of possible cycle lengths.
Definition 3.12 (Coxeter label). The Coxeter diagram for the Coxeter group mapping onto the dynamics group of an ω-independent Wolfram rule k is particularly simple because of the symmetry of construction of the Wolf (k) we see that one F * i is nontrivial iff they are all nontrivial and the order of F * i • F * i+1 is a constant independent of i and n. We call this constant c k , the Coxeter label of Wolfram rule k, and as noted above, the value of c k must divide 12. When G k is nontrivial all vertices remain. If c k > 2, all edges remain and are labeled c k .
The result we need from Coxeter theory is an identification of certain classes of groups.

Remark 3.13 (Small Coxeter labels). If Wolf (k)
n is ω-independent, G k is nontrivial, and c k = 2, then G k is a quotient of the Coxeter group Z n 2 defined by an edgeless Coxeter diagram. If Wolf (k) n is ω-independent, G k is nontrivial, and c k = 3, then G k is a quotient of the Coxeter group defined by a circular Coxeter diagram with edges labeled 3. This group is the affine Coxeter group of type A n−1 but since it is the only Coxeter group we consider without a pre-existing common name (such as Sym n ), we call this group Cox n . Its structure is well-known. Let (Z n ⊥ 1) denote the subset of Z n perpendicular to the vector 1 = (1, 1, . . . , 1), i.e., the set of vectors whose coordinates sum to 0, and note that these form a subgroup under vector addition. If we let Sym n act on (Z n ⊥ 1) by permuting coordinates in the natural way, then Cox n is isomorphic to the semidirect product (Z n ⊥ 1) ⋊ Sym n . Geometrically, it is the group of isometries of the Euclidean space R n that preserve the sum of the coordinates and send vectors with all integer coordinates to other such vectors.
For the sake of concreteness, we select the following explicit isomorphism between Cox n and (Z n ⊥ 1) ⋊ Sym n . To avoid confusion we use x = (x 1 , x 2 , . . . , x n ) for an element of (Z n ⊥ 1) and reserve y = (y 1 , y 2 , . . . , y n ) for states. Let s 1 , s 2 , . . . , s n , denote the Coxeter generators of Cox n . For each i < n let s i be the element that switches x i and x i+1 , and let s n send x = (x 1 , x 2 , . . . , x n−1 , x n ) to (x n −1, x 2 , . . . , x n−1 , x 1 +1). The natural map to Sym n only remembers how the subscripts on the x i s are permuted and ignores the translational component. An element in the kernel of the map Cox n → Sym n is called a pure translation since it merely adds to x a vector in (Z n ⊥ 1). These pure translations are generated by the elements T i in Cox n defined as follows. The element T 1 = s 1 s 2 · · · s n−1 s n s n−1 · · · s 3 s 2 and the other T i are obtained by consistently shifting the subscripts. In terms of its effect on an element x ∈ (Z n ⊥ 1), T 1 adds the vector −1, 0, . . . , 0, 1 . More generally, T i adds 1 to x i−1 and subtracts 1 from x i . The pure translations are generated by these commuting T i which are nearly independent. The sole nontrivial relation they satisfy is that T 1 + T 2 + · · · T n is trivial.

Trivial groups
In this section we discuss ω-independent Wolfram rules with trivial dynamics group. Of the 41 representative Wolfram rules, 26 of them fall into this category. For rule 204 (with tag ----), this is immediate since as its tag indicates no local function ever alters the current state. For the other 25 rules the triviality of G k is a consequence of Proposition 3.9.
More specifically, several lemmas in [2] established conditions under which all periodic points are fixed. These lemmas are listed below along with the representative rules they cover.
• • Lemma 6.3 (Rules 152 and 184) Even though the group G k is trivial in each case, the set P k remains to be calculated. (Many of the proofs in [2] are nonconstructive and do not determine the set of periodic states explicitly.) Because periodic states and fixed states coincide for these rules, there is a relatively straightforward procedure for finding them: simply look at the definition of the rule and remove all states containing triples y i−1 y i y i+1 of consecutive states that would lead to an alteration. Clearly the removed states are not fixed by all local functions and do not belong to P k , and any states remaining at the end of this procedure are fixed by every local function and do belong in P k . This prompts the following definitions.   4.3 (Why these words). The words we have chosen to abbreviate are those needed to efficiently describe the periodic sets of the 41 representative rules. The words B, C, D and E are triples that need to be avoided, while the words A and F deserve additional explanation. Avoiding the triple '110' is equivalent to avoiding the subword '11' while allowing the state 1, and avoiding the triple '011' leads to the same conditions. It thus makes sense to abbreviate the word '11' and treat the state 1 separately. The word F = '1100' is only needed to describe P 28 and P 29 , so we postpone our discussion of this abbreviation until Section 6. We note that this is the only abbreviated word that is not left-right symmetric.
The periodic sets for the 26 representative Wolfram rules under discussion, calculated as described above, are listed in Table 1. The tag of rule k, along with the decimal of its inversion, reflection and inversion-reflection are also included. Finally we turn to a calculation of the number of orbits for each of these rules.  for each n are the coefficients of an easily calculated rational generating function [5]. As a consequence, they satisfy a constant coefficient recurrence relation. The last statement also follows from [3, Theorem 5.3, p. 132].
In all but two cases these negative descriptions can be reformulated as positive ones that allow us to compute the recurrence with ease. For example, the states in N A are those without adjacent 1s and every such state can be uniquely decomposed into subwords of the form '0' and '10' that we call "tiles". Counting these involve the Lucas numbers and, indirectly, the Fibonacci numbers.
This analysis of the size of N A easily extends to those cases with a tiling description supplementing the description by words to avoid. The tiles in each case and the corresponding recurrence relation are listed in Table 2. The final column is a reference to the appropriate entry in Neil Sloane's Online Encyclopedia of Integer Sequences [4]. The remaining two cases, N D and N DE , are classical situations where isolated 1s and/or isolated 0s are to be avoided. See the references listed in their entries in [4] for further details.

Invertible rules
We now turn our attention to Wolfram rules where every state is periodic. Of the 41 representative Wolfram rules, 9 of them fall into this category. Our results for these 9 rules are summarized in Table 3. Note that the more complicated numbers and groups o k and G k are not explicitly listed in the table and only described in the text. As a convention, when it is clear that rule k is the rule under discussion, we use F i instead of the more cumbersome Wolf (k) i to denote the rule that updates the i th coordinate. Finally, recall that the Coxeter label c k must be a divisor of 12 and note that all six possible values occur among these "invertible" rules.  Table 3. Invertible rules.
note that when every update rule is bijective, their composition is a permutation and every state is periodic. Conversely, if every state is periodic, then the SDS maps are permutations and the only way this can happen is when every update rule is at least injective and hence bijective.
It is also worth noting that when there are only two possible vertex states, invertibility is characterized by the absence of the symbols 0s and 1s in the tags of the update rules. Before discussing the invertible rules individually, we need some additional notation.
Definition 5.2 (Blocks). If y is any state other than 0 or 1 then it consists of alternating strings of 0s an 1s that we abbreviate using exponents. For example 1 5 0 3 is shorthand for the word 11111000. We call a maximal subword of the form 0 i , 1 j , 0 i 1 j or 1 j 0 i (with i and j positive) a 0-block, a 1-block, a 01-block and a 10-block, respectively. For example, keeping in mind the cyclic nature of the subscripts, the state y = 1101001 has two 1-blocks (1 and 1 3 ), two 0-blocks (0 and 0 2 ), two 01-blocks (01 and 0 2 1 3 ), and two 10-blocks (10 2 and 1 3 0). Every block has a length. Blocks of length 1 are called isolated and longer blocks are called nontrivial.
The effect of each of the four possible x's in a tag can be described in this language. Remark 5.3 (Tags and dynamics). When t 0 =x (010 ↔ 000) isolated 1s can be created and removed and when t 3 =x (111 ↔ 101) isolated 0s can be created and removed. When t 1 = x (011 ↔ 001) the boundary between a 1-block and the 0-block to its left can be shifted left or right and when t 2 = x (110 ↔ 100) the boundary between a 1-block and the 0-block to its right can be shifted left or right.
We now discuss the invertible rules one at a time.
Rule 204. As we already noted in the last section, under rule 204, with tag ----, all of the local functions leave the state of the system unchanged, every local function induces the trivial permutation, and the group generated is the trivial group. There are thus 2 n orbits since every distinct state is an orbit.
Rule 51. Under rule 51, with tag xxxx, the local functions ignore their context and always alter the value. Since the local functions pairwise commute c 51 = 2 and the dynamics group is a quotient of Z n 2 . But since the composition of every distinct subset of local functions toggles a distinct subset of vertex states, there are at least 2 n elements in G 51 . Thus G 51 is isomorphic to Z n 2 . Finally, it is easy to see that there is only one orbit, so o 51 = 1.
Rule 60. The dynamics group G 60 is interesting because its structure is slightly unexpected. The key observation is that when vertex i is updated, its new value is its old value plus the value of the vertex immediately to its left. In other words Wolf (60) i replaces y i with y i + y i−1 , which leads to a matrix representation of the update rules. Viewing y as a column vector, the effect of updating vertex i can be achieved by multiplying y on the left by the matrix A i := I + E i,i−1 where I is the n × n identity matrix and E i,j is the elementary matrix with 0s everywhere except for a single 1 in the (i, j) position. Matrix multiplication by A i is a concise description of the function Wolf (60) i from F n 2 to F n 2 and thus the matrix group generated by the A i s is isomorphic to the dynamics group G 60 . Since each A i has determinant 1, it is clear that G 60 is a subgroup of SL n (Z 2 ), and, in fact, it is well-known that these matrices generate all of SL n (Z 2 ) [6, pg. 455]. Thus G 60 is isomorphic to SL n (Z 2 ). Under this group action it is clear that 0 is fixed and the remaining states form a single orbit. A calculation shows c 60 = 4.
Rule 150. Rule 150 is similar to rule 60 but this time, when vertex i is updated, its new value is the sum of its old value plus the value of the vertices immediately to its left and its right. This is better known as the parity function. More explicitly, F i = Wolf (150) i replaces y i with y i−1 + y i + y i+1 mod 2, which leads to a matrix representation of the update rules as before. If we define the matrices A i as I + E i,i−1 + E i,i+1 then the group G 150 can be identified as the subgroup of SL n (Z 2 ) the matrices A i generate. Unlike rule 60 it is not clear which subgroup of SL n (Z 2 ) this generates. An approach via Coxeter groups is more successful.
Since an easy calculation shows that c k = 3, G 150 is a quotient of Cox n . Recall from Remark 3.13 that Cox n ∼ = (Z n ⊥ 1) ⋊ Sym n as well as the conventions established there. The analysis of G 150 involves two steps. The first is to show that the map Cox n → G 150 is a factor of the map Cox n → Sym n (i.e. the later map decomposes as Cox n → G 150 → Sym n ). To see that G 150 maps onto Sym n in a manner consistent with the projection Cox n → Sym n start with a state y and imagine that the numbers 1 up to n are placed in the gaps between the n positions. In particular, initially place the number i between y i−1 and y i . When F i is applied to a state y switch the numbers on either side of y i fixing all the others, in addition to updating the value of y i . We claim that if i was originally in a gap that marked the end of a 0-block or 1-block, then the same is true of the place where i ends up in the final state. This follows easily from the way rule 150 updates states. From this it is not too hard to see that if a sequence of update rules fixes every state, then each of the numbers 1 through n must also return to their original position. More concretely, if the numbers 1 through n do not all return to their original positions, it is easy to find an explicit state that is not fixed by this sequence of update rules. This means that there is a well-defined group homomorphism G 150 to Sym n that sends the permutation [F Y , ω] = F ωm • · · · • F ω 1 to its permutation of the set {1, 2, . . . , n}. Since this matches the image of s ωm • · · · • s ω 1 under the map Cox n → Sym n we have the factorization we desire.
The existence of maps Cox n → G 150 → Sym n imply that the kernel of the first map consists solely of pure translations and we only need to analyze which pure translations lie in the kernel in order to completely understand the group G 150 . To do this we use the concrete description of Cox n given in Remark 3.13. One of the generating pure translations in Cox n is the element T 1 = s 1 s 2 · · · s n−1 s n s n−1 · · · s 3 s 2 . The image of this inside G 150 is the element If we apply this sequence of update rules to an arbitrary state y (using the parity function as we should), the final result is y + (y 2 + y n )1. More generally, the image of T i acts on states by sending y to y + (y i−1 + y i+1 )1. Applying T i twice is clearly trivial so the kernel contains the subgroup of (Z n ⊥ 1) that the vectors 2T i generate. This set is (2Z) n ⊥ 1. As a consequence, G 150 is a quotient of the group (Z n 2 ⊥ 1) ⋊ Sym n of size 2 n−1 · n!. When n is even there is another pure translation in the kernel, namely, the result of applying once each T i with an odd subscript. As a pure translation this adds the vector −1, 1, −1, · · · , −1, 1 . Equivalently, when n is even G 150 is a quotient of ((Z n 2 ⊥ 1)/ 1 ) ⋊ Sym n . (Note that adding 1 to a state x replaces x with its complement, the 0s become 1s and vice versa. Moreover, this pure translation commutes with the symmetric group action and is central in (Z n 2 ⊥ 1)⋊Sym n .) We now show that these are the only pure translations in the kernel.
Proof. That G 150 is a quotient of these groups was shown above, so we only need to show that we have found the full kernel of the map Cox n → G 150 . To see whether there are any other pure translations that are trivial in G 150 note that T i−1 and T i+1 are the only generating pure translations that add y i 1 to y. Thus, if a 1 T 1 +a 2 T 2 +· · ·+a n T n acts trivially on every state y, the parity of a i−1 and a i+1 must match for every i. When n is odd, this mean that all the a i have the same parity and every such element is one we already know lies in the kernel. When n is even there is one additional possibility. Perhaps the a i s with even subscripts have one parity and the ones with odd subscripts have the other. Removing summands we already know to lie in the kernel and using the relation T 1 + T 2 + · · ·+ T n = 0 if necessary, we see that this possibility is equivalent to T 1 + T 3 + T 5 + · · · + T n−1 , again, an element we already know lies in the kernel.
Although we did not need its orbit structure in order to analyze G 150 , it is easy to see that the changes rule 150 allows (and the only changes it allows) are the alterations of the boundaries of the 0-blocks and 1-blocks. Thus two states belong to the same orbit iff they have the same number of 0-blocks and the same number of 1-blocks. In particular o 150 = n 2 + 2 with the 2 corresponding to the fixed states 0 and 1. Rule 105. Rule 105 is the negation of the parity function and its analysis is very similar to our analysis of rule 150. In particular, F i = Wolf (105) i replaces y i with 1 + y i−1 + y i + y i+1 mod 2. The group G 105 can be described as a subgroup of a linear group (with an extra row and column added for constants) but viewing it as a Coxeter quotient is more fruitful. The Coxeter label c 105 = 3, and Cox n → G 105 → Sym n as above. The argument for such a factorization is similar in spirit to the one presented above for rule 150 but complicated by the presence of negations. We omit the details.
The existence of maps Cox n → G 105 → Sym n imply that the kernel of the first map consists solely of pure translations and we only need to analyze which pure translations lie in the kernel in order to completely understand the group G 105 . This time the image of the pure translation T i in G 105 acts on states by sending y to y + (1 + y i−1 + y i+1 )1. Applying T i twice is clearly trivial so the kernel contains the subgroup of (Z n ⊥ 1) that the vectors 2T i generate. This set is (2Z) n ⊥ 1. As a consequence, G 105 is a quotient of the group (Z n 2 ⊥ 1) ⋊ Sym n of size 2 n−1 · n!. When n is a multiple of 4 there is another pure translation in the kernel, namely, the result of applying once each T i with an odd subscript. The reason n needs to be a multiple of 4 and not merely even is that when n is twice an odd number y is sent to y+1. As a pure translation this adds the vector −1, 1, −1, · · · , −1, 1 . Equivalently, when n is even G 105 is a quotient of ((Z n 2 ⊥ 1)/ 1 ) ⋊ Sym n . We now show that these are the only pure translations in the kernel.
Proof. That G 105 is a quotient of these groups was shown above, so we only need to show that we have found the full kernel of the map Cox n → G 105 . To see whether there are any other pure translations that are trivial in G 105 note that T i−1 and T i+1 are the only generating pure translations that add y i 1 to y. Thus, if a 1 T 1 +a 2 T 2 +· · ·+a n T n acts trivially on every state y, the parity of a i−1 and a i+1 must match for every i. When n is odd, this mean that all the a i have the same parity and every such element is one we already know lies in the kernel. When n is even there is one additional possibility. Perhaps the a i s with even subscripts have one parity and the ones with odd subscripts have the other. Removing summands we already know to lie in the kernel and using the relation T 1 + T 2 + · · ·+ T n = 0 if necessary, we see that this possibility is equivalent to T 1 + T 3 + T 5 + · · · + T n−1 . If n is twice an odd number then y is sent to y + 1 and this is not in the kernel, but when n is twice an even number (i.e. 4 | n) then this is an element we already know lies in the kernel.
Finally, for the sake of completeness, we include a description of o 105 but leave a verification of our assertions as an exercise. When n is twice an odd number o 105 = 2 n 4 + 4, when n is twice an even number o 105 = 2 n 4 + 2, and when n is odd, o 105 = 2 (and these are the orbits of 0 and 1).
Rule 156. Wolfram rule 156 is a case where the orbit structure is useful and we use it to prove that G 156 is a subdirect product of symmetric groups of particular sizes in a very concrete fashion. The first thing to notice is that the only changes rule 156 allows are growing or shrinking 1-blocks from the right. Isolated 1s and 0s can neither be created nor removed (so the number of blocks is an invariant) and the left end of a 1-block is never moved (so that subwords of the form 01 persist forever). To analyze the number of orbits, apply the rewrite rule 110 → 100 to remove as many 1s as possible. It should be clear that (unless we started with the state 1) this process ends when all remaining 1s are isolated. Moreover, these remaining 1 are precisely the leftmost 1s in the initial blocks so there is a unique state in each orbit with isolated ones. In other words, the orbits are in natural bijection with the set N A ∪ 1, and thus o 156 = |N A ∪ 1| = Luc n + 1.
We now examine the way the updates rules act on the states in each orbit individually. The fixed state 1 can be discarded since the trivial group it generates does not contribute meaningfully to the subdirect product. Next we note that the dynamics group restricted to a single orbit usually splits further as a direct product. For example, consider the state y = 1000001000. It has a two 10-blocks, one of length 6 and one of length 4. The orbit of y consists of all words that can be written as a 10-block of length 6 followed by a 10-block of length 4. In particular, the first six digits can be 100000, 110000, 111000, 111100 or 111110 and the last four can be 1000, 1100 or 1110. These fifteen combinations form the complete orbit. In addition, writing F i in place of Wolf (156) i , the only update rules that act nontrivially on this orbit are F 2 , F 3 , F 4 , F 5 , F 8 and F 9 , but F 2 , F 3 , F 4 and F 5 commute with F 8 and F 9 so G 156 restricted to this orbit splits as a direct product F 2 , F 3 , F 4 , F 5 × F 8 , F 9 .
If we focus in on the first six digits for a moment and name the possibilities x 1 = 100000, x 2 = 110000, x 3 = 111000, x 4 = 111100 and x 5 = 111110 then we see that F 2 swaps x 1 and x 2 and fixes the other x i , F 3 swaps x 2 and x 3 , F 4 swaps x 3 and x 4 and F 5 swaps x 4 and x 5 . The induced permutations of the five possibilities are F 2 = (12), F 3 = (23), F 4 = (34) and F 5 = (45). Thus, these four update rules, restricted in this way generate a copy of Sym 5 with the functions F 2 , F 3 , F 4 and F 5 acting as the standard Coxeter generating set.
More generally, if a state y contains a 10-block of length m + 1 starting at position ℓ, then every state in the orbit of y contains a 10-block of this length at this location. There are m possibilities for a block of this type that we call x i = 1 i 0 j where i, j > 0 and i + j = m + 1. The update rules F ℓ+1 , . . . , F ℓ+m−1 are the only ones that alter this block and they generate a copy of Sym m acting on the possibilities x i in the standard way. We call this group Sym (ℓ) m . As a group it is Sym m and the number ℓ indicates which update rules generate Sym m and in what way. Returning to our earlier example, we see that the quotient of G 156 obtained by restricting to the orbit of y = 1000001000 is the group Sym 3 . More generally, if y has 10-blocks of lengths m 1 + 1, m 2 + 1, . . . , m k + 1 starting at ℓ 1 , ℓ 2 , . . . , ℓ k then the quotient of G 156 restricted to the orbit of y is the group To summarize, G 156 is a subdirect product of groups, each of which is isomorphic to a direct product of groups of the form Sym (ℓ) m . When written out completely using the orbit structure, the groups Sym (ℓ) m occur multiple times and the projection of G 156 onto each of these repeated factors is identical. As a consequence, the group G 156 can be embedded in a direct product where each of these groups only occurs once. Note that the position ℓ can be any number 1 through n, but that m + 1 can only be 2 through n excluding n − 1 since  Table 4. The orders of G 156 , G 201 and G 73 for small values of n.
the complement of the 10-block with length m + 1 must be tilable by 10-blocks and these have length at least 2.
Theorem 5.6 (Rule 156). The group G 156 is a subdirect product of symmetric groups. In particular, Sym (ℓ) m and each generator of G 156 restricted to a factor is either trivial or a standard Coxeter generator as described above.
Note that the factors with m = 1 have been eliminated from these products, which is possible because the groups Sym (ℓ) 1 are trivial. We computed the order of G 156 for 4 ≤ n ≤ 7, and the results are shown in Table 4. Notice that for n > 4 each of these orders are n th powers.
Rule 201. Rule 201 is a second situation where the orbit structure can be used to simplify our analysis. In particular we use orbit structures to prove that G 201 is a subdirect product of groups that are all (conjecturally) symmetric or alternating groups of particular sizes in a very concrete fashion. The first step is to analyze the orbit structure. The only changes under rule 201 are the creation or removal of isolated 1s. In particular the size and location of nontrivial 1-blocks in a state y are an invariant of its orbit. In fact, since we can remove all isolated 1s, any two states with the same set of nontrivial 1-blocks belong to the same orbit and every orbit has exactly one state with no isolated 1s. Thus o 201 = |N D |, the number of states with no isolated 1s.
Let y be a state with no isolated 1s. It should be clear that the restriction of the group G 201 to the orbit of y will split as a direct product with one factor for each 0-block in y. This is because all of the local functions that insert and remove isolated 1s in one 0-block will commute with those that insert and remove isolated 1s in a different 0-block, being separated by nontrivial 1-blocks. As was the case with rule 156, the orbit groups of G 201 split into factors, the refined direct product contains redundancies and these redundancies can be removed to give a better subdirect product representation of G 201 . In particular, G 201 embeds in the subdirect product of orbit groups acting on orbits with only one 0-block. Let LG n denote the group obtained by restricting G 201 to the orbit of 0 and let FG (ℓ) m be the group obtained by restricting G 201 to the orbit of the state y with a single 0-block of length m starting at position ℓ. The notations stand for Lucas group and Fibonacci group and are suggested by the fact that the orbit of 0 under G 201 is N A of size Luc n and the orbit of y under G 201 has size Fib m (the first 0 is fixed and the remaining m − 1 digits of the 0-block are tiled by tiles 0 and 10). In the case of LG n we can be slightly more precise.
Proposition 5.7 (Lucas groups). The group LG n is a subgroup of Sym Lucn when Fib n−1 is odd and a subgroup of Alt Lucn when Fib n−1 is even.
Proof. Since LG n acts on a set of size |N A | = Luc n , only the second assertion needs to be established. Let F * i denote the restriction of Wolf to N A and note that these permutations generate LG n . To count how many 2-cycles are in the disjoint cycle notation for F * i , note that for each y ∈ N A , F * i (y) = y iff y i−1 = y i+1 = 0. Thus, the number of 2-cycles in F * i equals the number of words y i+1 y i+2 . . . y i−2 y i−1 of length n − 1 with only isolated 1s and y i+1 = y i−1 = 0, which equals the number of ways to tile a word y i+2 . . . y i−2 y i−1 of length n − 2 with tiles 0 and 10. As we saw in Definition 4.5, this number is Fib n−1 . Thus F * i is an even permutation iff Fib n−1 is even, and when this is true, LG n is a subgroup of Alt Luc(n) .
The following conjecture is based on computational evidence for small values of n. We have checked, for example, that FG (ℓ) 6 ∼ = Sym 8 = Sym Fib 6 and that LG 4 ∼ = Alt 7 = Alt Luc 4 (as predicted since Fib 3 = 2 is even). The parity of the Fibonacci numbers is quite predictable and a more direct statement is possible, but the one given is more closely tied to the reason LG n stays inside Alt Luc n . The obstruction to establishing Conjecture 5.8 is how far the permutations generating the Fibonacci groups and Lucas groups differ from the standard generating sets of the symmetric and alternating groups. In any case, this analysis of the orbit structure under rule 201 gives the following subdirect product decomposition for G 201 . The values of m only range from 3 to n − 2 to exclude trivial groups on the low end and because the complement of the 0-block needs to leave room for a nontrivial block of 1s. Theorem 5.9 (Rule 201). The group G 201 is a subdirect product of Lucas groups and Fibonacci groups. In particular, Finally, we used a computer program to calculate the order of G 201 for 4 ≤ n ≤ 7, and the results are shown in Table 4. Notice that the answer in each case is an n th power times the size of Alt Lucn .
Rule 57. Wolfram rule 57 can introduce and remove isolated 0s and 1s and it can grow and shrink 0-blocks from the left and 1-blocks from the right. With so much flexibility it is easy to see that there is only one orbit and thus o 57 = 1. Moreover, because Wolf (57) i is 2 n−3 . In particular, it is an even permutation for n > 4 and we conclude that G 57 is a subgroup of Alt 2 n . Conjecture 5.10 (Rule 57). For all n > 4, G 57 ∼ = Alt 2 n .
We have verified Conjecture 5.10 explicitly up to n = 8. The reason Conjecture 5.10 is difficult to establish abstractly is that the permutations Wolf Rule 54. Rule 54 is similar to rule 57 except that the state 0 is now fixed. Since 1-blocks can grow to the left or the right and isolated 0s can be removed, all states other than 0 are in the same orbit as 1. Thus o 54 = 2. Since fixed states only contribute trivial groups to the subdirect product structure, they can be ignored when computing the dynamics group. In particular, G 54 is a subgroup of Sym 2 n −1 . Because Wolf  We have verified Conjecture 5.11 explicitly up to n = 8 as well. The reason Conjecture 5.11 is difficult to establish abstractly is that, as with rule 57, the permutations Wolf (54) i are far removed from the standard generating sets of Alt 2 n −1 .

Seven exceptions
Of the 41 representative Wolfram rules, we have seen that 26 have trivial dynamics groups, 9 are invertible, and 1 rule is both. In this section we study the remaining 7 rules. One key to understanding the dynamics of these noninvertible rules with nontrivial dynamics is to note that they agree with an invertible rule on a union of its orbits, which implies that the dynamics group of the noninvertible rule is a homomorphic image of the dynamics group of the invertible rule with which it agrees. We begin by establishing these general facts.
Theorem 6.1 (Independence and invertibility). If F Y is an ω-independent SDS, then there

and (3) there is a surjection from
. Proof. We define new local functions F ′ i as follows. Call a state y ∈ F n i-periodic if the sequence y, F i (y), F i (F i (y)), F i (F i (F i (y))), etc., eventually returns to y; otherwise call it i-transitory. The function F ′ i is defined as equal to F i on the i-periodic states and the identity function of the i-transitory ones. It is now straightforward to check that F ′ i is both Y -local at i and bijective. By Definition 5.1, the bijectivity of each F ′ i means that F ′ Y is invertible. Next, by Proposition 1.7 each F * i is a permutation of Per(F Y ). Thus the states in Per(F Y ) are i-periodic for each i, and F Y and F ′ Y agree completely on this set of states. The invariance of Per(F Y ) under each F i and its agreement with the corresponding Rule tag inv refl i.r.
F ′ i means that Per(F Y ) is a union of orbits under the action of DG(F ′ Y ). And finally, the projection from the subdirect product containing DG(F ′ Y ) onto the factors corresponding to the orbits contained in Per(F Y ) produces the required surjective group homomorphism. Proof. The assertion merely describes the effect the previous construction has on tags.
The proof of Theorem 6.1 also provides a concrete description of the periodic states. Corollary 6.4 (Periodic orbits). If F Y is an ω-independent SDS with only two possible vertex states and F ′ Y is the corresponding invertible SDS satisfying the conclusions of Theorem 6.1, then the nonperiodic states under F Y are the union of the orbits under F ′ Y that contain a state y that can be altered as a consequence of a 0 or a 1 in the tag of an update rule of F Y . Table 5 contains a summary of our results about these 7 exceptional rules. These noninvertible rules with nontrivial dynamics naturally fall into three classes: {28, 29}, {1, 9, 129, 137}, and {73}.
Rules 28 and 29. By Corollary 6.2, both G 28 and G 29 are quotients of G 156 . The first step is to decide which states are in P 28 and P 29 . By Corollary 6.4, rule 28 (with tag 0x--) must exclude all orbits that contain a state with subword 111 and rule 29 (with tag 0x-1) must exclude all orbits that contain a state with subword 111 or 000. For rule 29, we are left with those states that have no 10 blocks of length 4 or more (because any orbit that contains 1000 or 1100 also contains 1110) and for rule 28 we are left with the same states plus 0 which is fixed. These states can be described by excluding B = '111', C ='000' and F ='1100'. Because fixed states contribute trivial groups to the subdirect product and both G 28 and G 29 are obtained by restricting the action of G 156 on F n 2 to the same set of non-fixed periodic states, G 28 and G 29 are isomorphic groups. The number of orbits depends on the number of ways to tile n cyclically arranged positions by tiles of size 2 and 3 and, as we saw in Section 4, this number is counted by |N AB |. Thus o 29 = |N AB | and o 28 = |N AB | + 1. Continuing the notation used in our discussion of invertible rule 156, this means that G 28 = G 29 is the image of G 156 in the product Sym   which is isomorphic to Z n 2 . And since G 156 projects fully onto each factor, G 28 = G 29 is all of Z n 2 . As a final note, when n = 4, m + 1 is not allowed to be 3 and the factors Sym ℓ 2 do not occur in the subdirect product. Thus G 28 = G 29 are trivial groups for n = 4.
An alternative way to proceed would have been to calculate c 28 = c 29 = 2, conclude that G 28 = G 29 is a quotient of Z n 2 and then to argue that it is actually equal to Z n 2 . Finally, we remark that rules 28 and 29 have the same dynamics group as rule 51 but for very different reasons. It is perhaps surprising that rules 28 and 29 have such simple dynamics groups since they were among the six exceptional cases that needed to be dealt with separately in the proof of Theorem 2.4 due to the complications in analyzing their dynamics.
Rules 1, 9, 129 and 137. By Corollary 6.2, G 1 , G 9 , G 129 and G 137 are all quotients of G 201 . To decide which quotient, the first step is to decide which states are in P 1 , P 9 , P 129 and P 137 . By Corollary 6.4, all four sets must exclude any state with adjacent ones (although P 129 and P 137 include the fixed state 1) and, by our previous analysis of rule 201, the states with only isolated 1s form a single orbit under its action and thus are included in all four periodic sets. This means that o 1 = o 9 = 1 and o 129 = o 137 = 2. Moreover, recalling that fixed states contribute trivial groups to the subdirect product, G 1 , G 9 , G 129 and G 137 are all isomorphic to the group obtained when the action of G 201 is restricted to the single orbit N A . In other words, the groups G 1 , G 9 , G 129 , and G 137 are all isomorphic to LG n .
Rule 73. Our final rule, rule 73, is also a quotient of G 201 as indicated by Corollary 6.2, but this time the number of orbits retained is much larger. In fact, by Corollary 6.4, only states containing C='111' as a subword need to be removed. Since neither rule 201 nor rule 73 can bring subwords of the form '111' into existence, all states in N C are periodic under G 73 . Because the orbits under rule 201 each contain a unique state with no isolated 1s, the number of orbits in P 73 equals the number of states with no '111' and no '010'. Thus P 73 = N C and o 73 = |N CD |. When the orbit groups for these orbits are factored into direct products and redundancies are removed, the Lucas group LG n and all of the Fibonacci groups FG (ℓ) m arise, except those with m = n − 3 and m = n − 4. This is because the complement of the 0-block of length m starting at location ℓ must be tilable with pairs of adjacent 1s that alternate with other 0-blocks. When m = n − 2 the complement is a single pair of 1s and when m ≤ n − 5 the complement can be a word of the form 1 2 0 i 1 2 with i > 0. As with rule 201, we used a computer program to calculate the order of G 73 for 4 ≤ n ≤ 7, and the results are shown in Table 4.

Conclusion
Now that the periodic states and the dynamics groups have been roughly described for every ω-independent ACA, there are two types of generalizations that one might pursue. One natural extension would be to take a closer look at the Wolfram rules that are dependent on the update order ω and study the variety of periodic states and dynamics that arise. Because of the dependence on update order, however, dynamics groups are no longer well-defined in this context and alternative concepts will need to be developed. Alternatively, as we have tried to highlight throughout, many of the techniques developed here apply to larger classes of ω-independent SDSs. As in [2], we started with ACAs because they are simple enough to be analyzed but complicated enough to exhibit interesting behavior. Analyzing SDSs over more complicated graphs with a greater number of vertex states pose a bigger challenge.