Bibliography
A Note on Hack's Conjecture, Parikh Images of Matrix Languages and Multiset Grammars
Georg Zetzsche.
A note on Hack's Conjecture, Parikh images of matrix languages
and multiset grammars.
Bericht des Fachbereichs Informatik FBI-HH-B-289/09, Universität
Hamburg, Department Informatik, Vogt-Kölln Str. 30, D-22527 Hamburg,
Germany, 2009.
[pdf]
It is shown that Hack's Conjecture on Petri nets implies that for every language generated by a matrix grammar (without appearance checking), there is a non-erasing matrix grammar generating a language of the same Parikh image. Is is also shown that in this case, the classes of multiset languages generated by arbitrary and monotone multiset grammars coincide.[pdf]
BibTeX
@TECHREPORT{Zetzsche09a,
AUTHOR = {Zetzsche, Georg},
TITLE = {A Note on {Hack's Conjecture}, {Parikh} Images of
Matrix Languages and Multiset Grammars},
NUMBER = {FBI-HH-B-289/09},
YEAR = {2009},
TYPE = FBIBericht,
INSTITUTION = FBIUniHHab2006,
ADDRESS = FBIUniAdresseen,
ABSTRACT = {It is shown that Hack's Conjecture on Petri nets implies
that for every language generated by a matrix grammar
(without appearance checking), there is a non-erasing
matrix grammar generating a language of the same Parikh
image. Is is also shown that in this case, the classes of
multiset languages generated by arbitrary and monotone
multiset grammars coincide.}
}
