Petri Net Languages and One-Sided Dyck-Reductions On Context-Free Sets

In [2, 6, 8, 9] cancellation grammars (or grammars related to them) are defined and their relation to well-known families of languages are studied. Savitch showed in [9] that the class of EOL languages can be obtained from the context-free sets (CF) by iteratively and completely cancelling one matching pair xx̄ of parenthesis x and x̄. This type of reduction is here called a Dyck₁-reduction on a set L which can be taken from any family of languages — not only the context-free sets — and thus need not be definable by certain restricted classes of grammars as in [2, 9]. In this short note we will show that we get all (free) terminal Petri net languages and all transition sequences from the context-free sets by Dyck₁-reductions and, moreover, each non-erasing homomorphic image thereof, the corresponding families denoted by L and P as in [7].