On the power one-way communication

We look at a very simple model of parallel computation and study the question of how restricting the flow of data to be one-way compares with two-way flow. A one-way linear iterative array (1LIA) is a finite one-dimensional array of identical finite-state machines (cells) in which information is allowed to move only in one direction- from left to right. For inputs of length n, the array uses n cells which are initially set to the quiescent state. The serial input, which is applied to the leftmost cell, is accepted if the rightmost cell ever enters an accepting state. We give results which show that 1LIA´s are surprisingly very powerful in that they can accept languages which seemingly require two-way communication.