String Generation by Cellular Automata

Abstract

In contrast to many investigations of cellular automata with regard to their ability to accept inputs under certain time constraints, in this paper we are studying cellular automata with regard to their ability to generate strings in real time. Structural properties such as speedup results and closure properties are investigated. On the one hand, constructions for the closure under intersection, reversal and length-preserving homomorphism are presented, whereas on the other hand the nonclosure under union, complementation and arbitrary homomorphism are obtained. Finally, decidability questions such as emptiness, finiteness, equivalence, inclusion, regularity and context-freeness are addressed.