Verallgemeinerte kontextsensitive Termersetzung

01.02.2008 - 31.01.2011
Forschungsförderungsprojekt
Verallgemeinerte kontextsensitive Termersetzung Termersetzung ist ein fundamental wichtiger Formalismus, der in vielen Gebieten der theoretischen und praktischen Informatik verwendet wird. Die Grundidee bei Termersetzung ist die Ersetzung von Gleichem durch Gleiches in gegebenen (symbolischen) Objekten (hier: Termen), bis schließlich ein Endergebnis (Normalform) erreicht wird, das das Ergebnis der Berechnung darstellt. Operational ist nicht festgelegt, wie die einzelnen Ersetzungsschritte stattfinden. Das heißt, i.a. sind solche "Ersetzungs-Ableitungen" hochgradig nichtdeterministisch. Andererseits ist es in bestimmten Gebiten wie etwa im "gleichungsbasierten Programmieren" und bei "ausführbaren Spezifikationen" wichtig, daß der Berechungsprozeß gesteuert und der Nichtdeterminismus bei der Berechnung reduziert werden kann, um die Effizienz zu verbessern oder um überhaupt die gewünschten Berechungsresultate zu erhalten. Ein zentraler Ansatz, um dieses Ziel zu erreichen, ist Kontextsensitivität. Hierbei bestimmt die Struktur der Terme, welche nächsten Schritte tatsächlich möglich sind, in Abhängigkeit vom Kontext des betrachteten Teilterms. Im wesentlichen funktioniert dieser Ansatz so, daß man (global) für jedes Funktionssybol festlegt, welche seiner Argumente (für Ersetzungen) zugänglich sind und welche nicht (also "verboten" sind). Ansätze, die auf diesem Konzept von Kontextsensitivität basieren, wurden in den letzten 15 Jahren intensiv untersucht, mit beträchtlichem Erfolg. Jedoch ist die Ausdrucksstärke solcher traditioneller Ansätze für Kontextsensitivität recht beschränkt. Wir schlagen vor, das zugrundeliegende Konzept von Kontextsensitivität in verschiedene Richtungen zu verallgemeinern, um eine erhöhte Ausdrucksstärke und bessere theoretische sowie praktische Ergebnisse zu erzielen, wobei gleichzeitig die praktische Umsetzbarkeit gewährleistet bleiben muß. Insbesondere wird angestrebt, die neue Idee von "verbotenen Termmustern" näher zu untersuchen, die während des Berechungsprozesses invariant bleiben müssen. Der zu entwickelnde Ansatz verallgemeinerter kontextsensitiver Termersetzung wird schließlich evaluiert werden, d.h. implementiert und mit anderen bekannten Ansätzen im Hinblick auf theoretische Eigenschaften, Ausdrucksstärke, praktische Anwendbarkeit, Effizienz und Handhabbarkeit untersucht werden.

Personen

Projektleiter_in

Projektmitarbeiter_innen

Institut

Förderungmittel

  • Österr. Akademie der Wissenschaften (National) Österreichische Akademie der Wissenschaften (ÖAW)

Forschungsschwerpunkte

  • Computational Intelligence: 100%

Schlagwörter

DeutschEnglisch
Termersetzungterm rewriting
Kontextsensitivitätcontext-sensitivity

Publikationen