The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Bounded push down 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...

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.

Unambiguous recognizable two-dimensional languages

Marcella Anselmo, Dora Giammarresi, Maria Madonia, Antonio Restivo (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider the family UREC of unambiguous recognizable two-dimensional languages. We prove that there are recognizable languages that are inherently ambiguous, that is UREC family is a proper subclass of REC family. The result is obtained by showing a necessary condition for unambiguous recognizable languages. Further UREC family coincides with the class of picture languages defined by unambiguous 2OTA and it strictly contains its deterministic counterpart. Some closure and non-closure...