Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs

DOI10.1016/j.ic.2017.07.008zbMath1376.68068OpenAlexW2735429804MaRDI QIDQ2407103

Kei Uchizawa, Ogihara, Mitsunori

Publication date: 28 September 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2017.07.008

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamical systems involving maps of trees and graphs (37E25)

Related Items

On the dynamics of semilattice networks ⋮ Synchronous Boolean finite dynamical systems on directed graphs over XOR functions ⋮ Predecessors and Gardens of Eden in sequential dynamical systems over directed graphs ⋮ Existence, coexistence and uniqueness of fixed points in parallel and sequential dynamical systems over directed graphs ⋮ Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Reachability problems for sequential dynamical systems with threshold functions.
• On some special classes of sequential dynamical systems
• Elements of a theory of simulation. II: Sequential dynamical systems.
• On relationships between statistical zero-knowledge proofs
• Zero Knowledge and Circuit Minimization
• Circuit minimization problem
• The complexity of promise problems with applications to public-key cryptography
• Concise Guide to Computation Theory
• The complexity of satisfiability problems
• Power from Random Strings
• Equivalence relations on finite dynamical systems