Graphtransformationssysteme

Informationen

In der Informatik dreht sich Vieles um das Spezifizieren, Modellieren, Konstruieren und Anaysieren informationsverarbeitender Systeme. Die Zustände solcher Systeme können abstrakt mit Graphen beschrieben werden, wobei Knoten Systemkomponenten und Kanten Relationen zwischen Komponenten darstellen. Das Verhalten solcher Systeme kann als Menge seiner möglichen schrittweisen Zustandsveränderungen beschrieben werden. Oft betrifft eine Zustandsveränderung nur einen kleinen Teil eines Systems. Zustandsveränderungen können durch Systeme von endlich vielen Transformationsregeln auf den Graphen (Zuständen) definiert werden.

Graphtransformationssysteme können (mindestens) für zwei Zwecke benutzt werden:

• Eine Graphsprache (Menge von erreichbaren Zuständen) kann mit einer Grammatik beschrieben werden, die aus einem Startgraphen (Startzustand) und generativen Regeln besteht, mit denen die Graphen abgeleitet werden. Graphtransformationsregeln definieren eine Berechnungsmodell auf Graphen: Für beliebige Eingabegraphen können durch Anwendung der Regeln Ausgabegraphen berechnet werden, wobei im Allgemeinen verschiedenen Ausgaben errechnet werden.

Prominente Beispiele von regelbasierten Systemen sind kontextfreie Wortgrammatiken für die Syntax von Programmiersprachen, und Termersetzungssysteme und Klausellogik für die Semantik funtkionaler und logischer Programme. Graphgrammatiken können die Struktur visueller Softwaremodelle definieren, und Graphtransformationssysteme die Evolution dieser Modelle beschreiben.

In diesen Kurs werden wir die Grundlagen regelbasierter Systembeschreibungen auf der Basis von Zeichenketten, Bäumen und Graphen studieren, sowie regelbasierte Sprachen und regelbasierte Werkzeuge kennen lernen. In den Kurs sind Übungen im Umfang einer SWS integriert.

Voraussetzung: Inhalte von Programmiersprachen und von Theoretische Informatik I und II.

Studienbegleitende Leistungsnachweise (über 6 ETCS-Punkte) können durch regelmäßiges Bearbeiten von Übungsaufgaben (in Zweiergruppen) und eventuell ein Fachgespräch am Semesterende erworben werden.

Material zum Kurs

• Kurs: Inhalt und Material .
• Hinweise auf Sprachen und Werkzeuge.
• Weiterführende Literatur.
• Der Ablaufplan des Kurses und die Liste der TeilnehmerInnen werden in stud.ip verwaltet. (Unter Regelbasierte Systeme)