Complexity of reachability problems for finite discrete dynamical systems
From MaRDI portal
Publication:856411
DOI10.1016/J.JCSS.2006.03.006zbMATH Open1119.68095OpenAlexW2092522621MaRDI QIDQ856411FDOQ856411
H. B. III Hunt, Christopher L. Barrett, Daniel J. Rosenkrantz, Madhav V. Marathe, S. S. Ravi, R. E. Stearns
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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Limit Sets of Cellular Automata
- Elements of a theory of computer simulation. I
- Discrete, sequential dynamical systems
- On the complexity of verifying concurrent transition systems
- Elements of a theory of simulation. III: Equivalence of SDS.
- Evolutionary games and computer simulations.
- On Communicating Finite-State Machines
- Finite automata-models for the investigation of dynamical systems
- On the computational power of neural nets
- A Theory of Communicating Sequential Processes
- Computability with low-dimensional dynamical systems
- Reachability analysis of dynamical systems having piecewise-constant derivatives
- Unpredictability and undecidability in dynamical systems
- General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
- On the computational power of totalistic cellular automata
- On the computational power of dynamical systems and hybrid systems
- Transient length in sequential iteration of threshold functions
- On some relations between dynamical systems and transition systems
- On the computational complexity of finite cellular automata
- Decomposition and simulation of sequential dynamical systems
- Reachability problems for sequential dynamical systems with threshold functions.
- Generalized shifts: unpredictability and undecidability in dynamical systems
- Inversion of 2D cellular automata: Some complexity results
- On acyclic orientations and sequential dynamical systems
- Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)
- On totalistic systolic networks
- Proving liveness for networks of communicating finite state machines
- Asynchronous automata versus asynchronous cellular automata
- One-way cellular automata on Cayley graphs
- Adversarial models in evolutionary game dynamics
- Equivalence relations on finite dynamical systems
- Cellular automata and the sciences of complexity. A review of some outstanding problems in the theory of cellular automata.
Cited In (28)
- Complexity of local, global and universality properties in finite dynamical systems
- Title not available (Why is that?)
- Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
- A Framework for Simulating Multiple Contagions Over Multiple Networks
- A computational study of \(f\)-reversible processes on graphs
- Inferring local transition functions of discrete dynamical systems from observations of system behavior
- Complexity results for reachability in cooperating systems and approximated reachability by abstract over-approximations
- Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems
- Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems
- Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
- Intrinsic universality in automata networks. II: Glueing and gadgets
- Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems
- Reversible iterative graph processes
- Attractor stability in nonuniform Boolean networks
- Limit cycle structure for dynamic bi-threshold systems
- UNCERTAINTY VISUALIZATION FOR CHARACTERIZING HETEROGENEOUS HUMAN BEHAVIORS IN DISCRETE DYNAMICAL SYSTEM MODELS
- Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems
- Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions
- Dichotomy results for fixed point counting in Boolean dynamical systems
- Agent-Based Modeling, Mathematical Formalism for
- Asynchronous, finite dynamical systems
- On the Quantifier-Free Dynamic Complexity of Reachability
- Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results
- A note on the undecidability of the reachability problem for o-minimal dynamical systems
- Title not available (Why is that?)
- The hardness of local certification of finite-state dynamics
- Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
- Synchronous Boolean finite dynamical systems on directed graphs over XOR functions
This page was built for publication: Complexity of reachability problems for finite discrete dynamical systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q856411)
