ON ONE-WAY CELLULAR ARRAYS

被引：38

作者：

IBARRA, OH

JIANG, T

机构：

[1] Univ of Minnesota, Minneapolis, MN,, USA, Univ of Minnesota, Minneapolis, MN, USA

来源：

SIAM JOURNAL ON COMPUTING | 1987年 / 16卷 / 06期

关键词：

COMPUTER SYSTEMS; DIGITAL - Parallel Processing;

D O I：

10.1137/0216072

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

There are two simple models of parallel language recognizer: one-way cellular array (OCA) and one-way iterative array (OIA). For inputs of length n, both arrays consist of n identical finite-state machines (cells). The communication between cells is one way, from left to right. The difference in the two models is in the manner in which the input is applied. For the OCA, the input is applied to the cells in parallel. For the OIA, the input is applied serially to the leftmost processor. An input string is accepted if the rightmost cell eventually enters an accepting state. We show that OCA's accept exactly the same class of languages as OIA's. We also prove some new results concerning linear-time OCA's and OIA's.

引用

页码：1135 / 1154

页数：20