Real-Time Reversible One-Way Cellular Automata

Real-time one-way cellular automata (OCA) are investigated towards their ability to perform reversible computations with regard to formal language recognition. It turns out that the standard model with fixed boundary conditions is quite weak in terms of reversible information processing, since it is shown that in this case exactly the regular languages can be accepted reversibly. We then study a modest extension which allows that information may flow circularly from the leftmost cell into the rightmost cell. It is shown that this extension does not increase the computational power in the general case, but does increase it for reversible computations. On the other hand, the model is less powerful than real-time reversible two-way cellular automata. Additionally, we obtain that the corresponding language class is closed under Boolean operations, and we prove the undecidability of several decidability questions. Finally, it is shown that the reversibility of an arbitrary real-time circular one-way cellular automaton is undecidable as well.