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.

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.

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