Seminar Logic, Complexity, Games: Logic and (In)Dependence

WS 2008/09

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