The following problem is shown to be decidable: Given a context-free g
rammar G and a string w is-an-element-of X, does there exist a string
u is-an-element-of L(G) such that w is obtained from u by deleting al
l substrings u(i) that are elements of the symmetric Dyck set D1? The
intersection of any two context-free languages can be obtained from o
nly one context-free language by cancellation either with the smaller
semi-Dyck set D1' subset-of D1* or with D1* itself. Also, the followi
ng is shown here for the first time: if the set EQ:={x(n)x(n)BAR\n is-
an-element-of N} subset-of D1' is used for this cancellation, then ea
ch recursively enumerable set can be obtained from linear context-free
languages. Previous work has shown that cancellation of substrings fr
om the semi-Dyck language D1' or from any of the former languages D1*
, or EQ, allows one to obtain the following from the context-free lang
uages: any terminal Petri net language [14,16], the intersections of a
ny context-free with a terminal Petri net language, and the nested ite
rated substitution thereof [15]. We generalize this characterization b
y showing that linear context-free languages suffice for generating te
rminal Petri net languages. In proving this we obtain a new closure pr
operty of the family of Petri net languages which is not shared by the
context-free sets.