We study counting various types of configurations in certain classes of graph automata viewed as discrete dynamical systems. The graph automata models of our interest are Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively). These models have been proposed as a mathematical foundation for a theory of large-scale simulations of complex multi-agent systems. Our emphasis in this paper is on the computational complexity of counting the fixed point and the garden of Eden configurations in Boolean SDSs and SyDSs. We have shown in [47] that counting fixed points is, in general, computationally intractable. We show in the present report that this intractability still holds when both the underlying graphs and the node update rules of these SDSs and SyDSs are severely restricted. In particular, we prove that the problems of exactly counting fixed points, gardens of Eden and two other types of S(y)DS configurations are all #P-complete, even if the SDSs and SyDSs are defined over planar bipartite graphs, and each of their nodes updates its state according to a monotone update rule given as a Boolean formula. We thus add these formal discrete dynamical systems to the list of those problem domains for which counting the combinatorial structures of interest is intractable even when the related decision problems are known to be efficiently solvable.

We study counting various types of congurations in certain classes of graph
automata viewed as discrete dynamical systems. The graph automata models
of our interest are Sequential and Synchronous Dynamical Systems (SDSs and
SyDSs, respectively). These models have been proposed as a mathematical foun-
dation for a theory of large-scale simulations of complex multi-agent systems.
Our emphasis in this paper is on the computational complexity of counting the
xed point and the garden of Eden congurations in Boolean SDSs and SyDSs.
We have shown in [47] that counting xed points is, in general, computation-
ally intractable. We show in the present report that this intractability still holds
when both the underlying graphs and the node update rules of these SDSs and
SyDSs are severely restricted. In particular, we prove that the problems of exactly
counting xed points, gardens of Eden and two other types of S(y)DS congura-
tions are all #P-complete, even if the SDSs and SyDSs are dened over planar
bipartite graphs, and each of their nodes updates its state according to a mono-
tone update rule given as a Boolean formula. We thus add these formal discrete
dynamical systems to the list of those problem domains for which counting the
combinatorial structures of interest is intractable even when the related decision
problems are known to be enumerationciently solvable.