Skip to main content
Log in

Abstract

The effects of public announcements, private communications, deceptive messages to groups, and so on, can all be captured by a general mechanism of updating multi-agent models with update action models, now in widespread use. There is a natural extension of the definition of a bisimulation to action models. Surely enough, updating with bisimilar action models gives the same result (modulo bisimulation). But the converse turns out to be false: update models may have the same update effects without being bisimilar. We propose action emulation as a notion of equivalence more appropriate for action models, and generalizing standard bisimulation. It is proved that action emulation provides a full characterization of update effect. We first concentrate on the general case, and next focus on the important case of action models with propositional preconditions. Our notion of action emulation yields a simplification procedure for action models, and it gives designers of multi-agent systems a useful tool for comparing different ways of representing a particular communicative action.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Baltag A. (2002) A logic for suspicious players: Epistemic action and belief-updates in games. Bulletin of Economic Research 54(1): 1–45

    Article  Google Scholar 

  • Baltag A., Moss L. (2004) Logics for epistemic programs. Synthese 139(2): 165–224

    Article  Google Scholar 

  • Baltag, A., Moss, L., & Solecki, S. (1998). The logic of public announcements, common knowledge, and private suspicions. In I. Bilboa (Ed.), Proceedings of TARK’98 (pp. 43–56).

  • Blackburn, P., de Rijke, M., & Venema, Y. (2001). Modal logic. Cambridge tracts in theoretical computer science. New York: Cambridge University Press.

  • Ditmarsch, H. V. (2001). Knowledge games. Ph.D. thesis, ILLC, Amsterdam.

  • Ditmarsch, H. V., & French, T. (2008). Simulation and information: Quantifying over epistemic events. In J.-J. C. Meyer, & J. Broersen (Eds.), KRAMAS. Lecture notes in computer science (Vol. 5605, pp. 51–65). New York: Springer.

  • Ditmarsch H.V., van der Hoek W., Kooi B. (2007) Dynamic epistemic logic. Synthese library (Vol. 337). Springer, New York

    Google Scholar 

  • Fagin R., Halpern J., Moses Y., Vardi M. (1995) Reasoning about knowledge. MIT Press, Cambridge, MA

    Google Scholar 

  • Fischer M., Ladner R. (1979) Propositional dynamic logic of regular programs. Journal of Computer and System Sciences 18(2): 194–211

    Article  Google Scholar 

  • Gerbrandy, J. (1999). Bisimulations on planet Kripke. Ph.D. thesis, ILLC, Amsterdam.

  • Kozen D., Parikh R. (1981) An elementary proof of the completeness of PDL. Theoretical Computer Science 14: 113–118

    Article  Google Scholar 

  • Lutz, C. (2006). Complexity and succinctness of public announcement logic. In: AAMAS ’06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems (pp. 137–143). ACM: New York.

  • Paige R., Tarjan R. E. (1987) Three partition refinement algorithms. SIAM Journal on Scientific Computing 16(6): 973–989

    Google Scholar 

  • Ruan, J. (2004). Exploring the update universe. Master’s thesis, ILLC, Amsterdam.

  • Sadzik, T. (March 2006). Exploring the iterated update universe. Tech. rep., PP-2006-26. Amsterdam: ILLC.

  • Segerberg K. (1982) A completeness theorem in the modal logic of programs. In: Traczyck T. (ed) Universal algebra and applications. Polish Science Publications, Warsaw, pp 36–46

    Google Scholar 

  • van Benthem J. (2001) Language, logic, and communication. In: Benthem J., Dekker P., Eijck J., Rijke M., Venema Y. (eds) Logic in action. ILLC, Amsterdam, pp 7–25

    Google Scholar 

  • van Benthem J. (2002) One is a lonely number: On the logic of communication. In: Chatzidakis Z., Koepke P., Pohlers W. (eds) Proceedings of logic colloquium ’02. Münster, Germany, pp 95–128

    Google Scholar 

  • van Benthem J., van Eijck J., Kooi B. (2006) Logics of communication and change. Information and Computation 204(11): 1620–1662

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Ji Ruan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

van Eijck, J., Ruan, J. & Sadzik, T. Action emulation. Synthese 185 (Suppl 1), 131–151 (2012). https://doi.org/10.1007/s11229-012-0083-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11229-012-0083-1

Keywords

Navigation