Wissenskompilierung ist ein wichtiger Ansatz zur Lösung rechnerisch schwieriger Probleme. Dieser Ansatz wurde in den frühen 1990er Jahren eingeführt und ist seither ein sehr aktives Forschungsgebiet. Wissenskompilierung spaltet den Lösungsprozess in zwei Phasen: in einer ersten Phase, der Kompilierungsphase, werden die Eingabedaten in eine neue Darstellung übergeführt, die dann in einer zweiten Phase dazu verwendet werden, um eine große Anzahl von einzelnen Abfragen effizient auszuführen. Im Idealfall soll die Kompilierungsphase nur eine polynomielle Vergrößerung der Eingabedaten bewirken. Die systematische Erforschung der Kompilierbarkeit wichtiger Probleme, zeigt, dass nur sehr wenige praxisrelevante Probleme eine solche Kompilierung mit polynomiellem Platzbedarf erlauben. Für viele wichtige Problem kann die klassischen Theorie der Wissenskompilierung daher keine guten obere Schranken für den Kompilierungsplatz geben.
Das Forschungsziel ist strukturelle Aspekte der Eingabedaten für die Wissenskompilierung auszunützen und damit den klassischen Ansatzes zur Wissenskompilierung zu erweitern und zu verfeinern. Um dieses Ziel zu erreichen, werden wir Methoden und Konzepte der parametrisierten Komplexität verwenden. Parametrisierten Komplexität ist eine wichtige Forschungsrichtung aus dem Gebiet der Algorithmen und Komplexitätstheorie, die den klassischen Begriff der Berechenbarkeit in Polynomialzeit erweitert, in dem sie verschiedene strukturelle Eigenschaften der Eingabedaten (wie Baumweite oder den Grad der Zyklizität) ausnutzt, und damit mächtige algorithmische Methoden zur Verfügung stellt. Für die Wissenskompilierung ermöglicht die parameterisierte Analyse neue positive Resultate in Form von oberen Schranken zu Kompilierungsplatz und Kompilierungszeit für Probleme, die im klassischen Sinne nicht kompilierbar sind.
Die geplante Forschungsarbeit wird geleitet durch die Analyse von konkreten Kompilierungsproblemen aus den Bereichen des abduktiven Schließens, des logischen Programmierens, der abstrakten Argumentation, und des aussagenlogischen Planens. Die Erkenntnisse und Resultate einzelnen Kompilierungsproblemen werden zu einem allgemeinen theoretischen Fundament zusammengefasst, mit dem allgemeine Methoden zur Erstellung von oberen und unteren Platz- und Zeitschranken für die Wissenskompilierung erstellt werden können. Ein weiteres Ziel ist es, empirisch zu untersuchen, wie einzelne Parameter in realistischen Problemeingaben verteilt sind.
