Erasing in petri net languages and matrix grammars

Link:
Autor/in:
Beteiligte Personen:
  • Diekert, Volker
  • Nowotka, Dirk
Verlag/Körperschaft:
Springer
Erscheinungsjahr:
2009
Medientyp:
Text
Beschreibung:
  • It is shown that applying linear erasing to a Petri net language yields a language generated by a non-erasing matrix grammar. The proof uses Petri net controlled grammars. These are context-free grammars, where the application of productions has to comply with a firing sequence in a Petri net. Petri net controlled grammars are equivalent to arbitrary matrix grammars (without appearance checking), but a certain restriction on them (linear Petri net controlled grammars) leads to the class of languages generated by non-erasing matrix grammars. It is also shown that in Petri net controlled grammars (with final markings and arbitrary labeling), erasing rules can be eliminated, which yields a reformulation of the problem of whether erasing rules in matrix grammars can be eliminated. © 2009 Springer Berlin Heidelberg.
Lizenz:
  • info:eu-repo/semantics/closedAccess
Quellsystem:
Forschungsinformationssystem der UHH
Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/c9f3bbc4-067d-4758-a586-c976bdd3f0de