FAST PARALLEL LANGUAGE RECOGNITION BY CELLULAR AUTOMATA
FAST PARALLEL LANGUAGE RECOGNITION BY CELLULAR AUTOMATA
复制标题
DOI：
10.1016/0304-3975(85)90073-8
复制
发表时间：
1985-01-01
影响因子：
1.1
通讯作者：
KIM, SM
中科院分区：
文献类型：
--
作者：
IBARRA, OH;PALIS, MA;KIM, SM
我们来看看线性细胞自动机（CA），它接受一个输入，当且仅当在计算过程中的某个时候，数组中的所有处理器都处于接受状态。我们证明，有非上下文无关的语言，接受CA的O（log n）时间。此外，这是最好的可能性，因为o（log n）时间CA只能接受常规集。我们表明，单向CA的操作在T（n）的时间可以模拟CA的在1 - 2（T（n）+ 1）的时间。作为一个推论，CA的可以接受线性，Dyck，括号上下文无关的语言在12（n+ 1）的时间，这又是最佳的。我们还研究了CA的其他模式的接受和有关的速度，层次结构等方面的结果。
We look at linear cellular automata (CA's) which accept an input if and only if at some time during the computation all the processors in the array are in accepting states. We prove that there are noncontext-free languages that are accepted by CA's in O (log n) time. Moreover, this is the best possible since o (log n) time CA's can accept only regular sets. We show that one-way CA's operating in T (n) time can be simulated by CA's in 1 2 (T (n)+ 1) time. As a corollary, CA's can accept the linear, Dyck, and bracketed context-free languages in 1 2 (n+ 1) time, which is again optimal. We also study CA's with other modes of acceptance and derive results concerning speed-up, hierarchy, etcetera.