[Back]

M. Jakl:
"Efficient Algorithms through Bounded Treewidth";
Supervisor: R. Pichler; Institut für Informationssysteme, Arbeitsbereich Datenbanken & Artificial Intelligence, 2007.

Parametrized complexity has gained much interest in the last decade, especially the result of Bruno Courcelle, which states that the evaluation problem of monadic second order formulae is tractable (with restrictions). Interestingly enough, nearly nothing has been published describing the implementation of this result. We implement such a system, and describe the problems we ran into. After explaining exactly how the components of the system work and giving some real implementation details, we point out the problems and pitfalls of the approach. A lot of work has to be done in this direction until the enormous promising and valuable theoretical result becomes practically tractable.

Parameterisierte Komplexitätsanalyse weckte im letzten Jahrzent reges Interesse, besonders jedoch das Ergebnis von Bruno Courcelle das besagt, dass das Entscheidungsproblem von Monadic Second Order Formeln theoretisch "schaffbar" ist (mit Einschränkungen). Trotz der enormen Wichtigkeit des Theorems wurde nur wenig über erfolgreiche, oder fehlgeschlagene Implementierungen veröffentlicht. Wir implementieren dieses System und geben eine exakte Beschreibung der Komponenten des Systems und erläutern die Probleme, die bei der Umsetzung aufgetreten sind. Um eine praktisch sinnvolle Umsetzung zu ermöglichen, muss noch einiges an theoretischer Vorarbeit geleistet werden.

logic, fixed parameter algorithms, parameterized complexity