August 7th–11th, 2023 at ESSLLI 2023 held at the University of Ljubljana.
Dynamic epistemic logics (DELs) allow one to reason about how knowledge of agents evolves as a result of various information-changing events. Some of the notable examples of DELs include public announcement logic, arrow update logic, and action model logic. Adding quantification over epistemic events in those DELs shifts the perspective from the effects of a particular event to the question of (non-)existence of an event leading to some epistemic outcome. For example, we may want to verify that there is a communication between Alice and Bob such that they both learn some secret, while eavesdropper Eve remains unaware of the secret. In the course, we will present some of the more well-known DELs with quantification and provide highlights of the proofs behind significant technical results. Moreover, we will also discuss some of the tantalising open question spanning the landscape of logics with quantification over information change.
The course is provided by Rustam Galimullin (Univeristy of Bergen) and Louwe B. Kuijer (University of Liverpool). If you have any questions regarding the course,
you are very welcome to ask us personally during the school or to contact us via email.
You can reach us at rustam.galimullin
Exercises are for the whole course and are meant as a purely optional supplement to facilitate discussions and understanding of the discussed formalisms. [Exercises]
About. In the first lecture, we will recall the basics of epistemic logic (EL), and will build upon it Public Announcement Logic (PAL) and Arrow Update Logic (AUL).
We will discuss semantics of PAL and AUL, reduction axioms for the logics, and the relative update expressivity of their dynamic operators.
Reading.
Hans van Ditmarsch, Wiebe van der Hoek, and Barteld Kooi (2008). Dynamic epistemic logic, volume 337 of Synthese Library. Springer. (Chapters 2 and 4)
Barteld Kooi and Bryan Renne (2011). Arrow update logic, Review of Symbolic Logic 4(4), pp. 536–559. [pdf]
Slides.
[Introduction to DEL]About. We will continue with the basics of DEL, and after that we introduce quantification over public announcements resulting in
Arbitrary Public Announcement Logic (APAL). We will focus on the most salient features of the logic and present one of the most tantalising
open problems in the area.
Reading.
Hans van Ditmarsch (2023). To be announced, Information and computation 292. [pdf] (Sections 1, 2, 3, and 6).
Philippe Balbiani, Alexandru Baltag, Hans van Ditmarsch, Andreas Herzig, Tomohiro Hoshi, and Tiago de Lima: (2008). 'Knowable' as 'known after an announcement', Review of Symbolic Logic 1(3), pp. 305–334. [pdf] (Warning: please note that the finitary axiomatisation presented in the paper is unsound; click [here] for the counterexample).
Hans van Ditmarsch, Wiebe van der Hoek, Barteld Kooi, and Louwe B. Kuijer (2017). Arbitrary arrow update logic, Artificial Intelligence 242, pp. 80–106. [pdf]
Slides.
[APAL]About. We will consider two more agent-centric versions of APAL, Group Announcement Logic (GAL) and Coalition Announcement Logic (CAL). The former allows
quantification over announcements by groups of agents, and the latter takes a more game-theoretic stance by quantifying not over announcements by a coalition but
also over the counter-announcements by the anti-coalition. We will consider logical properties of these formalisms and study why axiomatisation of CAL seems
hard to obtain.
Reading.
Hans van Ditmarsch (2023). To be announced, Information and computation 292. [pdf] (Section 4).
Thomas Ågotnes, Philippe Balbiani, Hans van Ditmarsch, and Pablo Seban (2010). Group announcement logic, Journal of Applied Logic 8(1), pp. 62–81.
Rustam Galimullin (2021). Coalition and Relativised Group Announcement Logic, Journal of Logic, Language and Information 30(3), pp. 451–489. Springer. [pdf]
Natasha Alechina, Hans van Ditmarsch, Tim French, and Rustam Galimullin (2022). Expressivity of Quantified Group Announcements, Journal of Logic and Computation. [pdf]
Slides.
[GAL] [CAL]About. We will start by comparing the relative expressivity of the big three of logics of quantified announcements – APAL, GAL, and CAL. After that
we will turn to the notion of group knowledge and the role it plays in quantification over public announcements. In particular, we will focus on APAL with common
knowledge by studying its expressivity and the existence of its finitary axiomatisation.
Reading.
Hans van Ditmarsch, Wiebe van der Hoek, and Barteld Kooi (2008). Dynamic epistemic logic, volume 337 of Synthese Library. Springer. (Chapter 2)
Hans van Ditmarsch and Barteld Kooi (2006). The Secret of My Success, Synthese 151(2), pp. 201–232. Springer. [pdf]
Natasha Alechina, Hans van Ditmarsch, Tim French, and Rustam Galimullin (2022). Expressivity of Quantified Group Announcements, Journal of Logic and Computation. [pdf]
Thomas Ågotnes and Rustam Galimullin (2023). Quantifying over information change with common knowledge, Autonomous Agents and Multi-Agent Systems 37(19), p. 40. Springer. [pdf]
Rustam Galimullin and Louwe B. Kuijer (2023). Satisfiability of APAL with Common Knowledge is Σ11-hard , Proceedings of the 19th TARK, pp. 260–271. [pdf]
Slides.
[GAL versus CAL] [Group Knowledge] [APAL with Common Knowledge]About. In the final day, we will consider two new DELs, Action Model Logic (AML) and Arrow Update Model Logic (AUML), and their quantified extensions.
Time permitting, we will discuss their synthesis problems and the overall expressivity considerations regarding the logics discussed in the course.
Reading.
Hans van Ditmarsch, Wiebe van der Hoek, and Barteld Kooi (2008). Dynamic epistemic logic, volume 337 of Synthese Library. Springer. (Chapter 6)
James Hales (2013). Arbitrary Action Model Logic and Action Model Synthesis, Proceedings of the 28th LICS, pp. 253–262. [pdf]
Hans van Ditmarsch, Wiebe van der Hoek, Barteld Kooi, and Louwe B. Kuijer. (2017). Arbitrary arrow update logic, Artificial Intelligence 242, pp. 80–106. [pdf]
Hans van Ditmarsch, Wiebe van der Hoek, Barteld Kooi, and Louwe B. Kuijer. (2020). Arrow update synthesis, Information and Computation 275. [pdf]
Slides.
[AAML and friends]