Projekt: Anwendung von Ergebnissen über Petrinetze in der Theorie der Matrixgrammatiken

Laufzeit: seit Juni 1993

Schlagworte: Matrixgrammatiken, gesteuerte kontextfreie Ersetzungen, Petrinetze, Semilinearität

Ziele:

Immer dort, wo bei Grammatiken in deren Ableitungen die Anordnung der Symbole in der Satzform keine entscheidende Rolle spielt, lassen sich Petrinetze zur Simulation verwenden und deren Analysealgorithmen einsetzen. Die bislang ungelöste Frage, ob jede Matrixsprache über einem einelementigen Alphabet regulär ist, konnte mit dem Algorithmus zur Entscheidung der Semilinearität einer Petrinetzsprache positiv entschieden werden. Es wurde gezeigt, daß jede Matrixsprache über einem einelementigen Alphabet regulär ist und wie entschieden werden kann, ob eine Matrixgrammatik eine endliche Menge generiert.

Publikationen:

M. Jantzen, D. Hauschildt:

Petri net algorithms in the theory of matrix grammars; Acta Informatica 31, 1994, 719-728