Petri Net Algorithms in the Theory of Matrix Grammars
Jantzen, Matthias ; Hauschildt, Dirk
| URL | http://edoc.sub.uni-hamburg.de/informatik/volltexte/2009/27/ |
|---|---|
| Document type: | TechReport |
| Series: | Berichte des Fachbereichs Informatik der Universität Hamburg |
| Volume Number: | 167 |
| Language: | English |
| Year of creation: | 1994 |
| Date of publication: | 17.08.2009 |
| Keywords from authority file SWD (German): | Algorithmus , Grammatik , Matrix <Mathematik> |
| Free keywords (German): | Petrinetze , Grammatik , Matrix , Algorithmen |
| Free keywords (English): | Petri Net Algorithms , Matrix Grammars, Petri Nets |
| Dewey Decimal Classification: | Computer science |
| BK - classification: | 31.12 , 54.10 |
Abstract in English:
This paper shows that the languages over a one-letter alphabet generated by a context-free matrix grammar are always regular. Moreover we give a decision procedure for the question of whether a context-free matrix language is finite. Hereby we strengthen a result of [Mk 92] and settle a number of open questions in [DP 89]. Both results are obtained by a reduction to Petri net problems.
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.