Dichotomy results for fixed point counting in Boolean dynamical systems
DOI10.1016/J.TCS.2015.01.040zbMATH Open1318.68089OpenAlexW2021799291MaRDI QIDQ2257296FDOQ2257296
Authors: Christopher M. Homan, Sven Kosub 
Publication date: 24 February 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.01.040
Recommendations
- Dichotomy results for fixed-point existence problems for Boolean dynamical systems
- Unconventional Computation
- Complexity of fixed point counting problems in Boolean networks
- Fixed points in generalized parallel and sequential dynamical systems induced by a minterm or maxterm Boolean functions
- ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph minors (05C83) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Cites Work
- Title not available (Why is that?)
- Neural networks and physical systems with emergent collective computational abilities
- Graph minors. XX: Wagner's conjecture
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The Complexity of Enumeration and Reliability Problems
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- Elements of a theory of computer simulation. I
- Elements of a theory of simulation. II: Sequential dynamical systems.
- Elements of a theory of simulation. III: Equivalence of SDS.
- Complexity of generalized satisfiability counting problems
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- The complexity of counting in sparse, regular, and planar graphs
- The Parameterized Complexity of Counting Problems
- Complexity of equivalence problems for concurrent systems of finite agents
- Hard Enumeration Problems in Geometry and Combinatorics
- Dichotomy results for fixed-point existence problems for Boolean dynamical systems
- The complexity theory companion
- On the computational complexity of finite cellular automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complexity of reachability problems for finite discrete dynamical systems
- Reachability problems for sequential dynamical systems with threshold functions.
- Title not available (Why is that?)
- Unconventional Computation
- Title not available (Why is that?)
- Title not available (Why is that?)
- ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
Cited In (11)
- Computational complexity studies of synchronous Boolean finite dynamical systems
- Complexity of inferring local transition functions of discrete dynamical systems
- Unconventional Computation
- Fixed points in generalized parallel and sequential dynamical systems induced by a minterm or maxterm Boolean functions
- Positive circuits and maximal number of fixed points in discrete dynamical systems
- ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
- Existence and number of fixed points of Boolean transformations via the semi-tensor product method
- Dichotomy results for fixed-point existence problems for Boolean dynamical systems
- Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems
- On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules
- Synchronous Boolean finite dynamical systems on directed graphs over XOR functions
This page was built for publication: Dichotomy results for fixed point counting in Boolean dynamical systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2257296)
