Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
From MaRDI portal
Publication:1729688
DOI10.1016/j.tcs.2018.08.026zbMath1434.68315MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68Q80: Cellular automata (computational aspects)
37B15: Dynamical aspects of cellular automata
Related Items
Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions, Synchronous Boolean finite dynamical systems on directed graphs over XOR functions, Fuzzy parallel dynamical systems on Zadeh operators, On the impact of treewidth in the computational complexity of freezing dynamics, On the dynamics of semilattice networks, Existence, coexistence and uniqueness of fixed points in parallel and sequential dynamical systems over directed graphs, Fixed points in generalized parallel and sequential dynamical systems induced by a minterm or maxterm Boolean functions, Predecessors and Gardens of Eden in sequential dynamical systems over directed graphs
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item