Überwindung der Nichthandbarkeit im Compilation Map

In der Informatik kennt man verschiedene Datenstrukturen zur Darstellung von Boole`schen Funktionen, und je nach Anwendung sind unterschiedliche Darstellungen von Vorteil. Der Forschungszweig der "Knowledge Compilation" beschäftigt sich mit der Übersetzung zwischen diesen Darstellungen. Das "Kompilieren" einer Funktion bezeichnet den (potentiell zeitaufwändigen) Aufbau einer solchen Datenstruktur, die ein schnelles Auswerten der Funktion ermöglicht. Eine Klasse von Anfragen ist "effizient" für eine Datenstruktur, wenn es einen Algorithmus gibt, der sie schnell (in polynomieller Zeit) beantworten kann, wenn ihm diese Datenstruktur zur Verfügung steht. Die sogenannte "Knowledge Compilation Map" bietet eine Übersicht über häufig verwendete Datenstrukturen und deren effiziente Anfragen. Wichtige Kriterien, anhand derer Darstellungen von Funktionen verglichen werden können, sind deren Speichereffizienz, sowie der Umfang der Anfragen, die sie effizient beantworten können. Jede Kombination aus Datenstruktur und Anfrage kann demnach als "effizient" oder "ineffizient" eingestuft werden. Für eine Reihe von Datenstrukturen sind praxistaugliche Compiler entwicklet worden. Ziel des vorliegenden Projekts sind Methoden zur Beantwortung von Anfragen, die für die entsprechenden Datenstrukturen eigentlich "ineffizient" sind. Wir wollen zeigen, dass das Kompilieren die einfachere Beantwortung solcher Anfragen ermöglicht, selbst wenn sie nicht im engeren Sinn "effizient" werden. Ein Forschungsschwerpunkt es Projekts ist die Entwicklung von "parametrisierten" Ansätzen. Das umfasst einerseits die Entwicklung von Prozeduren, die für Datenstrukturen effizient sind, solange Parameter, die sie charakterisieren, klein genug sind. Andererseits können auch selbst Anfragen durch Parameter charakterisiert werden, deren Einschränkung ihre effiziente Beantwortung ermöglicht. Demnach kann Parametrisierung zu Methoden führen, die die effiziente Beantwortung einer Teilklasse von Anfragen erlauben. Eine weitere Forschungsrichtung ist die approximierte Beantwortung von Anfragen. Wenn eine Anfrage nicht effizient beantwortet werden kann, ist es häufig dennoch möglich, eine Antwort zu geben, die nahe an der korrekten Antwort liegt. Bislang ist Approximation nur als Eigenschaft des Kompilierens untersuchen worden, mit dem Ziel, die Größe der erzeugten Datenstruktur auf Kosten kleiner Fehler zu reduzieren. Stattdessen wollen wir Verfahren entwickeln, die exaktes Kompilieren mit approximativer Beantwortung von Anfragen kombiniert.