Reachability problems for sequential dynamical systems with threshold functions.

DOI10.1016/S0304-3975(02)00395-XMaRDI QIDQ1401231zbMATH OpenOpenAlexFDO

Authors H. B. III Hunt, S. S. Ravi, Daniel J. Rosenkrantz, R. E. Stearns, Madhav V. Marathe, Christopher 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

Cellular automataCommunicating finite state machinesComputational complexityDynamical systemsHopfield networksTheory of simulation

Mathematics Subject Classification ID

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

Recommendations

• Analysis problems for sequential dynamical systems and communicating state machines
• On some special classes of sequential dynamical systems
• Complexity of reachability problems for finite discrete dynamical systems
• Limit Set Reachability in Asynchronous Graph Dynamical Systems
• ETS IV: Sequential dynamical systems: fixed points, invertibility and equivalence

Cites work

• A Theory of Communicating Sequential Processes
• Analysis problems for sequential dynamical systems and communicating state machines
• Asynchronous automata versus asynchronous cellular automata
• Combinatorics of sequential dynamical systems
• Discrete, sequential dynamical systems
• Dynamics of positive automata networks
• Elements of a theory of simulation. III: Equivalence of SDS.
• Evolutionary games and computer simulations.
• Finite automata-models for the investigation of dynamical systems
• scientific article; zbMATH DE number 4058875 (Why is no real title available?)
• scientific article; zbMATH DE number 4074492 (Why is no real title available?)
• scientific article; zbMATH DE number 149060 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1296290 (Why is no real title available?)
• scientific article; zbMATH DE number 2102770 (Why is no real title available?)
• scientific article; zbMATH DE number 3328721 (Why is no real title available?)
• Neurons with graded response have collective computational properties like those of two-state neurons
• On Communicating Finite-State Machines
• On some relations between dynamical systems and transition systems
• On the complexity of verifying concurrent transition systems
• On the computational complexity of finite cellular automata
• One-way cellular automata on Cayley graphs
• Proving liveness for networks of communicating finite state machines
• Transient length in sequential iteration of threshold functions
• Unpredictability and undecidability in dynamical systems

Cited in

(20)

• On some special classes of sequential dynamical systems
• Enumerating periodic orbits in sequential dynamical systems over graphs
• Dichotomy results for fixed point counting in Boolean dynamical systems
• Inferring local transition functions of discrete dynamical systems from observations of system behavior
• Computational complexity studies of synchronous Boolean finite dynamical systems on directed graphs
• Predecessor existence problems for finite discrete dynamical systems
• Combinatorics of sequential dynamical systems
• Adversarial scheduling in discrete models of social dynamics
• Complexity of inferring local transition functions of discrete dynamical systems
• On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules
• Limit Set Reachability in Asynchronous Graph Dynamical Systems
• Analysis problems for sequential dynamical systems and communicating state machines
• Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions
• Agent-based modeling, mathematical formalism for
• ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
• Modeling and analyzing social network dynamics using stochastic discrete graphical 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
• Flexible toggles and symmetric invertible asynchronous elementary cellular automata
• Complexity of reachability problems for finite discrete dynamical systems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401231)