Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with enumeration problems:
TR05-091 | 11th August 2005
Predrag Tosic

Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs

Revisions: 1

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 ... 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