DEPARTMENT FÜR INFORMATIK, Abteilung Parallele Systeme Sekretariat: TEL: (0441) 7 98 – 45 22 FAX: (0441) 7 98 – 29 65 INTERNET: www.uni-oldenburg.de/parsys/arbeiten Abschlussarbeit Synthese elementarer Petrinetze Hintergrund Aufgabenstellung Bei der Verwendung und Analyse von Petrinetzen werden oft Erreichbarkeitsgraphen erzeugt. Bei diesen handelt es sich formal um (beschriftete) Transitionssysteme. Der Algorithmus zur Erzeugung des Erreichbarkeitsgraphen basiert im wesentlichen auf wiederholtes Feuern von Transitionen, ist also leicht nachvollziehbar und seit langem bekannt. Die Umkehrung wird als Petrinetz Synthese bezeichnet. Bei dieser wird aus einem Transitionssystem ein Petrinetz erzeugt, dessen Erreichbarkeitsgraph isomorph zum ursprüngliche Erreichbarkeitsgraphen sein soll. Synthese–Algorithmen sind schwieriger als der Erreichbarkeitsgraphen–Algorithmus, auch der Berechnungsaufwand dieser Algorithmen ist groß, sie benötigen bereits bei kleinen Eingaben relativ viel Rechenzeit und Speicher. Daher ist die Petrinetz Synthese weiterhin Gegenstand aktueller Forschung. Es werden Algorithmen entwickelt, die schneller sind, jedoch nur funktionieren, wenn das Transitionssystem bestimmte Eigenschaften erfüllt oder wenn das erzeugte Petrinetz bestimmte Eigenschaften aufweisen soll. Implementierung der Petrinetz Synthese für elementare Petrinetze: Elementare Petrinetze sind eine besondere Art sicherer Petrinetze, bei denen Transitionen nicht nur durch im Vorbereich fehlende Token, sondern auch durch bereits im Nachbereich vorhandene Token am Feuern gehindert werden. In einem aktuellem Buch beschreiben Badouel, Bernadinello und Darondeau einen Algorithmus für die Synthese solcher Netze. Unsere Software APT (Analyse von Petrinetzen und Transitionssystem) kann bereits normale Petrinetze mittels anderer Methoden synthetisieren, soll jedoch zukünftig auch elementare Petrinetze synthetisieren können. Betreuer Organisatorisches • • • • Möglicher Anfangszeitpunkt: jederzeit Art der Arbeit: Masterarbeit, ggf. auch als Bachelorarbeit Ansprechpartner: Uli Schlachter Nützliche Vorkenntnisse: Petrinetze, Transitionssysteme Prof. Dr. Eike Best Uli Schlachter, M. Sc. (0441) 7 98 – 29 73 [email protected] (0441) 7 98 – 34 95 [email protected]
© Copyright 2024 ExpyDoc
