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 Abstract Freely available
Right arrow Full Text (PDF)
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.
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

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



References

  1. Baltag A, Moss LS. Logics for epistemic programs. Synthese (2004) 139:165–224. Knowledge, Rationality & Action 1–60.[CrossRef][ISI]
  2. Baltag A, Moss LS, Solecki S. The logic of common knowledge, public announcements, and private suspicions. In: Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 98)—Gilboa I, ed. (1998) 43–56.
  3. Barwise J, Moss LS. Vicious Circles (1996) Stanford: CSLI Publications.
  4. Blackburn P, de Rijke M, Venema Y. Modal Logic (2001) Cambridge: Cambridge University Press. Cambridge Tracts in Theoretical Computer Science 53.
  5. Fagin R, Halpern JY, Moses Y, Vardi MY. Reasoning about Knowledge (1995) Cambridge MA: MIT Press.
  6. Freudenthal H. Formulation of the sum-and-product problem. Nieuw Archief voor Wiskunde (1969) 317:152.
  7. Freudenthal H. Solution of the sum-and-product problem. Nieuw Archief voor Wiskunde (1970) 318:102–106.
  8. Gammie P, van der Meyden R. MCK, Model checking the logic of knowledge. In: Proceedings of the 16th International Conference on Computer Aided Verification (CAV 2004)—Alur R, Peled D, eds. (2004) Springer. 479–483.
  9. Gamow G, Stern M. Puzzle-Math (1958) London: Macmillan.
  10. Gardner M. Mathematical games. Scientific American (1979) December :20–24;241. Also addressed in the March (p. 24) and May (pp. 20–21) issues of Volume 242, 1980.
  11. Gerbrandy JD. Bisimulations on Planet Kripke. In: PhD thesis (1999) University of Amsterdam. ILLC Dissertation Series DS-1999-01.
  12. Gerbrandy JD. The surprise examination in dynamic epistemic logic. Synthese (2007) 155(1):21–33.[CrossRef][ISI]
  13. Gerbrandy JD, Groeneveld W. Reasoning about information change. Journal of Logic, Language, and Information (1997) 6:147–169.[CrossRef]
  14. Greenblatt MH. Mathematical Entertainments: A Collection of Illuminating Puzzles New and Old (1968) London: George Allen and Unwin Ltd.
  15. Halpern JY, Vardi MY. Model checking vs. theorem proving: a manifesto. In: Artificial intelligence and mathematical theory of computation: papers in honor of John McCarthy—Lifschitz V, ed. (1991) San Diego, CA, USA: Academic Press Professional, Inc. 151–176.
  16. Hintikka J. Knowledge and Belief (1962) Ithaca, NY: Cornell University Press.
  17. Isaacs IM. The impossible problem revisited again. The Mathematical Intelligencer (1995) 17:4–6.
  18. Kooi BP. Expressivity and completeness for public update logics via reduction axioms. Journal of Applied Non-Classical Logics (2007) 17(2):231–253. To appear.[CrossRef]
  19. Lewis DK. Convention, a Philosophical Study (1969) Cambridge (MA): Harvard University Press.
  20. Lomuscio AR. Knowledge Sharing among Ideal Agents. In: PhD thesis (1999) University of Birmingham: Birmingham, UK.
  21. Lomuscio AR, Raimondi F. The complexity of model checking concurrent programs against CTLK specifications. Post-proceedings of DALT'06, the fourth workshop on Declarative Agent Languages and Technologies. To appear.
  22. McCarthy J. Formalization of two puzzles involving knowledge. In: Formalizing Common Sense: Papers by John McCarthy—Lifschitz Vladimir, ed. (1978–1981) Ablex Series in Artificial Intelligence. Ablex Publishing Corporation, Norwood, N. J. 1990. Original manuscript dated.
  23. Schilpp PA. A reply to my critics. In: The Philosophy of G.E. Moore (1942) Evanston IL: Northwestern University. 535–677. The Library of Living Philosophers (Volume 4).
  24. Nethercote N, Mycroft A. The cache behaviour of large lazy functional programs on stock hardware. SIGPLAN Notices (2003) 38(2,suppl):44–55.
  25. Panti G. Solution of a number theoretic problem involving knowledge. International Journal of Foundations of Computer Science (1991) 24:419–424.
  26. Parikh R. Finite and infinite dialogues. In: Workshop on Logic from Computer Science—Moschovakis E, ed. (1992) MSRI Publications/Springer. 481–498.
  27. Plaza JA. Logics of public communications. In: Proceedings of the 4th International Symposium on Methodologies for Intelligent Systems—Emrich ML, Pfeifer MS, Hadzikadic M, Ras ZW, eds. (1989) 201–216.
  28. Raimondi F, Lomuscio AR. Verification of multiagent systems via ordered binary decision diagrams: an algorithm and its implementation. In: Proceedings of the Third International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 04) (2004) IEEE Computer Society. 630–637.
  29. Sallows L. The impossible problem. The Mathematical Intelligencer (1995) 17(1):27–33.
  30. Schiffer S. Meaning (1972) Oxford: Oxford University Press.
  31. Su K. Model checking temporal logics of knowledge in distributed systems. In: Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI 04)—Deborah LM, Ferguson G, eds. (2004) AAAI Press/The MIT Press. 98–103.
  32. van Benthem JFAK. Dynamic odds and ends. In: Technical report (1998) University of Amsterdam. ILLC Research Report ML-1998-08.
  33. van Benthem JFAK. One is a lonely number: on the logic of communication. In: Technical report (2002) University of Amsterdam. ILLC Research Report PP-2002-27 (material presented at the Logic Colloquium 2002).
  34. van der Hoek W, Lomuscio AR, Wooldridge MJ. On the complexity of practical ATL model checking. In: Proceedings of the Fifth International Joint Conference on Autonomous Agents & Multiagent Systems (AAMAS 2006) (2006) 201–208. ACM.
  35. Petrosjan LA, Mazalov VV. Epistemic logic: a survey. Game theory and Applications (2002) Vol. 8:53–94.
  36. van der Hoek W, Wooldridge M. Model checking knowledge and time. In: Model Checking Software, Proceedings of SPIN 2002 (LNCS Volume 2318)—Bosnacki D, Leue S, eds. (2002) Springer. 95–111.
  37. van der Hoek W, Wooldridge MJ. Tractable multiagent planning for epistemic goals. In: Proceedings of the First International Joint Conference on Autonomous Agents & Multiagent Systems (AAMAS 2002) (2002) 1167–1174. ACM.
  38. Doyle Jon, Sandewall Erik, Torasso Pietro. Mutual belief revision. In: Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning (KR) (1994) Morgan Kaufmann. 595–606.
  39. van Ditmarsch HP, Kooi BP. The secret of my success. Synthese (2006) 151:201–232.[CrossRef][ISI]
  40. van Ditmarsch HP, Ruan J, Verbrugge R. Model checking sum and product. In: Proceedings of the 18th Australian Joint Conference on Artificial Intelligence (AI 2005) (2005) Springer Verlag. 790–795. LNAI 3809.
  41. van Ditmarsch HP, van der Hoek W, Kooi BP. Descriptions of game states. In: Logic, Games, and Constructive Sets—Mints G, Muskens R, eds. 43–58. CSLI Stanford, 2003.CSLI Publications. Lecture Notes No. 161.
  42. van Ditmarsch HP, van der Hoek W, Kooi BP. Dynamic Epistemic Logic. In: Synthese Library Series Vol.337 (2007) Berlin: Springer.
  43. van Eijck J. Dynamic epistemic modelling. In: Technical report (2004) Amsterdam: Centrum voor Wiskunde en Informatica. CWI Report SEN-E0424.
  44. van Tilburg G. Doe wel en zie niet om (do well and don't look back). Katholieke Illustratie (Catholic Illustrated Journal) (1956) 90(32):47. Breinbrouwsel 137 (‘Brain Cracker’ 137).
  45. Williams WT, Savage GH. The Penguin Problems Book: A Modern Anthology of Perplexities and Tantalizers (1940) Harmondsworth: Penguin Books (Allen Lane).
  46. Williams WT, Savage GH. The Second Penguin Problems Book (1944) Harmondsworth: Penguin Books.
  47. Yap A. Product update and looking backward. In: Technical report (2006) University of Amsterdam. ILLC Research Report PP-2006-39.

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



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
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.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?