Complex Systems

String Generation by Cellular Automata Download PDF

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