Paper Info
Title
Characterizing the regular languages by nonforgetting restarting automata
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.
Year
DOI
Venue
2011
10.1007/978-3-642-22321-1_25
Developments in Language Theory
Keywords
Field
DocType
restarting automaton,main result,non-monotone deterministic,monotone variant,semi-linear language,stateless deterministic r,window size,deterministic rr-automata,regular language
Deterministic context-free grammar,Discrete mathematics,Quantum finite automata,Combinatorics,Nondeterministic finite automaton,Deterministic automaton,Nested word,Computer science,Deterministic finite automaton,Abstract family of languages,Deterministic pushdown automaton
Conference
Citations 
PageRank 
References 
5
0.47
14
Authors
2
Name
Order
Citations
PageRank
Norbert Hundeshagen1214.86
Friedrich Otto224735.87