Paper Info
Title
Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs.
Abstract
A Boolean Finite Synchronous Dynamical System (BFDS, for short) consists of a finite number of objects that each maintains a boolean state, where after individually receiving state assignments, the objects update their state with respect to object-specific time-independent boolean functions synchronously in discrete time steps. The present paper studies the computational complexity of determining, given a boolean finite synchronous dynamical system, a configuration, which is a boolean vector representing the states of the objects, and a positive integer t, whether there exists another configuration from which the given configuration can be reached in t steps. It was previously shown that this problem, which we call the t-Predecessor Problem, is NP-complete even for t=1 if the update function of an object is either the conjunction of arbitrary fan-in or the disjunction of arbitrary fan-in.
Year
DOI
Venue
2019
10.1016/j.tcs.2018.08.026
Theoretical Computer Science
Keywords
Field
DocType
Computational complexity,Dynamical systems,Garden of Eden,Predecessor
Boolean function,Discrete mathematics,Finite set,Directed graph,Dynamical systems theory,Discrete time and continuous time,Mathematics,Dynamical system,Bounded function,Computational complexity theory
Journal
Volume
ISSN
Citations 
762
0304-3975
0
PageRank 
References 
Authors
0.34
14
3
Name
Order
Citations
PageRank
Akinori Kawachi118520.66
Mitsunori Ogihara23135257.04
Kei Uchizawa37412.89