Computational complexity studies of synchronous Boolean finite dynamical systems

DOI10.1007/978-3-319-17142-5_9MaRDI QIDQ2948456zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
• Generalized predecessor existence problems for Boolean finite dynamical systems
• Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
• Dichotomy results for fixed-point existence problems for Boolean dynamical systems
• Dichotomy results for fixed point counting in Boolean dynamical systems

Cites work

• scientific article; zbMATH DE number 4201618 (Why is no real title available?)
• scientific article; zbMATH DE number 1741013 (Why is no real title available?)
• scientific article; zbMATH DE number 872005 (Why is no real title available?)
• Complexity of reachability problems for finite discrete dynamical systems
• Dichotomy results for fixed point counting in Boolean dynamical systems
• Dichotomy results for fixed-point existence problems for Boolean dynamical systems
• Elements of a theory of simulation. II: Sequential dynamical systems.
• Equivalence relations on finite dynamical systems
• Self-witnessing polynomial-time complexity and prime factorization
• The complexity of satisfiability problems

Cited in

(7)

• On the dynamics of semilattice networks
• Existence, coexistence and uniqueness of fixed points in parallel and sequential dynamical systems over directed graphs
• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
• Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions
• Predecessors and Gardens of Eden in sequential dynamical systems over directed graphs
• Generalized predecessor existence problems for Boolean finite dynamical systems
• Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs

This page was built for publication: Computational complexity studies of synchronous Boolean finite dynamical systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948456)