Logik in der Informatik Prof. Dr. Martin Grohe

Logik spielt in der Informatik eine grundlegende Rolle, vergleichbar mit der Rolle der Analysis in der Physik und den traditionellen Ingenieursdisziplinen. Anwendungen der Logik findet man in so unterschiedlichen Bereichen der Informatik wie Rechnerarchitektur, Softwaretechnik, Programmiersprachen, Datenbanken, künstliche Intelligenz, Komplexitäts- und Berechenbarkeitstheorie.

Im Zentrum der Lehre und Forschung am Lehrstuhl für Logik in der Informatik steht das Grenzgebiet zwischen Logik, Algorithmik und Komplexitätstheorie. Wichtige algorithmische Probleme aus Anwendungen wie Datenbanksystemen oder künstlicher Intelligenz lassen sich auf natürliche Weise durch "logische" Probleme modellieren. Effiziente Algorithmen für die Probleme und ihre Komplexität lassen sich oft am besten anhand dieser abstrakten logischen Modelle untersuchen. Ebenso lassen sich grundlegende Fragen der Komplexitätstheorie oft mittels logischer Methoden untersuchen. Ein nützliches Paradigma besagt, dass die algorithmische Komplexität eines Problems sehr eng mit der sprachlich-logischen Komplexität zusammenhängt – sprich: Probleme, die schwer lösbar sind, sind auch schwer beschreibbar und umgekehrt.

Projekte

• Die Struktur parametrischer Komplexitätsklassen
• Die Komplexität von Constraint-Satisfaction Problemen
• Baumartige Zerlegungen von Graphen und Strukturen und ihre Anwendungen
• Graduiertenkolleg Methoden für Diskrete Strukturen
• Endliche Modelltheorie (im Rahmen des EU Netwerkes MODNET )

Publikationen

Martin Grohe

Yijia Chen

Stephan Kreutzer

Louchka Popova-Zeugmann

Daniel Rolf

Nicole Schweikardt