Fast reversible language recognition using cellular automata

We investigate cellular automata 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. We study whether for a given real-time CA working on finite configurations with fixed boundary conditions there exists a reverse real-time CA with the same neighborhood. It is shown that real-time reversibility is undecidable, which contrasts the general case, where reversibility is decidable for one-dimensional devices. Moreover, we prove the undecidability of emptiness, finiteness, infiniteness, inclusion, equivalence, regularity, and context-freedom. First steps towards the exploration of the computational capacity are done and closure under Boolean operations is shown.

Authors

• Martin Kutrib
• Andreas Malcher

Keywords

• Cellular automata
• Real-time reversible computations
• Language recognition
• Closure properties
• Decidability questions