User: Guest  Login
Document type:
Technical Report 
Author(s):
Sven Kosub 
Title:
Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems 
Abstract:
A complete classification of the computational complexity of the fixed-point existence problem for boolean dynamical systems, i.e., finite discrete dynamical systems over the domain {0,1}, is presented. For function classes F and graph classes G, an (F,G)-system is a boolean dynamical system such that all local transition functions lie in F and the underlying graph lies in G. Let F be a class of boolean functions which is closed under composition and let G be a class of graphs which is closed un...    »
 
Keywords:
Discrete dynamical systems; fixed points; algorithms and complexity 
Year:
2007 
Year / month:
2007-01-01 00:00:00 
Pages:
19