Skip to main navigation menu Skip to main content Skip to site footer

Articles

Vol. 2 No. 12 (2016): IJRDO - Journal of Mechanical and Civil Engineering

ALESHIN TYPE AUTOMATA WITH REGULAR LANGUAGES

DOI
https://doi.org/10.53555/mce.v2i12.1098
Submitted
January 2, 2018
Published
December 31, 2015

Abstract

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

Downloads

Download data is not yet available.