Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems

DOI10.1007/978-3-319-17142-5_9zbMath1459.68084OpenAlexW2261252637MaRDI QIDQ2948456

Ogihara, Mitsunori, Kei Uchizawa

Publication date: 30 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-17142-5_9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Invariant manifold theory for dynamical systems (37D10)

Related Items

On the dynamics of semilattice networks ⋮ Predecessors and Gardens of Eden in sequential dynamical systems over directed graphs ⋮ 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 ⋮ Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems

Cites Work

• Complexity of reachability problems for finite discrete dynamical systems
• Dichotomy results for fixed-point existence problems for Boolean dynamical systems
• Self-witnessing polynomial-time complexity and prime factorization
• Elements of a theory of simulation. II: Sequential dynamical systems.
• Dichotomy results for fixed point counting in Boolean dynamical systems
• The complexity of satisfiability problems
• Equivalence relations on finite dynamical systems
• Unnamed Item
• Unnamed Item
• Unnamed Item