Dichotomy results for fixed-point existence problems for Boolean dynamical systems

DOI10.1007/s11786-007-0038-yzbMath1138.68034OpenAlexW2056659750MaRDI QIDQ926325

Sven Kosub

Publication date: 27 May 2008

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11786-007-0038-y

zbMATH Keywords

fixed pointsdiscrete dynamical systemsalgorithms and complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)

Related Items (13)

Complexity of fixed point counting problems in Boolean networks ⋮ On the dynamics of semilattice networks ⋮ Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs ⋮ Fixed points in generalized parallel and sequential dynamical systems induced by a minterm or maxterm Boolean functions ⋮ Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems ⋮ Synchronous Boolean finite dynamical systems on directed graphs over XOR functions ⋮ Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs ⋮ Existence, coexistence and uniqueness of fixed points in parallel and sequential dynamical systems over directed graphs ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems ⋮ Sequentialization and procedural complexity in automata networks ⋮ Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions ⋮ Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems

This page was built for publication: Dichotomy results for fixed-point existence problems for Boolean dynamical systems