Studienarbeit

[Batz05]

Gernot Veit Batz, Generierung von Graphersetzungen mit programmierbarem Suchalgorithmus, IPD Goos, 2005.

Zusammenfassung

Im Rahmen der vorliegenden Studienarbeit wurde ein neues Backend für das generativ arbeitende Graphersetzungswerkzeug GrGen implementiert. Für das Teilgraphmatching kommt ein programmierbarer Suchalgorithmus zum Einsatz, wodurch der nachträgliche Einbau von dynamischen Suchplanern vorbereitet ist. Die Datenstruktur für den bearbeiteten Graphen folgt dem Prinzip der rahmenbasierten Speicheranordnung, das von Heiko Dörr vorgeschlagen worden ist. Überlegungen zum praktikablen Einsatz der virtuellen Maschine weisen auf eine ebenfalls von Heiko Dörr entwickelte Methode hin, mit der sich g¨unstigere Matcher-Programme konstruieren lassen. Mit Hilfe der besonderen Graphspeicherung geht dies bis hin zu einem Teilgraphmatching, dessen asymptotischer Zeitaufwand proportional zur Größe des zu findenden Graphmusters ist. Wegen der NP-Vollständigkeit des zugrunde liegenden Problems ist dies natürlich nicht immer möglich. Mit einer naiven Graphspeicherung arbeitete das System im Experiment jedoch schneller. Im Vergleich zu dem bisher verwendeten Backend, das die anfallenden Aufgaben an eine SQL-Datenbank delegiert, bringt das neue Backend einen deutlichen Laufzeitvorteil. Unzusammenhängende Graphmuster, negative Anwendungsbedingungen (NACs) und Attributberechnungen werden jedoch nicht unterstützt.

Autoren

Ex-Studenten Gernot Veit Batz