ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS

DOI10.1142/S0129054106004339zbMath1100.68072MaRDI QIDQ5493901

Predrag T. Tosic

Publication date: 16 October 2006

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexitydiscrete dynamical systemsenumeration problems{\#}P-completenesscellular and graph automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15)

Related Items

Predecessor existence problems for finite discrete dynamical systems ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ Enumerating periodic orbits in sequential dynamical systems over graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite automata-models for the investigation of dynamical systems
• The complexity of computing the permanent
• Elements of a theory of computer simulation. I
• One-way cellular automata on Cayley graphs
• Reachability problems for sequential dynamical systems with threshold functions.
• Elements of a theory of simulation. II: Sequential dynamical systems.
• Discrete, sequential dynamical systems
• Elements of a theory of simulation. III: Equivalence of SDS.
• On the computational complexity of finite cellular automata
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Polynomial-Time Approximation Algorithms for the Ising Model
• Approximating the Permanent
• PP is as Hard as the Polynomial-Time Hierarchy
• Proving liveness for networks of communicating finite state machines
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• Unpredictability and undecidability in dynamical systems
• Neural networks and physical systems with emergent collective computational abilities.