Algorithmische Modelltheorie

Zusammenfassung

In der endlichen Modelltheorie wird die Beziehung zwischen logischer Definierbarkeit und algorithmischer Komplexität auf endlichen Strukturen untersucht. Ein besonders wichtiger Aspekt ist hierbei die logische Beschreibung von Komplexitätsklassen. In unsere Arbeitsgruppe wurden einige signifikante Beiträge zu diesem Feld erarbeitet.

Eine neuere Entwicklung in diesem Feld ist der Erweiterung des Ansatzes und der Methodologie der endlichen Modelltheorie auf (bestimmte Klassen von) unendliche Strukturen. Algorithmische Fragestellungen auf unendlichen Strukturen sind in verschiedenen Bereichen der Informatik von wachsender Bedeutung. Das traditionell auf endlichen relationalen Strukturen beruhende Datenbankmodell hat sich für einige moderne Anwendungen (wie etwa geographische Daten, Constraint Databases, Daten im Netz) als unzureichend erwiesen. Auch in der Verifikation sind unendliche (aber endlich präsentierbare) Transitionssysteme von wachsender Bedeutung. Dies gilt insbesondere für Anwendungen in der Verifikation von Software.

Wir untersuchen verschiedene Ansätze die Methoden der endlichen Modelltheorie auch für unendliche Strukturen zugänglich zu machen. Fragen nach dem Zusammenhang zwischen logischer Definierbarkeit und algorithmischen Problemstellungen sind auch hier wieder von besonderer Bedeutung.

Wir haben eine Modelltheorie der metafiniten Strukturen entwickelt, welche endliche Strukturen mit arithmetischen Operationen auf einem unendlichen numerischen Definitionsbereich verbindet. Anwendungen metafiniter Modelltheorie wurden in den folgenden Bereichen untersucht: deskriptive Komplexität über reellen Zahlen, Approximationseigenschaften von Optimierungs- und Zählproblemen, Datenbanken mit unsicherer oder unzuverlässiger Information und Datenbankabfragesprachen mit Aggregaten.

Wir untersuchen algorithmische und Definierbarkeitsfragen auf verschiedenen Klassen unendlicher Strukturen, welche durch Automaten und Interpretationen darstellbar sind. Die Arbeiten von A. Blumensath, V. Bárány, und E. Grädel hatten einen großen Einfluss auf die Entwicklung dieses Gebietes.

Personen

  • Personen, die in der endlichen oder algorithmischen Modelltheorie arbeiten
  • Treten sie der FMT Mailingliste bei; Abonnieren bei der FMT mailman Seite

Offene Probleme

  • Wir pflegen eine Sammlung von Offenen Problemen in der endlichen Modelltheorie. (letztes Update 21. August 2003.)
  • Neue Probleme (höchstens eine halbe Seite) und Ankündigungen von Lösungen (höchstens eine Seite) sollten an Erich Grädel oder Richard Wilke, vorzugsweise in LaTeX, geschickt werden.

Workshops

Almoth

Finite and Algorithmic Model Theory

Workshop on Logic, Language, Information and Computation

Rückfragen

Erich Grädel, Richard Wilke