文章基本信息

标题：Transductions Computed by One-Dimensional Cellular Automata
本地全文：下载
作者：Martin Kutrib ; Andreas Malcher
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2012
卷号：90
页码：194-207
DOI：10.4204/EPTCS.90.16
出版社：Open Publishing Association
摘要：Cellular automata are investigated towards their ability to compute transductions, that is, to transform inputs into outputs. The families of transductions computed are classified with regard to the time allowed to process the input and to compute the output. Since there is a particular interest in fast transductions, we mainly focus on the time complexities real time and linear time. We first investigate the computational capabilities of cellular automaton transducers by comparing them to iterative array transducers, that is, we compare parallel input/output mode to sequential input/output mode of massively parallel machines. By direct simulations, it turns out that the parallel mode is not weaker than the sequential one. Moreover, with regard to certain time complexities cellular automaton transducers are even more powerful than iterative arrays. In the second part of the paper, the model in question is compared with the sequential devices single-valued finite state transducers and deterministic pushdown transducers. It turns out that both models can be simulated by cellular automaton transducers faster than by iterative array transducers.