Algorithms for Reengineering and Synthesis (ARS)
Final Report Abstract
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.
Publications
- “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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at https://doi.org/10.1016/j.scico.2017.07.005)
