Bibliography

Erasing in Petri Net Languages and Matrix Grammars

Georg Zetzsche.
Erasing in Petri net languages and matrix grammars.
In Volker Diekert and Dirk Nowotka, editors, Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings, volume 5583 of Lecture Notes in Computer Science, pages 490-501, 2009.

It is shown that applying linear erasing to a Petri net language yields a language generated by a non-erasing matrix grammar. The proof uses Petri net controlled grammars. These are context-free grammars, where the application of productions has to comply with a firing sequence in a Petri net. Petri net controlled grammars are equivalent to arbitrary matrix grammars (without appearance checking), but a certain restriction on them (linear Petri net controlled grammars) leads to the class of languages generated by non-erasing matrix grammars.
It is also shown that in Petri net controlled grammars (with final markings and arbitrary labeling), erasing rules can be eliminated, which yields a reformulation of the problem of whether erasing rules in matrix grammars can be eliminated.

BibTeX

@INPROCEEDINGS{Zetzsche09,
 AUTHOR    = {Zetzsche, Georg},
 TITLE     = {Erasing in {Petri} Net Languages and Matrix Grammars},
 BOOKTITLE = {Developments in Language Theory, 13th International
       Conference, DLT 2009, Stuttgart, Germany, June 30--July 3,
       2009.  Proceedings},
 EDITOR    = {Diekert, Volker and Nowotka, Dirk},
 PAGES     = {490--501},
 YEAR      = 2009,
        VOLUME    = 5583,
        SERIES    = LNCS,
 ABSTRACT  = {It is shown that applying linear erasing to a Petri net
       language yields a language generated by a non-erasing
       matrix grammar.  The proof uses Petri net controlled
       grammars. These are context-free grammars, where the
       application of productions has to comply with a firing
       sequence in a Petri net. Petri net controlled grammars are
       equivalent to arbitrary matrix grammars (without
       appearance checking), but a certain restriction on them
       (linear Petri net controlled grammars) leads to the class
       of languages generated by non-erasing matrix grammars.

       It is also shown that in Petri net controlled grammars
       (with final markings and arbitrary labeling), erasing
       rules can be eliminated, which yields a reformulation of
       the problem of whether erasing rules in matrix grammars
       can be eliminated.}
}