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.

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.

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.