Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SEQUENTIAL AND SYNCHRONOUS DYNAMICAL SYSTEMS:
Reports tagged with Sequential and Synchronous Dynamical Systems:
TR05-051 | 18th March 2005
Predrag Tosic

On Complexity of Counting Fixed Points in Certain Classes of Graph Automata

Revisions: 2

We study the computational complexity of counting the fixed point configurations in certain discrete dynamical systems. We prove that both exact and approximate counting in Sequential and Synchronous Dynamical Systems (SDSs and SyDS, respectrively) is computationally intractable, even when each node is required to update according to a symmetric Boolean ... more >>>


TR06-159 | 3rd October 2006
Predrag Tosic

Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata

We study the computational complexity of counting the fixed point configurations (FPs), the predecessor configurations and the ancestor configurations in certain classes of graph or network automata viewed as discrete dynamical systems. Early results of this investigation are presented in two recent ECCC reports [39, 40]. In particular, it is ... more >>>




ISSN 1433-8092 | Imprint