Journal article

Publication year: 2017

Pages: 31-58

Journal: Fundamenta Informaticae

Volume number: 155

Issue number: 1-2

ISSN: 0169-2968

eISSN: 1875-8681

DOI Link: https://doi.org/10.3233/FI-2017-1575

Publisher: SAGE Publications

Abstract: 
A kappa-limited automaton is a linear bounded automaton that may rewrite each tape square only in the first kappa visits, where kappa >= 0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate deterministic k-limited automata towards their ability to perform reversible computations, that is, computations in which every configuration has at most one predecessor. A first result is that, for all kappa >= 0, sweeping kappa-limited automata accept regular languages only. In contrast to reversible finite automata, all regular languages are accepted by sweeping 0 -limited automata. Then we study the computational power gained in the number kappa of possible rewrite operations. It is shown that the reversible 2-limited automata accept regular languages only and, thus, are strictly weaker than general 2-limited automata. Furthermore, a proper inclusion between reversible 3-limited and 4-limited automata languages is obtained. The next levels of the hierarchy are separated between every kappa and kappa + 3 rewrite operations. We investigate closure properties of the family of languages accepted by reversible k -limited automata. It turns out that these families are not closed under intersection, but are closed under complementation. They are closed under intersection with regular languages, which leads to the non-closure under concatenation, iteration, and homomorphisms. Finally, it turns out that all kappa-limited automata accept Church-Rosser languages only, that is, the intersection between context-free and Church-Rosser languages contains an infinite hierarchy of language families beyond the deterministic context-free languages.

Harvard Citation style: Kutrib, M. and Wendlandt, M. (2017) Reversible Limited Automata, Fundamenta Informaticae, 155(1-2), pp. 31-58. https://doi.org/10.3233/FI-2017-1575

APA Citation style: Kutrib, M., & Wendlandt, M. (2017). Reversible Limited Automata. Fundamenta Informaticae. 155(1-2), 31-58. https://doi.org/10.3233/FI-2017-1575