Algorithms for Reengineering and Synthesis (ARS)

• Applicant: Professor Dr. Ernst-Rüdiger Olderog, since 11/2018
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 265430725

• Final Report Year: 2019

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
  
• “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
  
• "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
  
• "Bounded choice-free Petri net synthesis: algorithmic issues," Acta Inf., vol. 55, iss. 7, pp. 575-611, 2018
  E. Best, R. Devillers, U. Schlachter
  
• "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
  
• “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