Logik in der Informatik Prof. Dr. Martin Grohe

Diplomarbeitsthemen können in allen Bereichen der theoretischen Informatik vergeben werden, beispielsweise in der Logik, Komplexitätstheorie, Algorithmik, Graphentheorie oder Datenbanktheorie. Einige Themenvorschläge werden unten beschrieben. Wenn Sie Interesse an einem dieser Themen, aber auch an Themen aus anderen Bereichen, hätten, oder wenn Sie selbst Themenvorschläge haben, dann können Sie sich jederzeit an Prof. Grohe oder einen Mitarbeiter des Lehrstuhls wenden.

Voraussetzung für die Vergabe eines Themas sind fundierte Kenntnisse in der theoretischen Informatik, die auch durch die erfolgreiche Teilnahme an Hauptstudiumsvorlesungen und Seminaren in der theoretischen Informatik belegt sein sollten. Manche der Themen erfordern speziellere Vorkenntnisse, auf die wir in einer Vorbesprechung eingehen.

Algorithmen für Paritätsspiele

Inhalt:

Paritätsspiele sind unendliche 2-Personenspiele auf endlichen Graphen, die eine zentrale Bedeutung in einem Grenzgebiet zwischen Logik und Automatentheorie und damit für theoretischen Grundlagen der automatischen Verifikation haben. Ein wichtige offenen Frage ist, ob es in Polynomialzeit entscheidbar ist, welcher der beiden Spieler in einem gegebenen Spiel eine Gewinnstrategie besitzt. Vöge und Jurdzinski haben einen Algorithmus vorgeschlagen, in dem iterativ eine Anfangsstrategie verbessert wird. Die Zahl der Iterationen bestimmt die Laufzeit. Bislang ist es offen, ob diese Zahl polynomiell ist. In dieser Arbeit soll untersucht werden, wie sich Vöge und Jurdzinskis Algorithmus auf speziellen Klassen von Spielgraphen wie etwa planaren Graphen verhält.

 

Ansprechpartner:

Martin Grohe

 

Themengebiete:

Logik, Algorithmik, Automatentheorie

 

Voraussetzungen:

Die regelmäßig angebotenen Vorlesung Logik, Spiele und Automaten wird als Voraussetzung empfohlen.

 

Literatur:

1. Hartmut Klauck. Algorithms for Parity Games. In: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001]. Lecture Notes in Computer Science 2500, Springer 2002: 107-129.
2. J. Vöge, M. Jurdzinski. A Discrete Strategy Improvement Algorithm for Solving Parity Games. In: E. Allen Emerson, A. Prasad Sistla (Eds.): Computer Aided Verification, 12th International Conference, CAV 2000. Lecture Notes in Computer Science 1855, Springer 2000: 202-215

Algorithmische Metasätze für Fixpunktlogiken

Inhalt:

Algorithmische Metasätze sind algorithmische Ergebnisse, die nicht nur einzelnen Probleme, sondern ganze Familien von Problemen betreffen. Typischerweise sind diese Familien durch eine logische und eine graphentheoretische Komponente definiert. In dieser Arbeit sollen algorithmische Metasätze für sogenannte Fixpunktlogiken untersucht werden.

 

Ansprechpartner:

Martin Grohe

 

Themengebiete:

Logik, Algorithmik, Komplexitätstheorie, Graphentheorie

 

Literatur:

1. M. Grohe. Logic, Graphs, and Algorithms, 2007.

Algorithmisches Lernen und logische Definierbarkeit

Inhalt:

Ziel des algorithmischen oder maschinellen Lernen ist die Entwicklung von Verfahren, mit denen unbekannte Konzepte etwa anhand von Beispielen möglichst genau erlernt werden können. Nicht alle Konzepte können gleichermaßen effizient erlernt werden, und es ist eine grundlegende Frage, welche Arten von Konzepten effizient lernbar sind. In dieser Arbeit soll, aufbauend auf den Ergebnissen von [1], die Lernbarkeit von logisch definierten Konzepten auf endlichen Graphen untersucht werden.

 

Ansprechpartner:

Martin Grohe

 

Themengebiete:

Logik, Algorithmische Lerntheorie, Graphentheorie

 

Literatur:

1. M. Grohe and G. Turan. Learnability and Definability in Trees and Similar Structures.Theory of Computing Systems 37(1):193-220, 2004.
2. M.J. Kearns and U.V.Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.

Simultanes Spielen

Inhalt:

Viele Situationen in der Komplexitätstheorie lassen sich am einfachsten durch kombinatorische Spiele beschreiben. Eine Frage, die in den letzten Jahren unter der Bezeichnung Parallel Repetition viel Aufmerksamkeit erfahren hat, ist, inwieweit in einem sehr simplen Spiel die Gewinnchancen des einen Spielers gesteigert werden können, wenn simultan mehrere Partien desselben Spiels gespielt werden. Diese Frage weist verblüffende Verbindungen nicht nur zu komplexitätstheoretischen Fragestellungen der Approximierbarkeit gewisser Optimierungsprobleme auf, sondern auch zu klassischen geometrischen Fragen, die die Struktur von Schäumen betreffen.

 

