User: Guest  Login
Document type:
Technical Report 
Author(s):
Sven Kosub; Christopher M. Homan 
Title:
Dichotomy Result for Fixed Point Counting in Boolean Dynamical Systems. 
Abstract:
We present dichotomy theorems regarding the computational complexity of counting fixed points in boolean (discrete) dynamical systems, i.e., finite discrete dynamical systems over the domain {0,1}. For a class F of boolean functions and a class G of graphs, an (F, G)-system is a boolean dynamical system with local transitions functions lying in F and graph in G. We show that, if local transition functions are given by lookup tables, then the following complexity classification holds: Let F be a...    »
 
Keywords:
Discrete dynamical systems; fixed point; algorithms and complexity 
Year:
2007 
Year / month:
2007-01-01 00:00:00 
Pages:
18