Friedrich Otto (2009)
RAIRO - Theoretical Informatics and Applications
Similarity:
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.
Tomasz Jurdziński, Friedrich Otto (2007)
RAIRO - Theoretical Informatics and Applications
Similarity:
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. ...
František Mráz, Friedrich Otto (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
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.
Martin Procházka (2000)
Acta Mathematica et Informatica Universitatis Ostraviensis
Similarity:
Ashish Choudhary, Kamala Krithivasan, Victor Mitrana (2007)
RAIRO - Theoretical Informatics and Applications
Similarity:
A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.
Alexander Okhotin (2004)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence...