Real-time reversible iterative arrays

Iterative arrays are one-dimensional arrays of interconnected interacting finite automata. The cell at the origin is equipped with a one-way read-only input tape. We investigate iterative arrays as acceptors for formal languages. In particular, we consider real-time devices which are reversible on the core of computation, i.e., from initial configuration to the configuration given by the time complexity. This property is called real-time reversibility. It is shown that real-time reversible iterative arrays can simulate restricted variants of stacks and queues. It turns out that real-time reversible iterative arrays are strictly weaker than real-time reversible cellular automata. On the other hand, a non-semilinear language is accepted. We show that real-time reversibility itself is not even semidecidable, which extends the undecidability for cellular automata and contrasts with the general case, where reversibility is decidable for one-dimensional devices. Moreover, we prove the non-semidecidability of several other properties. Several closure properties are also derived.