Organisation

Die Veranstaltung wird als Blockseminar am Ende der Vorlesungszeit durchgeführt. Die Vorbesprechung findet am Donnerstag, den 9. Oktober um 11 Uhr in Raum 4116 (Seminarraum des Lehrstuhls) statt.

Deadlines

30.10.	Gliederung
24.11.	Ausarbeitung
18.12.	Endgültige Fassung
12.01.	Folien
Ende Januar	Vorträge

Schedule

Mittwoch, 28. Januar
8:30	–	9:15	Malte Kampschulte	Die Komplexität Henkin-definierbarer Relationen
9:15	–	10:00	Thomas Jache	Independence-Friendly-Logik
10:30	–	11:15	Ruth Cremer	Independence-Friendly-Modallogiken
11:15	–	12:00	Michel Surmacs	Independence-Friendly-Fixpunktlogik
12:15	–	13:00	Björn Marschollek	Einfürung in Dependence Logic
Freitag, 30. Januar
9:00	–	9:45	Christian Schilli	Modellexistenz-Spiel für Dependence Logic
9:45	–	10:30	Daniel Kneer	Ehrenfeucht-Fraïssé-Spiel für Dependence Logic
11:00	–	11:45	Patrick Kabasci	Definierbarkeit in Dependence Logic
11:45	–	12:30	Daniel Medina Cardona	Team Logic

Content

Oft lässt sich beobachten, dass Ereignisse oder gemessene Größen voneinander abhängen, in vielen Fällen ist allerdings der genaue Zusammenhang unbekannt. In diesem Seminar werden wir uns hauptsächlich mit der Frage beschäftigen, wie solche Abhängigkeiten in einer Logik formalisiert werden können und welche Schlussfolgerungen daraus gezogen werden können.

Betrachten wir eine Formel ∀x∃y φ(x,y), so ist diese erfüllt, wenn zu jedem Element x ein (von diesem funktional abhängiges) Element y existiert, so dass φ gilt. Es gibt allerdings in der Prädikatenlogik keine Möglichkeit auszudrücken, dass es ein weiteres solches Paar u und v gibt, so dass v nur von u abhängt, denn eine Formel wie ∀x∃y∀u∃v φ(x,y,u,v) beschreibt nur, dass ein passendes Element v abhängig von u und x gewählt werden kann, jedoch nicht, das die Wahl von v unabhängig von x sein soll.

Um solche Aussagen formalisieren zu können, wurden verschiedene Konzepte eingeführt wie z.B. die Independence-Friendly Logic oder die sogenannten Henkin-Quantoren, mit deren Hilfe sich genau solche partiellen und nicht-linearen Abhängigkeiten beschreiben lassen.

In der von Väänänen eingeführten Dependence Logic werden neue atomare Formeln eingeführt, mit denen explizit ausgedrückt werden kann, dass eine Variable von anderen abhängig ist, ohne eine Aussage darüber zu machen, welcher Natur diese Abhängigkeit ist. Im Gegensatz zur Independence-Friendly Logic, die gleich ausdrucksstark ist, ermöglicht die Verwendung atomarer Formeln jedoch die explizite Formulierung und das direkte Schlussfolgern über Abhängigkeitsbeziehungen.

In dem Seminar sollen die verschiedenen Ansätze und deren Ausdrucksmöglichkeiten vorgestellt und mit anderen Logiken verglichen werden. Weiterhin lässt sich das Konzept voneinander abhängiger Variablen in Formeln übertragen auf Spiele mit unvollständiger Information, in denen die Spieler z.B. nicht genau wissen, welchen Zug ihr Gegner zuvor gemacht hat, oder die Position im Spielgraphen nicht genau kennen, d.h. sie können ihren nächsten Zug nur abhängig von einer Teilmenge der gesamten Informationen n-Quantoren machen.

Als Literaturquellen für die Vortragsthemen dienen Kapitel aus dem Buch Dependence Logic von J. Väänänen (Cambridge University Press, 2007) sowie weitere Konferenz- und Zeitschriftenartikel klassischer und aktueller Forschungsergebnisse.

Topics

