Logik in der Informatik
Prof. Dr. Martin Grohe

Mitarbeiterseminar Logik in der Informatik

Dieses Seminar wird von Mitgliedern des Lehrstuhls Logik in der Informatik als Forum der Diskussion und des Austauschs genutzt. Studierende und Gäste sind herzlich eingeladen. Das Seminar findet während des Sommersemesters 2004 Freitags von 11-13 Uhr in Raum 4.410 des Johann von Neumann Hauses (Rudower Chaussee 25) statt.

Folgende Termine und Vorträge sind bisher vorgesehen:

Fr, 23.04.04, 11-13 Uhr, Raum 4.410:

Thema: Die Nutzung von Schema-Informationen zur Optimierung von XQuery-Anfragen an XML-Dokumente (Teil 1)

Referentin: Nicole Schweikardt

Abstract: In diesem Vortrag stelle ich die Sprache FluX, eine Event-basierte Erweiterung der XML-Anfragesprache XQuery, vor und zeige, wie XQuery-Anfragen unter Einbeziehung von Schema-Informationen in FluX-Anfragen übersetzt werden können, die auch auf großen XML-Datenströmen effizient ausgewertet werden können.
[ Gemeinsame Forschungsarbeit mit Christoph Koch (TU Wien), Stefanie Scherzinger (Univ. Passau) und Bernhard Stegmaier (TU München). ]

Fr, 30.04.04, 11-13 Uhr, Raum 4.410:

Thema: Die Nutzung von Schema-Informationen zur Optimierung von XQuery-Anfragen an XML-Dokumente (Teil 2)

Referentin: Nicole Schweikardt

Abstract: siehe oben

Fr, 28.05.04, 11-13 Uhr, Raum 4.410:

Thema: Die Komplexität von k-SAT

Referent: Daniel Rolf

Abstract: Für k-SAT mit n Variablen, sei s_k = inf { c | es gibt einen 2^{cn} Algorithmus für k-SAT }. Die ETH (Exponential-Time Hypothesis) besagt, dass k-SAT nicht in subexponentialer Zeit in n lösbar ist, d.h. s_k > 0. Sei s_inf der Grenzwert von s_k für k gegen Unendlich, trivialerweise gilt s_inf <= 1. Es ist jedoch unbekannt, ob auch s_inf < 1 gilt. Es kann zumindest gezeigt werden, dass ein d > 0 existiert, so dass s_k <= (1-d/k)*s_inf, d.h. die Folge s_k steigt.
[ Die Ergebnisse stammen aus einer Arbeit von Impagliazzo und Paturi. ]

Fr, 11.06.04, 11-13 Uhr, Raum 4.410:

Thema: Das Sparsification Lemma von Impagliazzo, Paturi und Zane

Referent: Martin Grohe

Last modified: Wed Jun 2 16:29:23 CEST 2004
Nicole Schweikardt

Thema:	Die Nutzung von Schema-Informationen zur Optimierung von XQuery-Anfragen an XML-Dokumente (Teil 1)
Referentin:	Nicole Schweikardt
Abstract:	In diesem Vortrag stelle ich die Sprache FluX, eine Event-basierte Erweiterung der XML-Anfragesprache XQuery, vor und zeige, wie XQuery-Anfragen unter Einbeziehung von Schema-Informationen in FluX-Anfragen übersetzt werden können, die auch auf großen XML-Datenströmen effizient ausgewertet werden können. [ Gemeinsame Forschungsarbeit mit Christoph Koch (TU Wien), Stefanie Scherzinger (Univ. Passau) und Bernhard Stegmaier (TU München). ]

Thema:	Die Komplexität von k-SAT
Referent:	Daniel Rolf
Abstract:	Für k-SAT mit n Variablen, sei s_k = inf { c \| es gibt einen 2^{cn} Algorithmus für k-SAT }. Die ETH (Exponential-Time Hypothesis) besagt, dass k-SAT nicht in subexponentialer Zeit in n lösbar ist, d.h. s_k > 0. Sei s_inf der Grenzwert von s_k für k gegen Unendlich, trivialerweise gilt s_inf <= 1. Es ist jedoch unbekannt, ob auch s_inf < 1 gilt. Es kann zumindest gezeigt werden, dass ein d > 0 existiert, so dass s_k <= (1-d/k)*s_inf, d.h. die Folge s_k steigt. [ Die Ergebnisse stammen aus einer Arbeit von Impagliazzo und Paturi. ]

Thema:	Das Sparsification Lemma von Impagliazzo, Paturi und Zane
Referent:	Martin Grohe