A Note on Hack's Conjecture, Parikh Images of Matrix Languages and Multiset Grammars
| URL | http://edoc.sub.uni-hamburg.de/informatik/volltexte/2009/71/ |
|---|---|
| Dokumentart: | Report (Bericht) |
| Schriftenreihe: | Berichte des Fachbereichs Informatik der Universität Hamburg |
| Bandnummer: | 289 |
| Sprache: | Deutsch |
| Erstellungsjahr: | 2009 |
| Publikationsdatum: | 27.08.2009 |
| SWD-Schlagwörter: | Petri-Netz |
| Freie Schlagwörter (Deutsch): | Petri-Netze |
| Freie Schlagwörter (Englisch): | Petri nets |
| DDC-Sachgruppe: | Informatik |
| BK - Klassifikation: | 54.10 |
Kurzfassung auf Englisch:
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.
Kurzfassung auf Deutsch:
Es wird gezeigt, dass die Hack'sche Vermutung übe Petri-Netze impliziert, dass es für jede von einer Matrix-Grammatik (ohne Vorkommenstest) erzeugte Sprache eine nicht-löschende solche Grammatik gibt, die eine Sprache vom gleichen Parikh-Bild erzeugt. Es wird auch gezeigt, dass in diesem Fall die Klassen der Multiset-Sprachen, die von beliebigen bzw. monotonen Multiset-Grammatiken erzeugt werden, übereinstimmen.
Hinweis zum Urherberrecht
Für Dokumente, die in elektronischer Form über Datenenetze angeboten werden, gilt uneingeschränkt das Urheberrechtsgesetz (UrhG). Insbesondere gilt:
Einzelne Vervielfältigungen, z.B. Kopien und Ausdrucke, dürfen nur zum privaten und sonstigen eigenen Gebrauch angefertigt werden (Paragraph 53 Urheberrecht). Die Herstellung und Verbreitung von weiteren Reproduktionen ist nur mit ausdrücklicher Genehmigung des Urhebers gestattet.
Der Benutzer ist für die Einhaltung der Rechtsvorschriften selbst verantwortlich und kann bei Mißbrauch haftbar gemacht werden.