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) 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→Kn, where K is a finite field and (c) a word w, i.e. a family (w1,…,wk), where wj is a Y-vertex. A map Fvi(xv1,…,xvn) is called Y-local iff it fixes all variables xvj≠xvi and depends exclusively on the variables xvj, for vjB1(vi). The SDS-map is obtained by composing the local maps Fvi according to the word w: . Mutual dependencies of the local maps arising from their sequential application are expressed in the graph G(w,Y) having vertex set {1,…,k} (the indices of the word w) and in which r,s are adjacent iff ws,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). We show that within these equivalence classes the induced SDS are equivalent in the sense that their respective phase spaces are isomorphic as digraphs.