String Generation by Cellular Automata
Martin Kutrib
Andreas Malcher
Institut für Informatik, Universität Giessen
Arndtstr. 2, 35392 Giessen, Germany
kutrib@informatik.uni-giessen.de
andreas.malcher@informatik.uni-giessen.de
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.
Keywords: cellular automata; pattern generation; real-time computation; speedup; closure properties; decidability problems
Cite this publication as:
M. Kutrib and A. Malcher, “String Generation by Cellular Automata,” Complex Systems, 30(2), 2021 pp. 111–132.
https://doi.org/10.25088/ComplexSystems.30.2.111
