Bibliographie

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.

Kurzfassung: 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-Eintrag

@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-Hinweis

Diese Informationen werden zur Verfügung gestellt, um technische und Forschungsarbeiten zeitnah bekannt zu geben. Das Urheberrecht und alle damit verbundenen Rechte verbleiben bei den Autoren bzw. anderen Rechteinhabern. Von jedem, der Informationen dieser Seiten übernimmt, wird erwartet, dass er sich an die jeweiligen Bedingungen und Beschränkungen der Rechteinhaber hält. Meist bedeutet dies, dass die hier bereitgestellten Daten nicht ohne explizite Genehmigung der Rechteinhaber weiterveröffentlicht werden dürfen.