Page 1

Displaying 1 – 3 of 3

Showing per page

On the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin (2004)

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

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

On the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin (2010)

RAIRO - Theoretical Informatics and Applications

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

On the syntactic complexity of tree series

Symeon Bozapalidis, Antonios Kalampakas (2010)

RAIRO - Theoretical Informatics and Applications

We display a complexity notion based on the syntax of a tree series which yields two distinct hierarchies, one within the class of recognizable tree series and another one in the class of non-recognizable tree series.

Currently displaying 1 – 3 of 3

Page 1