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.}
}
