Displaying similar documents to “Left-to-right regular languages and two-way restarting automata”

On the equivalence of linear conjunctive grammars and trellis automata

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...

Hierarchies of weakly monotone restarting automata

František Mráz, Friedrich Otto (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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.

Sequential monotonicity for restarting automata

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. ...

CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store

Benedek Nagy, Friedrich Otto (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

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.

On the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin (2010)

RAIRO - Theoretical Informatics and 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...