ALESHIN TYPE AUTOMATA WITH REGULAR LANGUAGES - Jeyanthi, A.; Stalin, B. (IJRDO - Journal of Mechanical And Civil Engineering, 2015)
In this paper, the investigation of reversibility in computational devices is complemented by the study of reversible Aleshin type automata. These are deterministic Aleshin type automata that are also backward deterministic. All regular languages as well as some non-regular languages are accepted by reversible deterministic Aleshin type automata. Thus, the computational capacity of reversible Aleshin type automata lies properly in between the regular and deterministic context-free languages. The closure properties and decidability questions of the language class are investigated. It turns out that the closure properties of reversible Aleshin type automata are similar to those of deterministic Aleshin type automata