Real-Time Pattern Generation by One-Dimensional Cellular Automata
摘要
We give a survey on cellular automata that, in contrast to the traditional point of view, are used to generate formal languages which are here called patterns. In addition, we consider cellular automata that generate their patterns in minimal time, that is, in real time. We present several families of patterns that can be generated in real time comprising unary patterns, context-free properly thin languages, and prefixes of automatic sequences and morphic words. We also investigate structural properties of these pattern generating devices, namely, speed-up results and closure properties. Finally, we address decidability problems such as emptiness, finiteness, inclusion, and equivalence.