Repräsentation ist ein fundamentaler Konzept in der Informatik. Allerdings gibt es oft mehrere mögliche Repräsentationen für ein bestimmtes Objekt. Dies führt zu der Frage: Wie wählen wir zwischen verschiedenen Repräsentationsformaten? Die Antwort auf diese Frage besteht in der Regel aus zwei wesentlichen Komponenten. Einerseits möchten wir, dass unsere Repräsentation alle Informationen über unser ursprüngliches Objekt in einer Weise enthält, die algorithmisch leicht zu verwenden ist. Andererseits möchten wir, dass sie so kompakt wie möglich ist. Das Spannungsfeld zwischen diesen beiden Aspekten – nämlich Kompaktheit und algorithmische Leistungsfähigkeit – ist das Thema dieser Arbeit. Zunächst untersuchen wir die Darstellung von Mengen von Homomorphismen zwischen relationalen Strukturen durch Schaltungen mit Vereinigungs- und Kartesischen Produktgattern. Wir charakterisieren, welche Mengen von Homomorphismen durch diese Schaltungen prägnant dargestellt werden können. Diese Ergebnisse stehen in direktem Zusammenhang mit der Bearbeitbarkeit von Join-Abfragen in der Datenbanktheorie. Zweitens untersuchen wir Darstellungen von Aussagenformeln durch strukturierte d-DNNF-Schaltungen, eine prominente Schaltungsklasse in der Wissenskompilierung. Wir zeigen, dass solche Schaltungen keine polynominalen Negations-, Disjunktions- oder Existenzquantifizierungsoperationen unterstützen. Drittens stellen wir eine optimale doppelt exponentielle Trennung zwischen kontextfreien Grammatiken und ihrer eindeutigen Variante her und bestätigen damit eine Vermutung von Kimelfeld, Martens und Niewerth. Viertens beweisen wir im Rahmen der Logik mit endlichen Variablen exponentielle Untergrenzen für die Formelgröße im k-Variablen-Fragment der FO, die zur Trennung zweier Strukturen mit n Elementen erforderlich sind. Damit zeigen wir eine exponentielle Prägnanzlücke zwischen den k- und (k+1)-Variablen-Fragmenten von FO.
Harry Vinall-Smeeth (Mon,) studied this question.