Combinatorics of sequential dynamical systems

In this paper we study sequential dynamical systems (SDS) over words. Our main result is the classification of SDS over words for fixed graph Y   and family of local maps (Fvi)(Fvi) by means of a novel notion of SDS equivalence. This equivalence arises from a natural group action on acyclic orientations. An SDS consists of: (a) a graph Y, (b) a family of vertex indexed Y  -local maps Fvi:Kn→KnFvi:Kn→Kn, where K   is a finite field and (c) a word ww, i.e. a family (w1,…,wk)(w1,…,wk), where wjwj is a Y  -vertex. A map Fvi(xv1,…,xvn)Fvi(xv1,…,xvn) is called Y  -local iff it fixes all variables xvj≠xvixvj≠xvi and depends exclusively on the variables xvjxvj, for vj∈B1(vi)vj∈B1(vi). The SDS-map is obtained by composing the local maps FviFvi according to the word ww: [(Fvi)vi∈Y,w]=∏i=1kFwi:Kn⟶Kn. Mutual dependencies of the local maps arising from their sequential application are expressed in the graph G(w,Y)G(w,Y) having vertex set {1,…,k}{1,…,k} (the indices of the word ww) and in which r,sr,s are adjacent iff ws,wrws,wr are adjacent in Y. We prove a bijection from equivalence classes of SDS-words into equivalence classes of acyclic orientations of G(w,Y)G(w,Y). We show that within these equivalence classes the induced SDS are equivalent in the sense that their respective phase spaces are isomorphic as digraphs.