Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
复制标题
有向图上同步布尔有限动力系统的计算复杂性研究
DOI：
10.1016/j.ic.2017.07.008
复制
发表时间：
2017
影响因子：
1
通讯作者：
Kei Uchizawa
中科院分区：
文献类型：
--
作者：
Mitsunori Ogihara;Kei Uchizawa
有限动态系统是由有限数量的对象组成的系统，这些对象从某个域中取一个值作为状态，其中在初始化之后，对象的状态根据其他对象的状态和它们自己根据一定的更新时间表进行更新。本文研究了有限动力系统的一个子类同步布尔有限动力系统（synchronous Boolean finite dynamics system，简称synchronous BFDS），其中状态是布尔型的，状态更新在离散时间内同时发生在所有对象上。本文研究了状态更新函数（或局部状态转移函数）从布尔函数B的有限基中选取的同步BFDS的收敛性、路径相交性和循环长度三个问题。论文的结果描述了它们的计算复杂性。
A finite dynamical system is a system consisting of some finite number of objects that take upon a value from some domain as a state, in which after initialization the states of the objects are updated based upon the states of the other objects and themselves according to a certain update schedule. This paper studies a subclass of finite dynamical systems the synchronous Boolean finite dynamical system (synchronous BFDS, for short), where the states are Boolean and the state update takes place in discrete time and at the same on all objects. The paper is concerned with three problems, Convergence, Path Intersection, and Cycle Length, of the synchronous BFDS in which the state update functions (or the local state transition functions) are chosen from a predetermined finite basis of Boolean functions B. The paper results characterize their computational complexity.