Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
From MaRDI portal
Publication:1729688
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
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