TOWARD UNDERSTANDING THE GENERATIVE CAPACITY OF ERASING RULES IN MATRIX GRAMMARS

摘要

This article presents approaches to the open problem of whether erasing rules can beneliminated in matrix grammars. The class of languages generated by non-erasing matrixngrammars is characterized by the newly introduced linear Petri net grammars. Petri netngrammars are known to be equivalent to arbitrary matrix grammars (without appearancenchecking). In linear Petri net grammars, the marking has to be linear in size with respectnto the length of the sentential form. The characterization by linear Petri net grammars isnthen used to show that applying linear erasing to a Petri net language yields a languagengenerated by a non-erasing matrix grammar. It is also shown that in Petri net grammarsn(with final markings and arbitrary labeling), erasing rules can be eliminated, which yieldsntwo reformulations of the problem of whether erasing rules in matrix grammars can beneliminated.