Sequential Dynamical Systems Over Words |
| |
Authors: | C. M. Reidys |
| |
Affiliation: | (1) Center for Combinatorics, LPMC, Nankai University, Tianjin, 30071, P.R. China |
| |
Abstract: | 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, ..., wk), 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). Received September 12, 2004 |
| |
Keywords: | 05E99 |
本文献已被 SpringerLink 等数据库收录! |
|