Algorithmen für Reengineering und Synthese (ARS)
Zusammenfassung der Projektergebnisse
Zielsetzung des Projekts war die Entdeckung von möglichst effizienten Synthese-Algorithmen und -Methoden, wenn verteilte Systeme durch Petrinetze dargestellt werden und Spezifikationen durch beschriftete Transitionssysteme Ergebnisse des Projekts sind: • Ein Spektrum effizienter und getesteter Algorithmen für Spezialfälle, wie sie in den Anwendungsbereichen Geschäftsprozessmodellierung oder Hardwareentwurf vorkommen. • Eine Systematik zur Integration von Quick Fail in einer zweiphasigen (Prä-)Synthese. wodurch sich widersprüchliche Spezifikationen frühzeitig erkennen und verbessern lassen. • Eine Methode zur Auswahl verschiedener Synthesealgorithmen in Abhängigkeit von einer gewünschten Zielklasse von Systemen. • Die Erweiterbarkeit auf tolerante Spezifikationssprachen wie reguläre Sprachen, auf reiche wie modale Transitionssysteme, oder auf Fragestellungen wie simultane Synthese. • Theoretische Neuentwicklungen inklusive der Benutzung von Näherungsmethoden und inklusive der Beantwortung mehrerer offener Fragen aus der bekannten Literatur. Das unmittelbarste Anwendungspotential liegt in den beiden oben genannten Bereichen. Weitere Anwendungsbereiche erschließen sich voraussichtlich durch die Erweiterung auf modale Transitionssysteme, insbesondere wenn in einem Folgeprojekt die Übertragung von Ergebnissen auf beschriftete (statt unbeschriftete) Petrinetze gelingen sollte.
Projektbezogene Publikationen (Auswahl)
- “Bounded Petri Net Synthesis from Modal Transition Systems is Undecidable,” in Proc. 27th International Conference on Concurrency Theory, CONCUR 2016, August 23-26, 2016, Québec City, Canada, 2016, p. 15:1-15:14
U. Schlachter
(Siehe online unter https://doi.org/10.4230/LIPIcs.CONCUR.2016.15) - “Characterising Petri Net Solvable Binary Words," in Proc. Application and Theory of Petri Nets and Concurrency - 37th International Conference, PETRI NETS 2016, Torún, Poland, June 19-24, 2016. Proceedings, 2016, 39-58
E. Best, E. Erofeev, U. Schlachter, H. Wimmel
(Siehe online unter https://doi.org/10.1007/978-3-319-39086-4_4) - "K-Bounded Petri Net Synthesis from Modal Transition Systems.” in Proc. 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany, 2017, p. 6:1-6:15
U. Schlachter, H. Wimmel
(Siehe online unter https://doi.org/10.4230/LIPIcs.CONCUR.2017.6) - "Bounded choice-free Petri net synthesis: algorithmic issues," Acta Inf., vol. 55, iss. 7, pp. 575-611, 2018
E. Best, R. Devillers, U. Schlachter
(Siehe online unter https://doi.org/10.1007/s00236-017-0310-9) - "Over-Approximative Petri Net Synthesis for Restricted Subclasses of Nets.” in Proc. Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings, 2018, pp. 296-307
U. Schlachter
(Siehe online unter https://doi.org/10.1007/978-3-319-77313-1_23) - “Pre-synthesis of Petri nets based on prime cycles and distance paths," Sci. Comput. Program., vol. 157, pp. 41-55, 2018
E. Best, R. Devillers
(Siehe online unter https://doi.org/10.1016/j.scico.2017.07.005)
