Sequential Dynamical Systems Over Words

摘要

In this paper we study sequential dynamical systems (SDS) over words. An SDS is a triple consisting of: (a) a graph Y with vertex set {v 1, ..., v n }, (b) a family of Y-local functions $ (F_{v_{i}})_{1 leq i leq n} , F_{v_{i}} :K^{n} to K^{n} $ , where K is a finite field and (c) a word w, i.e., a family (w 1, ..., w k ), where w i is a Y-vertex. A map $ F_{v_{i}} (x_{v_{1}} , ldots x_{v_{n}} ) $ is called Y-local if and only if it fixes all variables $ x_{v_{j}} ne x_{v_{i}} $ and depends exclusively on the variables $ x_{v_{j}} $ , for $ v_{j} in B_{1} (v_{i} ) $ . An SDS induces an SDS- map, $ {left[ {(F_{v_{i}} )_{{v_{i} in Y}} ,w} right]} = {prodnolimits_{i = 1}^k {F_{w_{i}} :K^{n} } } to K^{n} $ , obtained by the map-composition of the functions $ F_{v_{i}} $ according to w. We show that an SDS induces in addition the graph G(w,Y) having vertex set {1, ..., k} where r, s are adjacent if and only if w s , w r are adjacent in Y. G(w, Y) is acted upon by S k via $ rho cdot w = (w_{{rho ^{{ - 1}} (1)}} , ldots w_{{rho ^{{ - 1}} (k)}} ) $ and Fix(w) is the group of G(w, Y) graph automorphisms which fix w. We analyze G(w, Y)-automorphisms via an exact sequence involving the normalizer of Fix(w) in Aut(G(w, Y)), Fix(w) and Aut(Y). Furthermore we introduce an equivalence relation over words and prove a bijection between word equivalence classes and certain orbits of acyclic orientations of G(w, Y).