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 | ||||
|
|
– |
|
|
|
|
|
– |
|
|
|
|
|
– |
|
|
|
|
|
– |
|
|
|
|
|
– |
|
|
|
|
|
– |
|
|
|
|
|
– |
|
|
|
| Mittwoch, 12. Juli | ||||
|
|
– |
|
|
|
|
|
– |
|
|
|
|
|
– |
|
|
|
|
|
– |
|
|
|
|
|
– |
|
|
|
|
|
– |
|
|
|
|
|
– |
|
|
|
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
| [AB95] | R. J. Aumann and A. Brandenburger. Epistemic Conditions for Nash Equilibrium. Econometrica, vol. 63(5), pp. 1161–1180, 1995. |
| [AGM85] | C. Alchourron, P. Gärdenfors, and D. Makinson. On the Logic of Theory Change: Partial Meet Contraction and Revision Functions. Journal of Symbolic Logic, vol. 50, pp. 510–530, 1985. |
| [Aum95] | R. J. Aumann. Backward Induction and Common Knowledge of Rationality. Games and Economic Behavior, vol. 8, pp. 6–19, 1995. |
| [BMS99] | A. Baltag, L. S. Moss, and S. Solecki. The logic of public announcements, common knowledge, and private suspicions. Technical Report. CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1999. |
| [BS96] | C. Bicchieri and O. Schulte. Common reasoning about admissibility. Erkenntnis, vol. 45(2–3), pp. 299–325, 1996. |
| [DSTW01] | J. Delgrande, T. Schaub, H. Tompits, and S. Woltran. On Computing Solutions to Belief Change Scenarios. In Sixth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (S. Benferhat and P. Besnard, Eds.), Lecture Notes in Artificial Intelligence, pp. 510-521. Springer-Verlag, 2001. |
| [FH94a] | N. Friedman and J. Y. Halpern. A Knowledge-Based Framework for Belief change, Part I: Foundations. In TARK, pp. 44-64, 1994. |
| [FH94b] | N. Friedman and J. Y. Halpern. A Knowledge-Based Framework for Belief Change, Part II: Revision and Update. In KR'94: Principles of Knowledge Representation and Reasoning (J. Doyle, E. Sandewall, and P. Torasso, Eds.), pp. 190–201. Morgan Kaufmann, San Francisco, California, 1994. |
| [FHMV95] | R. Fagin, J. Y. Halpern, M. Y. Vardi, and Y. Moses. Reasoning about knowledge. MIT Press, Cambridge, MA, USA, 1995. |
| [Gea92] | J. Geanakoplos. Common Knowledge. In TARK, pp. 254-315, 1992. |
| [HM00] | J. Y. Halpern and Y. Moses. Knowledge and common knowledge in a distributed environment. CoRR, vol. cs.DC/0006009, 2000. |
| [HMW90] | J. Halpern, Y. Moses, and O. Waarts. A Characterization of Eventual Byzantine Agreement. In Proceedings of the 9th Annual ACM Symposium on Principles of Distribted Computing (C. Dwork, Ed.), pp. 333–346, Québec City, Québec, Canada. ACM Press, 1990. |
| [Hal99] | J. Y. Halpern and R. A. Shore. Reasoning about Common Knowledge with Infinitely Many Agents. In Logic in Computer Science, pp. 384-393, 1999. |
| [MM05] | J. S. Miller and L. S. Moss. The Undecidability of Iterated Modal Relativization. Studia Logica, vol. 79(3), pp. 373-407, 2005. |
| [PP04] | E. Pacuit and R. Parikh. The Logic of Communication Graphs. In DALT, pp. 256-269, 2004. |
| [PR03] | R. Parikh and R. Ramanujam. A Knowledge Based Semantics of Messages. J. of Logic, Lang. and Inf., vol. 12(4), pp. 453–467, 2003. |
| [vB03] | J. van Benthem. Rational Dynamics and Epistemic Logic in Games. Technical Report. Institute for Logic, Language and Computation, 2003. |
| [vE04] | J. van Eijck. Reducing dynamic epistemic logic to PDL by program transformation. Technical Report. CWI, Amsterdam, 2004. |
| [vdMW05] | R. van der Meyden and T. Wilke. Synthesis of Distributed Systems from Knowledge-Based Specifications. In CONCUR, pp. 562-576, 2005. |
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