Complexity of One-Way Cellular Automata

Among the different types of cellular automata the one-dimensional one-way variant with fixed boundary conditions is one of the simplest. Here we consider these devices as massively parallel computing model. The formal investigations of their properties and capacities began in the sixties. Though a lot of results have been found over the years, there are still several open problems. The survey addresses the basic hierarchy of induced language classes. Aspects of computational complexity are discussed in connection with classical complexity theory. Hard open problems give rise to consider one-way cellular automata also from the structural complexity point of view. Adding (limited) nondeterminism to the model yields structurally more complex and computationally more powerful devices. Finally, the capabilities of one-way cellular automata to time-compute functions are considered. This means that given an input of length n a distinguished cell has to enter a distinguished state exactly after f(n) time steps. We present some selected results on these topics and want to draw attention to the overall picture and to some of the main ideas involved.