Logik in der Informatik Prof. Dr. Nicole Schweikardt

Wir decken ein breites Spektrum von Themen aus dem Bereich Logik in der Informatik und angrenzenden Gebieten der Theoretischen Informatik, der mathematischen Logik und der Diskreten Mathematik ab. Unsere Schwerpunkte liegen hierbei in der endlichen Modelltheorie, der Datenbanktheorie und der Komplexitätstheorie. Besonderes Augenmerk richten wir auf die Verbindungen zwischen diesen Gebieten. Beispielsweise fungieren Logiken u.a. als Basis für Datenbankanfragesprachen und Spezifikationssprachen. Viele Aspekte komplexer Systeme lassen sich auf natürliche Weise durch logische Strukturen modellieren, so dass Eigenschaften komplexer Systeme durch logische Formeln beschrieben werden können.

Generelles Ziel unserer Arbeit ist, die Komplexität, die Problemen oder Systemen innewohnt, besser zu verstehen. Dabei interessieren uns die unterschiedlichsten Maße für Komplexität, darunter verschiedene Maße für die Berechnungskomplexität (Frage: Wie schwer ist es, das Problem algorithmisch zu lösen?) sowie für die Beschreibungskomplexität (Frage: Wie schwer ist es, das Problem in einem geeigneten Formalismus zu beschreiben?). Hierbei geht es uns u.a. darum, den Zusammenhang zwischen logischer Beschreibbarkeit und algorithmischer Lösbarkeit zu ergründen.

Ein Schwerpunkt der Arbeitsgruppe liegt in der Untersuchung der Ausdrucksstärke und Komplexität unterschiedlicher Logiken. Ein weiterer Schwerpunkt ist die Erforschung der Komplexität der Verarbeitung von großen Datenmengen und Datenströmen. Hierbei geht es uns insbesondere um die Entwicklung von Berechnungsmodellen, die den durch Speicherzugriffe verursachten Aufwand klassifizieren, um den Nachweis unterer Schranken, sowie um die Entwicklung effizienter Algorithmen zur Verarbeitung von großen Datenmengen und Datenströmen.

Publikationen

Nicole Schweikardt

Christoph Berkholz

Joachim Bremer

André Frochaux

Berit Grußien

Lucas Heimberg

Jens Keppeler

Louchka Popova-Zeugmann