Algorithmen für Synthese und Präsynthese auf Grundlage der Strukturtheorie von Petrinetzen (ASYST)

• Antragsteller: Professor Dr. Ernst-Rüdiger Olderog, seit 11/2018
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 336738132

Das Projekt leistet Beiträge zur Synthese von Petrinetzen aus Transitionssystemen. Die Grundkonzepte dieser Theorie und die dazu gehörigen Algorithmen sind in der Monographie Badouel, Bernardinello, Darondeau: Petri Net Synthesis (Springer-Verlag, 2015) beschrieben. Es handelt sich um ein aktives, stark anwendungsträchtiges Forschungsgebiet; am bekanntesten dürften Anwendungen in den Bereichen asynchroner Hardware-Entwurf und Process Mining sein. In beiden Fällen ist man an speziellen Petrinetzen interessiert (wahlfreie Netze und Marked Graphs). Aus solchen Gründen ist es wichtig, die Synthese bezüglich spezieller Petrinetzklassen zu optimieren. Zur Erschließung weiterer Anwendungsgebiete ist die Optimierung auch bezüglich anderer Petrinetzklassen wesentlich.Ein allgemeiner Petrinetzsynthesealgorithmus beinhaltet das Lösen sehr vieler gleichartiger linearer Ungleichungssysteme. Dadurch werden Regionen (d.h.: geeignete Teilstrukturen) eines Transitionssystems konstruiert. Fokussiert man diesen Algorithmus auf spezielle Zielklassen, kommen im Allgemeinen Ungleichungssysteme hinzu, und der Algorithmus kann sich sogar verlangsamen. Ansatz des Projekts ist es, diesem Verlangsamungseffekt durch Ausnutzen vorhandenen Wissens über strukturtheoretische Eigenschaften der Zielklassen entgegenzuwirken. Für die Zielklasse der Marked Graphs wurde bereits gezeigt, dass ein Algorithmus existiert, der nur die absolut nötigen Regionen sehr effizient erzeugt. Für andere Zielklassen soll untersucht werden, auf welche Weise vorhandene (und neu zu entwickelnde) zielklassenbezogene Strukturtheorie dazu verwendet werden kann, die Konstruktion von Regionen zu minimieren bzw. zu beschleunigen. Als allgemeine Methode verwenden wir eine Präsynthesephase, während der eine Eingabe explizit auf strukturtheoretische Eigenschaften hin geprüft werden kann. Die darauf folgende Synthesephase lässt sich -- wie im Projekt nachzuweisen wäre, und was im Fall wahlfreier Netze schon gelungen und veröffentlicht worden ist -- nach Kenntnis dieser Eigenschaften optimieren.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Professor Dr. Eike Best, bis 10/2018