Seminar Logik und dynamisches Wissen

SS 2006

Organisation

Die Veranstaltung wird als Blockseminar angeboten, die Vorträge finden am 28. Juni und 12. Juli 2006 im Seminarraum Informatik 7 statt. Die Nachmittags-Vorträge am 12. Juli 2006 finden im Seminarraum Informatik 4 statt.

Zeitplan

18.04. Konzept
2.05. Gliederung
22.05. Ausarbeitung
12.06. Endgültige Fassung
19.06. Folien
28.06./12.07. Vorträge

Programm

Mittwoch, 28. Juni
9:30 10:15 Richard Gay Modallogiken, Epistemische Logiken, Entscheidbarkeit und Komplexität
10:15 11:00 Jens Otten Common Knowledge, Mu-Kalkül, Fixpunktsemantik
11:15 12:00 Robert Hochstrat Common Knowledge and Agreement
12:00 13:30 Mittagspause
13:30 14:15 Andreas Guta (Common) Knowledge bei unendlich vielen Agenten
14:15 15:00 Christian Brockly Public Announcement, Epistemic Actions, and Private Suspicions
15:15 16:00 Sergej Fries Wiederholtes Public Announcement
Mittwoch, 12. Juli
9:30 10:15 Nicolas Ehses Epistemische Bedingungen für die Existenz von Nash-Gleichgewichten
10:15 11:00 Jan Manuel Theegarten Common Reasoning about Admissibility
11:15 12:00 Tobias Hermes Logics of Belief and Belief Revision
12:00 14:00 Mittagspause
14:00 14:45 Tobias Vaegs Formalisierung von Belief Change Szenarien
14:45 15:30 Lukas Berthold Wissensbasierte Semantik von Nachrichten und Kommunikation
15:45 16:30 Martin Zimmermann Synthese verteilter Systeme aus wissensbasierten Spezifikationen

Themen

Thema Vortragende(r) Betreuer(in) Literatur
Modallogiken, Epistemische Logiken, Entscheidbarkeit und Komplexität Richard Gay L. Kaiser [FHMV95, Kap. 2,3]
Common Knowledge, Mu-Kalkül, Fixpunktsemantik Jens Otten T. Ganzow [FHMV95, Kap. 3,6, Gea92, HM00]
Common Knowledge and Agreement Robert Hochstrat T. Ganzow [FHMV95, Kap. 6, HMW90]
(Common) Knowledge bei unendlich vielen Agenten Andreas Guta L. Kaiser [Hal99]
Public Announcement, Epistemic Actions, and Private Suspicions Christian Brockly V. Bárány [BMS99]
Transformation von DEL in PDL Zhonghua Long V. Bárány [vE04]
Wiederholtes Public Announcement Sergej Fries V. Bárány [MM05]
Epistemische Bedingungen für die Existenz von Nash-Gleichgewichten Nicolas Ehses L. Kaiser [AB95, Aum95]
Common Reasoning about Admissibility Jan Manuel Theegarten L. Kaiser [BS96]
Rational Dynamics and Epistemic Logic in Games Joachim Kerkmann L. Kaiser [vB03]
Logics of Belief and Belief Revision Tobias Hermes T. Ganzow [AGM85, FH94a, FH94b]
Formalisierung von Belief Change Szenarien Tobias Vaegs T. Ganzow [DSTW01]
Wissensbasierte Semantik von Nachrichten und Kommunikation Lukas Berthold V. Bárány [PP04, PR03]
Synthese verteilter Systeme aus wissensbasierten Spezifikationen Martin Zimmermann V. Bárány [vdMW05]

Inhalt

Es werden verschiedene Logiken und Modelle betrachtet, mit denen das Wissen von (einem oder mehreren) Agenten in einem Systemen beschrieben werden kann. Dazu gehören zum Beispiel epistemische Logiken, in denen sich Aussagen darüber machen lassen, was die Agenten wissen, was sie für möglich halten, was sie darüber wissen, was die anderen wissen usw.

Durch Kommunikation zwischen den Agenten ergeben sich weitere interessante Fragestellungen: Was kann zum Beispiel daraus gefolgert werden, dass A auf der Straße von B nach dem Weg zur Universität gefragt wird? A kann daraus folgern, dass B den Weg nicht weiß, dass B es aber für möglich hält, dass A den Weg weiß. Nachdem A B den Weg erklärt hat, weiß erstens B den Weg, und zweitens weiß A, dass B den weg jetzt auch weiß; B weiß, dass A weiß, dass B den Weg weiß, ....

Ein weiteres interessantes Beispiel ist folgendes Rätsel:

Drei Kinder kommen vom Spielen nach Hause und zwei von ihnen haben Dreck auf ihrer Stirn (den sie natürlich nicht selbst sehen können). Der Vater sagt: "Mindestens einer von euch hat Dreck auf der Stirn", und fragt direkt: "wer von euch weiß, ob er schmutzig oder sauber ist?" Da keines der Kinder jemals lügen würde, antwortet keines von ihnen. Der Vater fragt erneut: "Wer von euch weiß jetzt, ob er schmutzig oder sauber ist?" Daraufhin gehen die beiden Kinder mit Dreck auf der Stirn ins Bad, um sich zu waschen.
Warum wussten die beiden Kinder nach der zweiten Frage des Vaters, dass sie schmutzig waren? Offenbar ist ihr Wissen durch die Kommunikation mit ihrem Vater gewachsen.

Um diese Phänomene beschreiben zu können, betrachten wir verschiedene Anätze wie man z.B. epistemische Logiken derart erweitern kann, dass es möglich wird, Änderungen des Wissens der Agenten, die z.B. durch Kommunikation der Agenten untereinander hervorgerufen wird, zu formalisieren und zu analysieren.

Insbesondere sollen auch die sich ergebenden algorithmischen Fragestellungen (z.B. Entscheidbarkeit bzw. Komplexität des entsprechenden Erfüllbarkeitsproblems) sowie die Verbindungen zu Fixpunktlogiken untersucht werden.

Literatur

Zuordnung

  • Informatik (D)/Hauptstudium/Theoretische Informatik
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/D: Angewandte Mathematik

Voraussetzungen

  • Vorlesung Mathematische Logik, insbesondere Kenntnisse von Modallogik.

Rückfragen

Erich Grädel, Vince Bárány, Tobias Ganzow, Łukasz Kaiser