Thema	Vortragende(r)	Betreuer(in)	Literatur
Henkin-Quantoren	Peng Sun	B. Puchala	[Hen61, Wal70, End70]
Die Komplexität Henkin-definierbarer Relationen	Malte Kampschulte	R. Rabinovich	[BG86]
Independence-Friendly-Logik	Thomas Jache	M. Ummels	[HS97, Hin02]
Independence-Friendly-Modallogiken	Ruth Cremer	B. Puchala	[ST06, Bra00]
Independence-Friendly-Fixpunktlogik	Michel Surmacs	D. Fischer	[Bra04]
Die Komplexität von Independence-Friendly-Fixpunktlogik	Sevket Gökay	R. Rabinovich	[BK07]
Einfürung in Dependence Logic	Björn Marschollek	M. Ummels	[Vaa07, Kapitel 3-5]
Modellexistenz-Spiel für Dependence Logic	Christian Schilli	T. Ganzow	[Vaa07, Kapitel 6.5]
Ehrenfeucht-Fraïssé-Spiel für Dependence Logic	Daniel Kneer	T. Ganzow	[Vaa07, Kapitel 6.6]
Definierbarkeit in Dependence Logic	Patrick Kabasci	D. Fischer	[KV07]
Team Logic	Daniel Medina Cardona	Ł. Kaiser	[Vaa07, Kapitel 8]
Finite Information Logic	Chantal Höller	Ł. Kaiser	[PV05]

Literature

[BG86]	A. Blass and Y. Gurevich. Henkin quantifiers and complete problems. Annals of Pure and Applied Logic, vol. 32, pp. 1–16, 1986.
[BK07]	J. Bradfield and S. Kreutzer. The Complexity of Independence-Friendly Fixpoint Logic. In Foundations of the Formal Sciences V - Infinite Games (FotFS V), vol. 11 of Studies in Logic. College Publications, London, 2007.
[Bra00]	J. C. Bradfield. Independence: logics and concurrency. In CSL 2000, vol. 1862 of Lecture Notes in Computer Science, pp. 247–261. Springer, 2000.
[Bra04]	J. Bradfield. On independence-friendly fixpoint logics. Philosophia Scientiae, vol. 8, pp. 125–144, 2004.
[End70]	H. B. Enderton. Finite Partially-Ordered Quantifiers. Mathematical Logic Quarterly, vol. 16(8), pp. 393–397, 1970.
[HS97]	J. Hintikka and G. Sandu. Game-Theoretical Semantics. In Handbook of Logic and Language (J. F. van Benthem and A. G. ter. Meulen, Eds.), pp. 361–410. Elsevier, Amsterdam, 1997.
[Hen61]	L. Henkin. Some remarks on infinitely long formulas. In Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics, pp. 167–183. Pergamon Press and Państwowe Wydawnisctwo Naukowe (Polish scientific Publishers), 1961.
[Hin02]	J. Hintikka. Hyperclassical logic (a.k.a. IF logic) and its implications for logical theory. Bulletin of Symbolic Logic, vol. 8(3), pp. 404–423, 2002.
[KV07]	J. Kontinen and J. Väänänen. On Definability in Dependence Logic. ILLC Prepublications, 2007.
[PV05]	R. Parikh and J. Väänänen. Finite information logic. Annals of Pure and Applied Logic, vol. 134(1), pp. 83–93, 2005.
[ST06]	M. Sevenster and T. Tulenheimo. On modal logic, IF logic, and IF modal logic. Advances in Modal Logic, vol. 6, pp. 481–501, 2006.
[Vaa07]	J. Väänänen. Dependence Logic. Cambridge University Press, 2007.
[Wal70]	W. Walkoe. Finite Partially-Ordered Quantification. Journal of Symbolic Logic, vol. 35(4), pp. 535–555, 1970.

Classification

• Informatik (B.Sc.)/Seminar Informatik
• Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
• Informatik (D)/Hauptstudium/Theoretische Informatik
• Mathematik (D)/Hauptstudium/Reine Mathematik
• Informatik (S II)
• Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Prerequisites

• Vorlesung Mathematische Logik
• für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Contact

Erich Grädel, Diana Fischer, Tobias Ganzow, Łukasz Kaiser, Bernd Puchala, Roman Rabinovich, Michael Ummels