Benutzer: Gast  Login
Titel:

Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems

Dokumenttyp:
Technical Report
Autor(en):
Sven Kosub
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...     »
Stichworte:
Discrete dynamical systems; fixed points; algorithms and complexity
Jahr:
2007
Jahr / Monat:
2007-01-01 00:00:00
Seiten/Umfang:
19
 BibTeX