Das FoPra beschäftigt sich mit einer eindeutigen Repräsentation
von rekursiven, höherstufigen Typen. Wir benutzen die in dem Paper
An incremental unique Representation for Regular Trees von
Laurent Mauborgne beschriebenen Algorithmen. Mauborgne beschäftigt
sich dort mit einer eindeutigen, inkrementellen Repräsentation für
reguläre Bäume, die es ermöglicht, zu einem rekursiven, höherstufigen Typ eine Repräsentation in O(n^2 * log n) zu berechnen.
Durch diese können Typen in konstanter Zeit auf Gleichheit getestet werden.
Zusätzlich zur Implementierung der Algorithmen haben wir den theoretischen Unterbau entwickelt und einige entscheidende Verbesserungen an den Algorithmen vorgenommen.
Momentan verfügbares Material:
Aufgabenstellung
Notizen von Prof. Smolka
Das Programm in einer Version vom 16.4.2002
und
die Quelldateien des Programms
Arbeitsversion unseres ersten Berichtes (Stand: 21. April 2002)
Aktuelle, völlig überarbeitete Version (Stand: 5.11.02),
auch als pdf-Datei.
Folien der Abschluss-Vorträge von Matthias und Sven.