Set-theoretical operations on $k$-multiple languages

Jaroslav Král

Skip to main content (access key 's'), Skip to navigation (access key 'n'), Accessibility information (access key '0')

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

Displaying similar documents to “Set-theoretical operations on $k$ -multiple languages”

Bounded push down automata

Branislav Rovan (1969)

Kybernetika

Similarity:

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

Displaying similar documents to “Set-theoretical operations on k -multiple languages”

Bounded push down automata

On the equivalence of linear conjunctive grammars and trellis automata

Displaying similar documents to “Set-theoretical operations on $k$ -multiple languages”