The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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...
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...
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