Advertisement
Published in:
2011 | OriginalPaper | Chapter
Characterizing the Regular Languages by Nonforgetting Restarting Automata
Authors : Norbert Hundeshagen, Friedrich Otto
Published in: Developments in Language Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.