Speaker: Alexandru Baltag (ILLC, Amsterdam)
Date and Time: Thursday, April 11th 2024, 17:00-18:30 (note unusual time!)
Venue: F1.15 and online.
Title: Simple Recursion Laws for DEL and its extensions
Abstract. There are two standard approaches to axiomatizing full DEL (with common knowledge and arbitrary events): (a) directly axiomatizing the dynamic logic, using “Dynamic Induction” rules; and (b) extending the static base to Epistemic PDL (E-PDL) and reducing DEL to it using Recursion/Reduction axioms. Each of these options has its disadvantage: option (a) uses rather complex and non-standard rules, and the completeness proof is rather convoluted; while (b) uses a simple logic with a well-known axiomatization for the static logic, but the dynamic recursion/reduction axioms are extremely complex and opaque (-indeed, they take several pages of notations just to state). The same dilemma occurs again when DEL is extended to data-exchange events, in which agents access other agents’ full information database: in the case, the relevant static base is Group Epistemic PDL (GE-PDL, i.e. PDL built on top of distributed knowledge modalities for groups of agents), but the relevant recursion laws become even more impenetrable.
In this talk, I take a fresh look at the minimal static base needed for obtaining reductions for DEL and its mentioned extensions. By looking at recursion axioms as systems of equations, we are lead to extend the static language with polyadic conditionals, that are obtained as solutions to such systems of equations. Epistemically, these polyadic modalities capture various complex levels of conditional group knowledge, so they can be considered as generalizations of the common knowledge operator. As such, they can be given a transparent axiomatization and a filtration-based completeness proof, obtained by generalizing the corresponding axioms and proof for common knowledge. More importantly, the recursion/reduction laws become extremely simple and elegant. Even better, the same program can be applied to the extension of DEL with data-exchange events.
This talk is based on joint work: reference [1], joint with Johan van Benthem; and [2], joint with Sonja Smets; and it also relates to older joint work [3].
REFERENCES:
[1] A. Baltag & J. van Benthem: Updates, Generalized p-Morphisms, and (Co-)Recursive Equations. In J. van Benthem & F. Liu (eds), *Graph Games and Logic Design – Recent developments and further directions*, Springer 2024 to appear.
[2] A. Baltag & S. Smets: Logics for Data Exchange and Communication. Submitted to AiML 2024.
[3] A. Baltag and S. Smets: Learning what Others Know. In L. Kovacs and E. Albert (eds.), *LPAR23 proceedings of the International Conference on Logic for Programming AI and Reasoning*, EPiC Series in Computing, Volume 73, pp 90-110, 2020. https://doi.org/10.29007/plm4