Das Wortproblem für Petri-Netze

Beschreibung

Da die Sprachen von Petri-Netzen sämtlich kontextsensitiv sind, ist das Wortproblem entscheidbar. Ziel der Arbeit ist es, ein Tool im Umfeld von PEP zu bauen, das dieses Problem möglichst effizient löst. Das Tool sollte zumindest in der Lage sein, bei Eingabe eines Petri-Netzes (z.B. in PNML) und eines Wortes (bzw. einer Feuersequenz) festzustellen, ob das Wort in der Sprache dieses Petri-Netzes liegt, und es sollte Worte aus der Sprache systematisch (z.B. lexikografisch) aufzählen können.

Das Tool soll später leicht erweiterbar sein, z.B. durch effizientere Algorithmen für spezielle Teilklassen von Petri-Netzen (S-Systeme, T-Systeme, Free-Choice-Netze, syntaktisch beschränkte Netze, etc.). An die Implementierung des Leerheitstests für Sprachen von Petri-Netzen und die algebraisch-symbolische Auswertung mittels Sprachoperationen (und einigen Grundsprachen) ist ebenfalls gedacht. Weiter soll es möglich sein, anstelle von Worten andere Objekte zu untersuchen: etwa Pattern wie “a*b?” als Menge aller Worte, die mit a beginnen und als vorletzten Buchstaben ein b enthalten, oder im Rahmen einer Halbordnungssemantik Pomsets und Pomsetsprachen. Solche weiterführenden Untersuchungen sind z.B. im Rahmen einer Diplomarbeit vorstellbar.