Language Recognition by Reversible Partitioned Cellular Automata and Iterative Arrays

摘要

We propose two kinds of language recognition models based on partitioned cellular automata (PCAs). They are one-dimensional PCA acceptors (PCAAs), and one-dimensional partitioned iterative array acceptors (PIAAs). We investigate how their accepting capabilities are affected by the constraint of reversibility. It is well known that (irreversible) deterministic cellular automaton acceptors and iterative array acceptors whose space is bounded by the length of the input are equivalent to deterministic linear-bounded automata (DLBAs). Here, we show reversible PCAAs and reversible PIAAs with the same space bound are also equivalent to them. These results are proved by giving concrete construction methods of a reversible PCAA and a reversible PIAA that can simulate a given DLBA. Thus, the reversibility constraint does not weaken the accepting powers of these models.