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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Real-Time Pattern Generation by One-Dimensional Cellular Automata

  • Martin Kutrib,
  • Andreas Malcher

摘要

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.