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

DOI10.1142/S0129054106004339MaRDI QIDQ5493901zbMATH OpenFDO

Authors Predrag T. Tosic

Publication date 16 October 2006

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

Full work available at URL https://doi.org/10.1142/S0129054106004339

zbMATH Keywords

cellular and graph automatacomputational complexitydiscrete dynamical systemsenumeration problems{\#}P-completeness

Mathematics Subject Classification ID

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

Recommendations

• Unconventional Computation
• scientific article; zbMATH DE number 1741013
• On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules
• Dichotomy results for fixed point counting in Boolean dynamical systems
• Elements of a theory of simulation. III: Equivalence of SDS.

Cites work

• Approximating the Permanent
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Discrete, sequential dynamical systems
• Elements of a theory of computer simulation. I
• Elements of a theory of simulation. II: Sequential dynamical systems.
• Elements of a theory of simulation. III: Equivalence of SDS.
• Finite automata-models for the investigation of dynamical systems
• scientific article; zbMATH DE number 3986649 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 726524 (Why is no real title available?)
• Neural networks and physical systems with emergent collective computational abilities
• On the computational complexity of finite cellular automata
• One-way cellular automata on Cayley graphs
• Polynomial-Time Approximation Algorithms for the Ising Model
• PP is as Hard as the Polynomial-Time Hierarchy
• Proving liveness for networks of communicating finite state machines
• Reachability problems for sequential dynamical systems with threshold functions.
• The complexity of computing the permanent
• The complexity of counting in sparse, regular, and planar graphs
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• Unpredictability and undecidability in dynamical systems

Cited in

(8)

• Enumerating periodic orbits in sequential dynamical systems over graphs
• \#P-completeness of counting update digraphs, cacti, and series-parallel decomposition method
• Dichotomy results for fixed point counting in Boolean dynamical systems
• Predecessor existence problems for finite discrete dynamical systems
• On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules
• scientific article; zbMATH DE number 1741013 (Why is no real title available?)
• Unconventional Computation
• Counting and hardness-of-finding fixed points in cellular automata on random graphs

This page was built for publication: ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS

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