Affiliations: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. {kutrib,matthias.wendlandt}@informatik.uni-giessen.de
Correspondence:
[*]
Address for correspondence: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany
Abstract: A k-limited automaton is a linear bounded automaton that may rewrite each tape square only in the first k visits, where k ≥ 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 k ≥ 0, sweeping k-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 k 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 k and k + 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 k-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.
