All reports by Author Predrag Tosic:

__
TR06-159
| 3rd October 2006
__

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

__
TR05-091
| 11th August 2005
__

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

Revisions: 1

__
TR05-051
| 18th March 2005
__

Predrag Tosic#### On Complexity of Counting Fixed Points in Certain Classes of Graph Automata

Revisions: 2

Predrag Tosic

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

Predrag Tosic

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

Predrag Tosic

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