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

Bei der Verifikation analysiert man das Verhalten von strukturellen Objekten wie Programmen oder Petrinetzen. Bei der Systemsynthese steht eine umgekehrte Frage im Vordergrund: Gibt es zu einem gegebenen Verhalten ein strukturelles Objekt, das dieses Verhalten implementiert? Beide Fragen sind in der Informatik intensiv studiert worden und es gibt ein weites Anwendungsspektrum. Im vorliegenden Projekt geht es speziell um Verhalten, das mit Hilfe eines (sequentiellen) Transitionssystems spezifiziert wird und mit Hilfe eines (parallelen, in der Regel viel kleineren) Petrinetzes realisiert werden soll. Im System-Reengineering wird eine verwandte Fragestellung untersucht: Gibt es zu einer bereits existierenden Implementierung eine `bessere' (z.B. eine weniger sequentielle oder eine passenderer Gestalt)? Diese Fragen wurden intensiv untersucht, auch im Hinblick auf Algorithmen, die der automatischen Erzeugung von Implementierungen aus Spezifikationen dienen. Als solche sind sie in aller Allgemeinheit viel zu kostspielig, selbst wenn die beteiligten Objekte endlich sind. Die volle Allgemeinheit ist allerdings bei Anwendungen oft nicht gefragt, wenn man die beteiligten Klassen von Objekten strukturell eingrenzen kann. Deshalb ist es interessant, zu erforschen und zu erfahren, ob sich spezifische Synthese- und Reengineering-Methoden finden lassen, die in speziellen Situationen schneller und besser sind als allgemeine. Beim Schaltkreisentwurf untersucht man zum Beispiel getaktete Systeme im (normalen) synchronen Fall und weitestgehend persistente, zeitunkritische Systeme im asynchronen Fall. Einerseits erhofft man sich durch solche Restriktionen die Gewinnung effizienter Synthese- und Reengineering-Algorithmen. Andererseits erhofft man sich auch eine genauere Entsprechung zwischen Klassen struktureller und Klassen dynamischer Objekte, als dies im Allgemeinfall gegeben ist. In diesem Projekt wird die systematische Untersuchung solcher Entsprechungen sowohl in mathematischer als auch in algorithmischer Hinsicht (zur Gewinnung effizienter Synthese- und Reengineering-Algorithmen) im Rahmen von Transitionssystemen (als dynamische Objekte) und Petrinetzen (als strukturelle Objekte) beabsichtigt. Zu Beginn und im Verlauf des Projekts wird die Klasse persistenter Systeme untersucht. Intuitiv bedeutet Persistenz, dass eine freigegebene Aktion nicht durch andere Aktionen behindert werden kann. Solche Systeme sind nichttrivial und von praktischer Relevanz. Die Untersuchungen werden im Projektverlauf auf andere Systemklassen ausgeweitet. Besondere Aufmerksamkeit soll der Frage gewidmet werden, ob ein System nicht nur parallel implementiert, sondern auch physisch verteilt werden kann.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Professor Dr. Eike Best, bis 10/2018