Abstract
Coalition Logic (CL) is one of the most influential logical formalisms for strategic abilities of multi-agent systems. However CL can not formalize the evolvement of rational mental attitudes of the agents such as knowledge. In this paper, we introduce Coalition Logic of Temporal Knowledge (CLTK), by incorporating a temporal logic of knowledge (Halpern and Vardi’s logic of CKL n ) into CL to equip CL with the power to formalize how agents’ knowledge (individual or group knowledge) evolves over the time by the coalitional forces and the temporal properties of strategic abilities as well. Furthermore, we provide a complete axiomatization of CLTK, along with the complexity of the satisfiability problem, which is shown to be EXPTIME-complete.
This work is supported by National Natural Science Foundation of China grant No.61003056,71271061 and 61272415; National Basic Research 973 Program of China grant 2010CB328103; ARC Future Fellowship FT0991785, Fundamental Research Funds for the Central Universities of China grant No.21612413 and 21612414, and Business Intelligence Key Team of Guangdong University of Foreign Studies (TD1202). Corresponding author: Guiwu Hu (guiwuhu@gdcc.edu.cn).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Wooldridge, M.: An Introduction to Multiagent Systems, 2nd edn. John Wiley & Sons Press (2009)
Pauly, M.: A modal logic for coalitional power in games. Journal of Logic and Computation 12(1), 149–166 (2002)
Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. Journal of the ACM 49(5), 672–713 (2002)
Broersen, J.: A complete STIT logic for knowledge and action, and some of its applications. In: Baldoni, M., Son, T.C., van Riemsdijk, M.B., Winikoff, M. (eds.) DALT 2008. LNCS (LNAI), vol. 5397, pp. 47–59. Springer, Heidelberg (2009)
Halpern, J.Y., Fagin, R., Moses, Y., Vardi, M.Y.: Reasoning About Knowledge. MIT Press (1995)
Halpern, J.Y., Vardi, M.Y.: The complexity of reasoning about knowledge and time: Extended abstract. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, California, USA, May 28-30, pp. 304–315 (1986)
Goranko, V., van Drimmelen, G.: Complete axiomatization and decidability of alternating-time temporal logic. Theoretical Computer Science 353(1-3), 93–117 (2006)
Broersen, J., Herzig, A., Troquard, N.: A normal simulation of coalition logic and an epistemic extension. In: Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2007), Brussels, Belgium, pp. 92–101 (2007)
Broersen, J., Herzig, A., Troquard, N.: What groups do, can do, and know they can do: an analysis in normal modal logics. Journal of Applied Non-Classical Logics 19(3), 261–290 (2009)
Ågotnes, T., Alechina, N.: Epistemic coalition logic: Completeness and complexity. In: Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), pp. 1099–1106. ACM Press (2012)
van der Hoek, W., Wooldridge, M.: Cooperation, knowledge, and time: Alternating-time temporal epistemic logic and its applications. Studia Logica 75(1), 125–157 (2003)
Jamroga, W., Ågotnes, T.: Constructive knowledge: What agents can achieve under imperfect information. Journal of Applied Non-Classical Logics 17(4), 423–475 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Chen, Q., Su, K., Hu, Y., Hu, G. (2014). Complete Axiomatization and Complexity of Coalition Logic of Temporal Knowledge for Multi-agent Systems. In: Sokolova, M., van Beek, P. (eds) Advances in Artificial Intelligence. Canadian AI 2014. Lecture Notes in Computer Science(), vol 8436. Springer, Cham. https://doi.org/10.1007/978-3-319-06483-3_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-06483-3_24
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06482-6
Online ISBN: 978-3-319-06483-3
eBook Packages: Computer ScienceComputer Science (R0)