Ansprechpartner:

Martin Grohe

 

Themengebiete:

Komplexitätstheorie

 

Literatur:

1. T. Holenstein. Parallel Repetition: Simplifications and the No-Signaling Case. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp.411-419, 2007.
2. U. Feige, G. Kindler, and R. O'Donnell. Understanding Parallel Repetition Requires Understanding Foams. In Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, pp.179-192, 2007.

Nachfolgende Themenvorschläge sind überwiegend auf dem Gebiet der Theorie der Petrinetze. Die Implementierung der Resultate wird stets ein wichtiger Bestandteil der jeweiligen Arbeit sein.

Analyse von Intervall-Petrinetze

Inhalt:

Petrinetze sind ein geeignetes Mittel zu Modelliereung, Analyse und Simulation von Systemen unterschiedlichster Natur. Während für die klassischen Petrinetze eine große Varietät an Analysetechniken und ihrer Implementationen vorhanden ist, ist dies für die zeitabhängigen Petrinetze nicht der Fall. Für die Intervall-Petrinetze gibt es im wesentlichen zwei verschiedene algorithmische Analysevorgehen.

In dieser Arbeit sollen die Analysealgorithmen für Intervall-Petrinetze verglichen werden und eine der Methoden implementiert werden.

Ansprechpartner:

Louchka Popova-Zeugmann

Themengebiete:

Theorie der Petrinetze, Sofrwaeentwicklung

Endlichkeitkriterien für Zustandsraumcluster eines Intervall-Petrinetzes

Inhalt:

Der Zustandsraum eines Intervall-Petrinetzes wird durch einen (Erreichbarkeits-)Graphen ausreichend gut sowohl für eine qualitative als auch für eine quantitative Analyse beschrieben. Die Größe dieses Graphen ist exponential zu der Größe des Petrinetzes. Deshalb ist jede adäquate Reduktiion des Graphen interessant.

In dieser Arbeit sollen Endlichkeitsbedingungen für die Äquivallenz zweier Zustandsklassen betrachtet werden.

Ansprechpartner:

Louchka Popova-Zeugmann

Themengebiete:

Theorie der Petrinetze

Time Automata und Intervall-Petrinetze

Inhalt:

Time Automata sind auch sehr gut für die Modellierung und die Analyse zeitabhängiger Systeme geeiget. Einige Arbeiten beschäftigten sich bereits mit der Transformationen eines beliebigen Internall-Petrinetzes in ein Time Automaton. Der entstandene Time Automaton ist wesentlich größer. Und falls das Petrinetz das Modell eines Systems ist, verliert sich die natürliche Verbindung zwischen Modell (dann Time Automaton) und dem System.

In dieser Arbeit soll ein Vergleich von Analysetechniken beider Mittel durchgeführt werden sowie die Möglichkeit der Anpassung von Analysealgorithem aus der einen Theorie in die andere und umgekehrt betrachtet werden.

Ansprechpartner:

Louchka Popova-Zeugmann

Themengebiete:

Theorie der Petrinetze

Zeitabhängige Verhaltenseigenschaften und ihre Anwendung in biochemischen Netzwerken

Inhalt:

Metabolische Systeme, in denen viele nebenläufigen Prozesse stattfinden können, lassen sich auf natürlicher Art mit (zeitabhängigen) Petrinetzen modellieren. Damit sind die Fragen wie z.Bsp. nach dem Eintreten von einem Äquilibrium im Verhalten des Systems, Realisierbarkeit von Sequenzen etc. auf Fragen nach dem Verhalten des Petrinetzes zurückgeführt.

Der Zustandsraum eines zeitabhängigen Petrinetzes ist ein Teil des Zustandsraumes seines Skeletts. Somit können schaltbare Transitionssequenzen im Skelett zu nicht schaltbaren in dem IPN werden. Folglich ist das Verhalten des zeitabhängigen Petrinetzes mit diesem des Skeletts im Allgemein nicht vergleichbar.

In dieser Arbeit sollen zusätzliche strukturelle Bedingungen aufgestellt werden, die unerwünschte Eigenschaften eines zeitlosen Petrinetzes in dem zeitabhängigen Petrinetz beseitigen, wie z. Bsp.: Unter welchen Bedingungen ist ein zeitabhängiges Petrinetz beschränkt, obwohl sein Skelett unbeschränkt ist.

Ansprechpartner:

Louchka Popova-Zeugmann

Themengebiete:

Theorie der Petrinetze, Biochemische Netzwerke