Complexity of reachability problems for finite discrete dynamical systems
From MaRDI portal
Publication:856411
DOI10.1016/j.jcss.2006.03.006zbMath1119.68095OpenAlexW2092522621MaRDI QIDQ856411
Christopher L. Barrett, Madhav V. Marathe, S. S. Ravi, Richard E. Stearns, Harry B. III Hunt, Daniel J. Rosenkrantz
Publication date: 7 December 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2006.03.006
computational complexitycellular automatacomplexity classesfinite discrete dynamical systemsconcurrent transition systemsdiscrete Hopfield networks
Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (20)
A Framework for Simulating Multiple Contagions Over Multiple Networks ⋮ Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs ⋮ Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems ⋮ Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems ⋮ Synchronous Boolean finite dynamical systems on directed graphs over XOR functions ⋮ UNCERTAINTY VISUALIZATION FOR CHARACTERIZING HETEROGENEOUS HUMAN BEHAVIORS IN DISCRETE DYNAMICAL SYSTEM MODELS ⋮ Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results ⋮ Attractor stability in nonuniform Boolean networks ⋮ Limit cycle structure for dynamic bi-threshold systems ⋮ Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs ⋮ Agent-Based Modeling, Mathematical Formalism for ⋮ A computational study of \(f\)-reversible processes on graphs ⋮ Reversible iterative graph processes ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems ⋮ Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game? ⋮ Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions ⋮ Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems ⋮ Complexity of local, global and universality properties in finite dynamical systems ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior
Cites Work
- Finite automata-models for the investigation of dynamical systems
- Cellular automata and the sciences of complexity. A review of some outstanding problems in the theory of cellular automata.
- On totalistic systolic networks
- Elements of a theory of computer simulation. I
- Computability with low-dimensional dynamical systems
- Asynchronous automata versus asynchronous cellular automata
- One-way cellular automata on Cayley graphs
- Inversion of 2D cellular automata: Some complexity results
- On the computational power of dynamical systems and hybrid systems
- Reachability analysis of dynamical systems having piecewise-constant derivatives
- Reachability problems for sequential dynamical systems with threshold functions.
- Decomposition and simulation of sequential dynamical systems
- On acyclic orientations and sequential dynamical systems
- Transient length in sequential iteration of threshold functions
- Discrete, sequential dynamical systems
- On the complexity of verifying concurrent transition systems
- Elements of a theory of simulation. III: Equivalence of SDS.
- On the computational complexity of finite cellular automata
- On the computational power of neural nets
- Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)
- On the Limit Sets of Cellular Automata
- Evolutionary games and computer simulations.
- On Communicating Finite-State Machines
- Proving liveness for networks of communicating finite state machines
- On the computational power of totalistic cellular automata
- A Theory of Communicating Sequential Processes
- Unpredictability and undecidability in dynamical systems
- On some relations between dynamical systems and transition systems
- General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
- Generalized shifts: unpredictability and undecidability in dynamical systems
- Equivalence relations on finite dynamical systems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity of reachability problems for finite discrete dynamical systems
