首页 | 官方网站   微博 | 高级检索  
     


On Acyclic Orientations and Sequential Dynamical Systems
Authors:C M Reidys
Affiliation:Los Alamos National Laboratory, D 2, New Mexico, 87545, f1
Abstract:We study a class of discrete dynamical systems that consists of the following data: (a) a finite (labeled) graph Y with vertex set {1, …, n}, where each vertex has a binary state, (b) a vertex labeled multi-set of functions (Fi, Y: Image 2n → Image 2n)i, and (c) a permutation π set membership, variant Sn. The function Fi, Y updates the binary state of vertex i as a function of the states of vertex i and its Y-neighbors and leaves the states of all other vertices fixed. The permutation π represents a Y-vertex ordering according to which the functions Fi, Y are applied. By composing the functions Fi, Y in the order given by π we obtain the sequential dynamical system (SDS):
Image
In this paper we first establish a sharp, combinatorial upper bound on the number of non-equivalent SDSs for fixed graph Y and multi-set of functions (Fi, Y). Second, we analyze the structure of a certain class of fixed-point-free SDSs.
Keywords:acyclic orientations  sequential dynamical system  orderings  graph automorphisms
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号