TY  - GEN
A1  - Gersdorf, Jörn
T1  - Untersuchungen zu einigen Problemklassen des Context-Matching und Implementierung ausgewählter Algorithmen in der funktionalen Programmiersprache Haskell
N2  - In dieser Diplomarbeit wurde zunächst eine Einführung in das Gebiet der Unifikationstheorie gegeben, um dann zum Teilgebiet des Kontextmatchings zu kommen. Dieses wurde in das Gesamtgebiet der Unifikation eingeordnet. In Anlehnung an [Schm2003] wurde die Komplexität einiger Einschränkungen des Kontextmatchings betrachtet. Insbesondere wurde ein Algorithmus zur Lösung linearer Kontextmatchingprobleme in polynomieller Zeit vorgestellt. Es folgte die Einführung des Transformationsalgorithmus aus [Schm2003] zur Lösung allgemeiner Kontextmatchingprobleme, wobei nach und nach verbesserte Transformationsregeln für einzelne spezielle Problemsituationen vorgestellt wurden. Über [Schm2003] hinausgehend wurden die Regeln Split: Korrespondierende Lochpfade und Konstantenelimination vorgestellt. Im Rahmen der Diplomarbeit wurden die genannten Algorithmen in der funktionalen Programmiersprache Haskell implementiert, wobei auf eine einfache Erweiterbarkeit um neue Transformationsregeln sowie alternative Heuristiken zur Auswahl der in einem Schritt anzuwendenden Transformationsregel geachtet wurde. Die Implementierung (und damit auch die in ihr implementierten Algorithmen) wurde mit Hilfe von zufällig erzeugten Termen auf ihre Leistungsfähigkeit getestet. Hauptaugenmerk lag dabei darauf, inwiefern sich Regeln, die über die Basisregeln aus Tabelle 3.4.1 hinausgehen, positiv auf die Anzahl der Transformationsschritte auswirken. Das Ergebnis ist beeindruckend: durch die Einführung komplexerer Transformationsregeln ließen sich in unseren Testfällen bis zu 87% der Transformationsschritte einsparen, im Durchschnitt immerhin noch 83%. Speziell komplexere Kontextmatchingprobleme mit einer größeren Anzahl an Kontextvariablen profitieren hiervon. Insbesondere die Erkennung korrespondierender Positionen in Verbindung mit der Regel Split führte zu erheblichen Verbesserungen. Die implementierten Algorithmen zur Erkennung korrespondierender Positionen stellen teilweise nur ein notwendiges Kriterium für die Existenz korrespondierender Löcher dar. Dies kann zu fehlerhaften Erkennungen solcher Positionen führen. Wie sich in unseren Tests zeigte, scheint das jedoch kein gravierendes Problem zu sein, da die entsprechenden Split- Transformationen ohnehin äußerst sparsam eingesetzt werden.
Y1  - 2004
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/2872
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-25351
EP  - 158
ER  -