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.
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
Baltag A., Moss L. (2004) Logics for epistemic programs. Synthese 139(2): 165–224
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
Fagin R., Halpern J., Moses Y., Vardi M. (1995) Reasoning about knowledge. MIT Press, Cambridge, MA
Fischer M., Ladner R. (1979) Propositional dynamic logic of regular programs. Journal of Computer and System Sciences 18(2): 194–211
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
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
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
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
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
van Benthem J., van Eijck J., Kooi B. (2006) Logics of communication and change. Information and Computation 204(11): 1620–1662
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11229-012-0083-1