Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs

DOI10.1016/j.tcs.2018.08.026zbMath1434.68315OpenAlexW2891749150MaRDI QIDQ1729688

Akinori Kawachi, Kei Uchizawa, Ogihara, Mitsunori

Publication date: 28 February 2019

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.08.026

zbMATH Keywords

computational complexitydynamical systemsGarden of Edenpredecessor

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15)

Related Items (8)

On the dynamics of semilattice networks ⋮ Fixed points in generalized parallel and sequential dynamical systems induced by a minterm or maxterm Boolean functions ⋮ Synchronous Boolean finite dynamical systems on directed graphs over XOR functions ⋮ Fuzzy parallel dynamical systems on Zadeh operators ⋮ 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 ⋮ On the impact of treewidth in the computational complexity of freezing dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for singleton attractor detection in planar and nonplanar AND/OR Boolean networks
• Determining a singleton attractor of an AND/OR Boolean network in \(O(n^{1.587})\) time
• Complexity of reachability problems for finite discrete dynamical systems
• Dichotomy results for fixed-point existence problems for Boolean dynamical systems
• Elements of a theory of simulation. II: Sequential dynamical systems.
• Predecessor existence problems for finite discrete dynamical systems
• Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems
• Nondeterministic Space is Closed under Complementation

This page was built for publication: Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs