ON ONE-WAY CELLULAR ARRAYS

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.