General Dynamic Dynamic Logic

Abstract

Dynamic epistemic logic (DEL) extends purely modal epistemic logic (S5) by adding dynamic operators that change the model structure. Propositional dynamic logic (PDL) extends basic modal logic with programs that allow the definition of complex modalities. We provide a common generalisation: a logic that is `dynamic' in both senses, and one that is not limited to S5 as its modal base. It also incorporates, and significantly generalises, all the features of existing extensions of DEL such as BMS [3] and LCC [21]. Our dynamic operators work in two steps. First, they provide a multiplicity of transformations of the original model, one for each `action' in a purely syntactic `action structure' (in the style of BMS). Second, they specify how to combine these multiple copies to produce a new model. In each step, we use the generality of PDL to specify the transformations. The main technical contribution of the paper is to provide an axiomatisation of this `general dynamic dynamic logic' (GDDL). This is done by providing a computable translation of GDDL formulas to equivalent PDL formulas, thus reducing the logic to PDL, which is decidable. The proof involves switching between representing programs as terms and as automata. We also show that both BMS and LCC are special cases of GDDL, and that there are interesting applications that require the additional generality of GDDL, namely the modelling of private belief update. More recent extensions and variations of BMS and LCC are also discussed.