Reachability problems for sequential dynamical systems with threshold functions.

DOI10.1016/S0304-3975(02)00395-XzbMath1045.68062OpenAlexW2127028562MaRDI QIDQ1401231

Harry B. III Hunt, Richard E. Stearns, S. S. Ravi, Daniel J. Rosenkrantz, Madhav V. Marathe, Chris L. Barrett

Publication date: 17 August 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00395-x

zbMATH Keywords

Dynamical systemsCellular automataComputational complexityHopfield networksCommunicating finite state machinesTheory of simulation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cellular automata (computational aspects) (68Q80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (15)

Complexity of reachability problems for finite discrete dynamical systems ⋮ Adversarial scheduling in discrete models of social dynamics ⋮ Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs ⋮ Synchronous Boolean finite dynamical systems on directed graphs over XOR functions ⋮ UNCERTAINTY VISUALIZATION FOR CHARACTERIZING HETEROGENEOUS HUMAN BEHAVIORS IN DISCRETE DYNAMICAL SYSTEM MODELS ⋮ Predecessor existence problems for finite discrete dynamical systems ⋮ Agent-Based Modeling, Mathematical Formalism for ⋮ Combinatorics of sequential dynamical systems ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems ⋮ Flexible toggles and symmetric invertible asynchronous elementary cellular automata ⋮ Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions ⋮ Limit Set Reachability in Asynchronous Graph Dynamical Systems ⋮ Enumerating periodic orbits in sequential dynamical systems over graphs ⋮ ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite automata-models for the investigation of dynamical systems
• Dynamics of positive automata networks
• Asynchronous automata versus asynchronous cellular automata
• One-way cellular automata on Cayley graphs
• 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
• Combinatorics of sequential dynamical systems
• Evolutionary games and computer simulations.
• On Communicating Finite-State Machines
• Proving liveness for networks of communicating finite state machines
• A Theory of Communicating Sequential Processes
• Unpredictability and undecidability in dynamical systems
• On some relations between dynamical systems and transition systems
• Neurons with graded response have collective computational properties like those of two-state neurons.

This page was built for publication: Reachability problems for sequential dynamical systems with threshold functions.