It is shown that the class of left-to-right regular languages coincides with the class of languages that are accepted by monotone deterministic -automata, in this way establishing a close correspondence between a classical parsing algorithm and a certain restricted type of analysis by reduction.
We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are equipped with an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of word languages that are linearizations of context-free trace languages.
Several types of systems of parallel communicating restarting automata are introduced and studied. The main result shows that, for all types of restarting automata X, centralized systems of restarting automata of type X have the same computational power as non-centralized systems of restarting automata of the same type and the same number of components. This result is proved by a direct simulation. In addition, it is shown that for one-way restarting automata without auxiliary symbols, systems of...
It is known that the weakly monotone restarting automata accept exactly the growing context-sensitive languages. We introduce a measure on the degree of weak monotonicity and show that the language classes obtained in this way form strict hierarchies for the various types of deterministic and nondeterministic restarting automata without auxiliary symbols.
It is known that the weakly monotone restarting automata accept exactly the growing context-sensitive languages. We introduce a measure on the degree of weak monotonicity and show that the language classes obtained in this way form strict hierarchies for the various types of deterministic and nondeterministic restarting automata without auxiliary symbols.
As already 2-monotone -automata accept -complete languages, we introduce a restricted variant of -monotonicity for restarting automata, called . For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that -automata that are sequentially monotone of degree for any only accept context-free languages.
We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are equipped with an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of word languages that are linearizations of context-free trace languages.
In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word is accepted by such an automaton if, starting from the initial configuration that corresponds to input , the word is reduced to the empty word by a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context of McNaughton...
Page 1