Erweiterung des Kantenkonzepts dekorativer Graphensetzungssysteme von Einfachkanten über Hyperkanten zu "Superkanten"

  • Type:Diplomarbeit
  • Date:29.03.2007
  • Supervisor:

    Dr. Ing. Tom Gelhausen

  • Person in Charge:Oliver Denninger
  • Links:Links_bearbeiten

  • Als eine flexible und leistungsfähige Methode zur Erzeugung und Bearbeitung von beliebigen Modellen bieten sich die Theorie der Graphtransformationen an. Hierbei handelt es sich um eine ganze Reihe unterschiedlicher Ansätzen zur Manipulation von Graphen. Eine wachsende Zahl von Werkzeugen hat sich der Implementierung verschiedener Ansätze angenommen.

    Für die Generierung von Modellen aus Anforderungsdokumenten beispielsweise sind allerdings Funktionen nötig, die bisher in der Graphentheorie nicht oder nur unzureichend behandelt wurden. Dazu zählen:

    • Die Erweiterung des Konzepts der Kanten als Verbindung zwischen Knoten auf ein allgemeineres Konzept, das Kanten auch als Verbindung zwischen anderen Kanten zulässt. Dies ist nötig, um beispielsweise kausale oder temporale Zusammenhänge zwischen verschiedenen Sätzen eines Dokumentes darstellen zu können. Dieses in der Literatur bisher nicht benannte Konzept wird im Weiteren als „Superkante“ bezeichnet.
    • Die Zuordnung von Rollen zu Graphelementen, wie sie zum Beispiel in Topic Maps möglich ist. Im Falle einfacher, gerichteter Graphen sind die Rollen der beiden durch eine Kante verbundenen Graphelemente klar: Eingangs- und Zielknoten. Bei Hypergraphen liegt die Rollenverteilung leider nicht mehr so eindeutig vor – sie muss explizit vorgenommen werden. Eindeutige Rollen sind aber wichtig um die Bedeutung von Objekten eines Satzes in Graphen darstellen zu können.
    Für das Konzept der Superkanten und die Darstellung von Rollen muss zu Beginn dieser Arbeit ein geeigneter Formalismus entwickelt werden.

    Neben diesen beiden Konzepten muss ein geeignetes Graphtransformationswerkzeug Unterstützung für Hyperkanten, attributierte Knoten und Kanten, sowie eine umfassende Steuerungsmöglichkeit des Transformationsprozesses bieten.

    Da bisher keines der verfügbaren Werkzeuge alle Merkmale bietet, soll das am Lehrstuhl Goos [1] entwickelte Graphtransformationswerkzeug GrGen um die geforderten Merkmale erweitert werden. GrGen bietet bereits eine leistungsfähige Syntax zur Spezifikation von sowohl Metamodellen, Graphen und Transformationsregeln als auch der Ablaufsteuerung der Regeln.

    Für die genannten Funktionen müssen zuerst geeignete Erweiterungen der Syntax von GrGen entwickelt werden, bevor im Anschluss Parser und Regelübersetzer von GrGen um die entsprechende Funktionalität erweitert werden.