Details

Autor(en) / Beteiligte

• Ziegert, Steffen
• Wehrheim, Heike[Akademischer Betreuer]
• Schäfer, Wilhelm[Akademischer Betreuer]

Titel

Graph transformation planning with time and concurrency

Ort / Verlag

Paderborn

Erscheinungsjahr

2016

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 11.02.2016
• ger: Indem sie ein formales Framework für die regelbasierte Modifikation von Graphen und Graph-ähnlichen Strukturen zur Verfügung stellen, ermöglichen es Graphtransformationssysteme, die Dynamik von Strukturen zu modellieren. Sie sind damit besonders zur Modellierung von Rekonfigurationen einer Softwarearchitektur geeignet. Bisher wurden Graphtransformationssysteme jedoch nur selten als Modelle für Planungsverfahren eingesetzt. Motiviert durch die unterschiedlichen Anforderungen zweier grundverschiedener Anwendungsbeispiele, wurden in dieser Arbeit zwei Verfahren zur Planung mit Graphtransformationen entwickelt. Das erste Verfahren erhält die Ausdruckskraft von Graphtransformationssystemen, indem es direkt auf dem Zustandsraum eines Graphtransformationssystems arbeitet. Es verwendet eine domänenunabhängige Heuristik, die die Länge der Lösung eines relaxierten Planungsproblems als Schätzwert liefert. Sie berücksichtigt sowohl die Struktur des Graphen als auch die anwendbaren Graphtransformationen, was eine deutliche Verbesserung gegenüber verwandten Arbeiten darstellt. Das zweite Verfahren legt seinen Fokus auf Zeitaspekte und Nebenläufigkeit. Es bringt einen neuen Formalismus zur Spezifikation von zeitkonsumierenden Graphtransformationen mit sich. Dieser Formalismus stellt sicher, dass mehrere zueinander im Konflikt stehende zeitkonsumierende Graphtransformationen nicht nebenläufig ausgeführt werden können. Des Weiteren ermöglicht er die explizite, regelbasierte Spezifikation von Anforderungen bezüglich ihrer nebenläufigen und eiligen Ausführung. Indem er auf zeitbehafteten Graphtransformationen aufsetzt, ermöglicht er außerdem die Verwendung bereits verfügbarer Verifikationsverfahren.
• eng: By providing a formal framework for the rule-based modification of graphs or graph-like structures, graph transformation systems enable to model the dynamics of structures. As a consequence, they are particularly convenient for modeling reconfiguration behavior of software architectures. However, graph transformation systems have only rarely been employed as system models for planning techniques. Motivated by different requirements arising from two fundamentally different application examples, two approaches for graph transformation planning have been developed in this thesis. The first approach preserves the expressiveness of graph transformation systems by directly working on a graph transformation system's state space. It employs a domain-specific heuristic function that uses the solution length of a relaxed planning problem as heuristic estimate. Taking both the structure of graphs and applicable graph transformations into account, this is a considerable improvement over related work. The second approach puts its focus on timing aspects and concurrency. It comes with a new formalism for the specification of durative graph transformations. This formalism ensures that multiple durative graph transformations with conflicting behavior cannot be executed concurrently. Furthermore, it enables the explicit, rule-based specification of requirements regarding their concurrent and urgent execution. By being based on timed graph transformation systems, it also allows to employ available verification procedures.