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 congurations 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 congurations 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 congura-

tions are all #P-complete, even if the SDSs and SyDSs are dened 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.