Algorithmen für Reengineering und Synthese (ARS)

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

• Erstellungsjahr: 2019

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
  
• “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