Skip Navigation



Journal of Logic and Computation Advance Access published online on December 21, 2007
Journal of Logic and Computation, doi:10.1093/logcom/exm081
This Article
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
18/4/563    most recent
exm081v1
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by van Ditmarsch, H. P.
Right arrow Articles by Verbrugge, R.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2007. Published by Oxford University Press on behalf of the Association of Physicians. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original papers

Sum and Product in Dynamic Epistemic Logic

H. P. van Ditmarsch

Department of Computer Science, University of Otago, New Zealand.E-mail: hans{at}cs.otago.ac.nz

J. Ruan

Department of Computer Science, University of Liverpool, UK.E-mail: jruan{at}csc.liv.ac.uk

R. Verbrugge

Department of Artificial Intelligence, University of Groningen, The Netherlands.E-mail: rinke{at}ai.rug.nl


  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


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.