Sum and Product in Dynamic Epistemic Logic

This is a joint work with H. P. VAN DITMARSCH and R. VERBRUGGE.

PDF Download: Sum and Product in Dynamic Epistemic Logic

Abstract:

The Sum-and-Product riddle was first published in the reference H. Freudenthal (1969, Nieuw Archief voor Wiskunde 3, 152) [6].We provide an overview on the history of the dissemination of this riddle through the academic and puzzle-math community. This includes some references to precursors of the riddle, that were previously (as far as we know) unknown.

We then model the Sum-and-Product riddle in a modal logic called public announcement logic. This logic contains operators for knowledge, but also operators for the informational consequences of public announcements. The logic is interpreted on multi-agent Kripke models. The information in the riddle can be represented in the traditional way by number pairs, so that Sum knows their sum and Product their product, but also as an interpreted system, so that Sum and Product at least know their local state. We show that the different representations are isomorphic. We also provide characteristic formulas of the initial epistemic state of the riddle. We analyse one of the announcements towards the solution of the riddle as a so-called unsuccessful update: a formula that becomes false because it is announced.

The riddle is then implemented and its solution verified in the epistemic model checker DEMO. This can be done, we think, surprisingly elegantly. The results are compared with other work in epistemic model checking and the complexity is experimentally investigated for several representations and parameter settings.

Keywords: Modal logic, puzzle math, dynamic epistemic logic, characteristic formula, model checking.

Published at Journal of Logic and Computation 2008 18(4):563-588; doi:10.1093/logcom/exm081

We gave a joint talk in the University of Groningen:

Related posts:

1. My Coming talk in Liverpool: Connecting Dynamic Epistemic and Temporal Epistemic Logics For Multi-Agent Systems Title: Connecting Dynamic Epistemic and Temporal Epistemic Logics For Multi-Agent...
2. Data-Aware Monitoring For Healthcare Workflows Using Formal Methods Authors: Ji Ruan and Wendy MacCaull Centre of Logic and...

Related posts brought to you by Yet Another Related Posts Plugin.