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]
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.[pdf]
BibTeX entry
@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.}
}
Copyright Notice
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
