Synthese von Petrinetzen auf der Basis der Union/Find-Verfahren
Zusammenfassung der Projektergebnisse
Das Syntheseproblem für Petrinetze sucht für einen gegebenen Graphen ein Petrinetz, das diesen Graphen als seinen Erreichbarkeitsgraph (Zustandsraum) produziert. Es wird gelöst, indem Lösungen für aus dem Graphen ablesbare Separierungsprobleme gefunden werden. Im Vorhaben konnten spezifische Schwächen eines vielversprechenden Ansatzes nicht in ausreichendem Umfang behoben werden. Die wesentliche Schwäche ist dabei, dass einzelnen erfolgreichen Probleminstanzen mit bis zu 10 Millionen Graphknoten andere deutlich kleinere Instanzen (mit wenigen 10.000 Knoten) gegenüberstehen, die nicht erfolgreich gelöst werden können. Eine ganze Reihe von Ideen zur Steigerung der Leistungsfähigkeit erwiesen sich als nicht tragfähig. Dies wurde so bei der Konzeption des Vorhabens nicht erwartet. Abweichend vom ursprünglichen Projektplan wurden generelle Komplexitätsfragestellungen bearbeitet. Hier wurde Stand der Forschung erheblich erweitert.
Projektbezogene Publikationen (Auswahl)
-
Finding an Optimal Label-Splitting to Make a Transition System Petri Net Implementable: a Complete Complexity Characterization. ICTCS 2020: 131-144
Ronny Tredup
-
The complexity of synthesizing elementary net systems relative to natural parameters. Journal of Computer and System Sciences, 110, 37-54.
Rosenke, Christian & Tredup, Ronny
-
On the parameterized complexity of the synthesis of Boolean nets with restricted place environments. Theoretical Computer Science, 890 (2021, 10), 36-69.
Tredup, Ronny & Erofeev, Evgeny
-
The Complexity of Synthesis of b-Bounded Petri Nets. Fundamenta Informaticae, 183(1-2), 125-167.
Tredup, Ronny
