Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with cellular automata:
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 >>>

TR14-029 | 4th March 2014
Oded Goldreich, Dana Ron

On Learning and Testing Dynamic Environments

Revisions: 3

We initiate a study of learning and testing dynamic environments,
focusing on environment that evolve according to a fixed local rule.
The (proper) learning task consists of obtaining the initial configuration
of the environment, whereas for non-proper learning it suffices to predict
its future values. The testing task consists of ... more >>>

TR14-044 | 2nd April 2014
Daniel Dewey

Additively efficient universal computers

We give evidence for a stronger version of the extended Church-Turing thesis: among the set of physically possible computers, there are computers that can simulate any other realizable computer with only additive constant overhead in space, time, and other natural resources. Complexity-theoretic results that hold for these computers can therefore ... more >>>

TR14-084 | 12th June 2014
Luke Schaeffer

A Physically Universal Cellular Automaton

Several cellular automata (CA) are known to be universal in the sense that one can simulate arbitrary computations (e.g., circuits or Turing machines) by carefully encoding the computational device and its input into the cells of the CA. In this paper, we consider a different kind of universality proposed by ... more >>>

ISSN 1433-8092 | Imprint