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...
The cyclic shift of a language , defined as =, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov’s pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl. 11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! 2, which shows that the state complexity...
The cyclic shift of a language , defined as SHIFT() = {},
is an operation known to preserve both regularity and context-freeness.
Its descriptional complexity has been addressed in Maslov's
pioneering paper on the state complexity of regular language operations
[
(1970) 1373–1375],
where a high lower bound for partial DFAs using a growing alphabet was given.
We improve this result by using a fixed 4-letter alphabet,
obtaining a lower bound (n-1)! . 2(n-1)(n-2),
which shows that...
Download Results (CSV)