Predecessor existence problems for finite discrete dynamical systems

DOI10.1016/j.tcs.2007.04.026zbMath1137.68410OpenAlexW2039967553MaRDI QIDQ2455591

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

Publication date: 25 October 2007

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.026

zbMATH Keywords

computational complexitycellular automatadiscrete dynamical systemsdata flow analysispredecessor existencesoftware and hardware verification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) 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

Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems ⋮ Synchronous Boolean finite dynamical systems on directed graphs over XOR functions ⋮ Predecessors and Gardens of Eden in sequential dynamical systems over directed graphs ⋮ 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 ⋮ Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs ⋮ Agent-Based Modeling, Mathematical Formalism for ⋮ Predecessors and Garden-of-Eden configurations in parallel dynamical systems on maxterm and minterm Boolean functions ⋮ Solution to the predecessors and gardens-of-Eden problems for synchronous systems over directed graphs ⋮ Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems ⋮ Reversing computation in membrane systems ⋮ Dual P Systems ⋮ Dynamical attraction in parallel network models ⋮ Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions ⋮ Predecessors existence problems and Gardens of Eden in sequential dynamical systems ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior

Cites Work

• 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
• Cellular automata and the sciences of complexity. A review of some outstanding problems in the theory of cellular automata.
• NP is as easy as detecting unique solutions
• On totalistic systolic networks
• One-way cellular automata on Cayley graphs
• Inversion of 2D cellular automata: Some complexity results
• Reachability problems for sequential dynamical systems with threshold functions.
• Decomposition and simulation of sequential dynamical systems
• Which problems have strongly exponential complexity?
• On acyclic orientations and sequential dynamical systems
• 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
• Complexity of generalized satisfiability counting problems
• A computational algebra approach to the reverse engineering of gene regulatory networks
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures
• On the Limit Sets of Cellular Automata
• Statistical mechanics of complex networks
• Proving liveness for networks of communicating finite state machines
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• Limit, logic, and computation
• The Structure and Function of Complex Networks
• Factor graphs and the sum-product algorithm
• General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
• The complexity of satisfiability problems
• SAT-Based Analysis of Cellular Automata
• Unconventional Computation
• ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
• Automata, Languages and Programming
• Power indices and easier hard problems
• Equivalence relations on finite dynamical systems

This page was built for publication: Predecessor existence problems for finite discrete dynamical systems