Displaying similar documents to “Sequential monotonicity for restarting automata”

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.

Left-to-right regular languages and two-way restarting automata

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.

Returning and non-returning parallel communicating finite automata are equivalent

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.

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