CANCELLATION IN CONTEXT-FREE LANGUAGES - ENRICHMENT BY REDUCTION

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.