Characterizing the regular languages by nonforgetting restarting automata

Norbert Hundeshagen and Friedrich Otto

Abstract. We study nonforgetting R- and nonforgetting deterministic RR-automata of window size one, that is, nf-R(1)- and det-nf-RR(1)-automata. Our main result shows that the monotone variants of these two types of restarting automata characterize the regular languages. On the other hand, we prove that already the non-monotone deterministic nonforgetting R(1)-automata accept a class of languages that is incomparable to the class of semi-linear languages with respect to inclusion, but that properly includes the class of languages that are accepted by globally deterministic cooperating distributed systems of stateless deterministic R(1)-automata.

Comments are closed.