Im Seminar sollen wesentliche Teile des Buchs von Ebbinghaus/Flum[1] durchgearbeitet werden:
Achtes und letztes Treffen :
Stephan Kepser erklärt die Darstellung zweitstufiger Quantoren durch den partielle-Fixpunkt-Operator.
Evtl. erzähle ich noch etwas über EXPTIME und PTIME-Sprachen, definiert durch erststufige Formeln mit kleinstem-Fixpunkt-Operator; insbesondere, wann und wie man (effiziente) Tabellenparser für Grammatiken aus der Fixpunktdefinition bekommt.
Sechstes Treffen :
Evtl. noch Kapitel 7.1 über inflationäre und kleinste Fixpunkte (sonst bleibt das für private Lektüre).
Fünftes Treffen
Das vierte Treffen findet schon nächste Woche statt,
Das dritte Treffen hatten wir auf
Das Treffen ist um eine Woche, auf Mi, 22.1.97, verschoben!
Das zweite Treffen ist am
Es wird Kapitel 2 des Buches außer Abschnitt 2.4 besprochen: Zweitstufige Logik, infinitäre Logiken, Pebble Games, Ungültigkeit von Sätzen der klassischen Modelltheorie in der Theorie endlicher Modelle.
Entschuldigung, daß das erste Treffen bis fast 20 Uhr gedauert hat.
Nach den Antworten zu den Terminvorschlägen scheint der Mittwochnachmittag der beste Termin zu sein. Der Seminarraum 0.41, in dem die Vorbesprechung stattfand, ist dann auch frei. Die erste inhaltliche Sitzung ist also :
Leider muß ein neuer Termin gefunden werden, da Holger Sturm mittwochs doch nicht ganztägig frei ist. Neue Terminvorschläge:
Die erste Sitzung soll wie geplant am 17.11. stattfinden, aber der Beginn müsste auf 14.00 Uhr verschoben werden.
Alle Interessenten sollten mir bitte eine E-Nachricht schicken oder anrufen (Tel. 2178-2718), welcher der Termine ihnen passen. Notfalls müssen wir zum wöchentlichen Termin, Do 15-17 Uhr, zurückkehren.
In der Sitzung am 7.11.96 wurde beschlossen, das Seminar in 5 Blöcken abzuhalten und 0-1-Gesetze sowie infinitäre Sprachen nicht auszuschließen. Die erste Blocksitzung findet am
Thema der ersten Blocksitzung sind der Satz von Ehrenfeucht-Fraïsse mit Anwendungen (Kurz, Kepser(?), Wilke(?)), die Sätze von Hanf (Sturm) und Gaifmann (Leiß) und ggf. Teile von Kapitel 2 (bis S.60) (Leiß)
Jeder Teilnehmer sollte Kapitel 1 (S.1-35) bis dann gelesen haben; wenn möglich noch etwas aus Kapitel 2.
|
7.11.96 |
Themenvergabe und Einführung |
|
14.11.96 |
Satz von Ehrenfeucht-Fraïsse |
|
21.11.96 |
Anwendungen von Ehrenfeucht-Fraïsse-Spielen |
|
28.11.96 |
Satz von Gaifman über lokale Formeln |
|
5.12.96 |
Ungültigkeit von Definierbarkeits- und Erhaltungssätzen |
|
12.12.96 |
Nichtaxiomatisierbarkeit der Allgemeingültigkeit im Endlichen |
|
19.12.96 |
Erfüllbarkeit in endlichen Strukturen |
|
7.1.97 |
Logische Beschreibung von Turingmaschinenrechnungen |
|
14.1.97 |
Erkennungskomplexität definierbarer Modellklassen |
|
21.1.97 |
Fixpunktlogiken für inflationäre und kleinste Fixpunkte |
|
28.1.97 |
Fixpunktlogik mit partiellem Fixpunktoperator |
|
4.2.97 |
Vergleiche der Fixpunktlogiken mit zweitstufiger Logik |
|
11.2.97 |
Logik mit einem Operator für die transitive Hülle binärer Relationen |
|
18.2.97 |
Definierbarkeit regulärer Sprachen in monadischer zweiter Stufe |
|
25.2.97 |
Definierbarkeit von PTIME- und EXPTIME-Sprachen mit beschränkten (monadischen) Fixpunktoperatoren |