<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue4" %>
Sequential Dynamical Systems Over Words
C.M. Reidys
Center for Combinatorics, LPMC, Nankai University, Tianjin 30071, P.R. China
Annals of Combinatorics 10 (4) p.481-498 December, 2006
AMS Subject Classification: 05E99
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 {v1, … vn}, (b) a family of Y-local functions , where K is a finite field and (c) a word w, i.e., a family (w1, … ww), where wi is a Y-vertex. A map is called Y-local if and only if it fixes all variables and depends exclusively on the variables , for . An SDS induces an SDS- map, , obtained by the map-composition of the functions 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 ws, wr are adjacent in Y. G(w,Y) is acted upon by Sk via 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).
Keywords: word, dependency graph, acyclic orientation, sequential dynamical system, graph automorphism


1. C.L. Barret, R. Thord, and C.M. Reidys, Knowledge and Networks in a Dynamic Economy, Springer, Berlin, Heidelberg, New York, 1998.

2. P. Cartier and D. Foata, Problemes combinatoires de commutation et reárrangements, Lecture Notes in Math. 85, Springer-Verlag, Berlin-New York, 1969.

3. A.M. Law and W.D. Kelton, Simulation Modeling and Analysis, McGraw-Hill Book Company, Singapore, 1991.

4. H.S. Mortveit and C.M. Reidys. Discrete, sequential dynamical systems, Discrete Math. 226 (2000) 281-295.

5. C.M. Reidys, Acyclic orientations of random graphs, Adv. Appl. Math. 21 (2) (1998) 181- 192.

6. C.M. Reidys, Certain morphisms of sequential dynamical systems, Discrete Math. 296 (2-3) (2005) 245-257.