Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Probevortrag - Promotion: Frederik Harwath

  • Wann 13.02.2017 von 10:30 bis 11:30
  • Wo 12489 Berlin, Rudower Chaussee 25, Humboldt-Kabinett
  • iCal

Herr Frederik Harwath (M.Sc. Inf.) wird einen Vortrag zum Thema

"On Invariant Formulae of First-Order Logic with Numerical Predicates"

halten. Mit diesem Vortrag möchte er Ihnen sein Promotionsthema vorstellen.

Alle Interesseneten sind herzlich eingeladen!


 

Abstract:

Der Vortrag beschäftigt sich mit Logiken auf endlichen Strukturen (z.B. Graphen, relationale Datenbanken, Bäume).
Logiken werden in der Informatik beispielsweise genutzt um Anfragen an Datenbanken zu formulieren.
Die Repräsentation einer Datenbank in einem Computer führt dabei notwendigerweise zu einer linearen Anordnung der Datenbank. Lässt man die Verwendung der Ordnung in logischen Formeln (als binäres Prädikat <) zu, kann dies die Ausdrucksstärke einer Logik erhöhen. Auch algorithmische Aspekte, z.B. die Länge der Formeln für eine Anfrage oder die Auswertungskomplexität von Formeln können hiervon beeinflusst werden.

Im Kontext relationaler Datenbanken wird üblicherweise verlangt, dass das Ergebnis einer Anfrage nicht von der Speicherung der Datenbank abhängt (Datenunabhängigkeitsprinzip). Um dies zu erreichen, wenn Anfragen durch logische Formeln ausgedrückt werden, die eine lineare Ordnung benutzen, verlangt man, dass der Wahrheitswert einer Formel in jeder gegebenen Datenbank unverändert bleiben soll, wenn sich die lineare Ordnung der Datenbank ändert. Formeln mit dieser Eigenschaft nennt man ordnungsinvariant.

Der Vortrag stellt das Konzept der Ordnungsinvarianz, seine Wurzeln in der Datenbanktheorie und seine Bezüge zur Komplexitätstheorie vor. Anschließend gebe ich einen Überblick über die Ergebnisse meiner Dissertation.
Diese beschäftigen sich mit Ordnungsinvarianz und verwandten Konzepten, bei denen Formeln Zugriff auf unterschiedliche arithmetische Prädikate (z.B. Addition) gewährt wird.
Die Ergebnisse betreffen die Prädikatenlogik erster Stufe und Erweiterungen dieser um unterschiedliche Quantoren (Mengenquantoren, Zählquantoren) auf unterschiedlichen Klassen von Strukturen.