Cellular automata (abstract and discussion): complex nonadaptive systems

Cellular automata CA are discrete dynamical systems consist of a regular finite grid of cell; each cell encapsulating an equal portion of the state, and arranged spatially in a regular fashion to form an n-dimensional lattice. A cellular automata is ...

Concerning the power of one-dimensional cellular automata recognizers, Ibarra and Jiang have proved that real time cellular automata (CA) and linear time CA are equivalent if and only if real time CA is closed under reverse. In this paper we investigate ...

We study the sofic tree shifts of A^@S^^^@?, where @S^@? is a regular rooted tree of finite rank. In particular, we give their characterization in terms of unrestricted Rabin automata. We show that if X@?A^@S^^^@? is a sofic tree shift, then the ...