文章基本信息

标题：A speed-up of oblivious multi-head finite automata by cellular automata
本地全文：下载
作者：Alex Borelllo ; Gaetan Richard ; Veronique Terrier 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：9
页码：273-283
DOI：10.4230/LIPIcs.STACS.2011.273
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In this paper, we present a parallel speed-up of a simple, yet significantly powerful, sequential model by cellular automata. The simulated model is called oblivious multi-head finite automata and is characterized by the fact that the trajectory of the heads only depends on the length of the input word. While the original $k$-head finite automaton works in time $O(n^k)$, its corresponding cellular automaton performs the same task in time $O(n^(k-1)log(n))$ and space $O(n^(k - 1))$.
关键词：oblivious multi-head finite automata; cellular automata; parallel speed-up; simulation