Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 4688))
Included in the following conference series:
1453Accesses
Abstract
Clarke and McMillan presented symbolic approaches to model check temporal logics via mu-calculus and OBDDs. These approaches are very efficient and can be applied to verify many practical systems with extremely large state spaces in excess of 1020 states. However, these approaches cannot model check knowledge logics. But temporal logics of knowledge can describe more accurately the desirable specification of systems and protocols in distributed systems. In this paper, the symbolic approaches to model check the temporal logic of knowledge via extended mu-calculus and OBDDs are discussed mainly. First the mu-calculus is extended. Then the symbolic approaches to model check temporal logics of knowledge via extended mu-calculus and OBDDs are presented.
Supported by the National Natural Science Foundation of China under Grant No.90604006 and No.60496327.
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
van der Meyden, R., Shilov, N.V.: Model Checking Knowledge and Time in Systems with Perfect Recall(Extended Abstract). In: Pandu Rangan, C., Raman, V., Ramanujam, R. (eds.) Foundations of Software Technology and Theoretical Computer Science. LNCS, vol. 1738, pp. 432–445. Springer, Heidelberg (1999)
van der Meyden, R., Shilov, N.V.: Model Checking Knowledge and Time in Systems with Perfect Recall. In: Pandu Rangan, C., Raman, V., Ramanujam, R. (eds.) Foundations of Software Technology and Theoretical Computer Science. LNCS, vol. 1738, Springer, Heidelberg (1999)
van der Hoek, W., Wooldridge, M.: Model Checking Knowledge and Time. In: Stefan Leue, C.C. (ed.) 9th international SPIN workshop on model checking of software, pp. 1–16 (2002)
van der Meyden, R., Su, K.: Symbolic model checking the knowledge of the dining cryptographers. In: The 17th IEEE Security Foundation Workshop, pp. 280–291. IEEE Computer Society Press, Los Alamitos (2004)
Su, K.: Model Checking Temporal Logics of Knowledge in Distributed Systems. In: AAAI 2004. The Nineteenth National Conference on Artificial Intelligence (2004)
Li-Jun, W., Kai-Le, S.: A Model Checking Algorithm for Temporal Logics of Knowledge in Multi-Agent System. Journal of Software 15(7), 1012–1020 (2004)
Kozen, D.: Results on the prepositional mu-calculus. Theoretical Computer Science 27, 333–354 (1983)
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transaction on computers 35(8), 687–691 (1986)
Clarke, E.M., Grumberg, O., Peled, D.A.: Model checking, 1st edn. MIT Press, Cambridge (1999)
Burch, J.R., Clarke, E.M., McMillan, K.L.: Symbolic model checking: 1020 states and beyond. Information and Computation 2, 142–170 (1998)
Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning about Knowledge, 1st edn., pp. 111–120. MIT Press, Cambridge (1995)
Mitchell, J.C., Shmatikov, V., Stern, U.: Finite-state analysis of SSL 3.0. In: Proc. 7th USENIX Security Symposium, pp. 201–215 (1998)
Wozna, B., Lomuscio, A., Penczek, W.: Bounded Model Checking for Knowledge and Real Time. In: AAMAS 2005. Proceedings of the 4th International Joint Conference on Autonomous Agents and Multi Agent Systems, ACM Press, New York (2005)
Raimondi, F., Lomuscio, A.: MCMAS: a tool for verifying multi-agent systems. In: Hermanns, H., Palsberg, J. (eds.) TACAS 2006 and ETAPS 2006. LNCS, vol. 3920, Springer, Heidelberg (2006)
Lomuscio, A., Raimondi, F.: Model checking knowledge, strategies, and games in multi-agent systems. In: AAMAS 2006. Proceedings of the 5th International Conference on Autonomous Agents and Multi-Agent systems, ACM Press, New York (2006)
Su, K., Sattar, A., Wang, K., Luo, X., Governatori, G., Padmanabhan, V.: Observation-based model for BDI-agents. In: AAAI 2005 (2005)
Author information
Authors and Affiliations
School of Computer Science, National University of Defense and Technology, 410073 Changsha, China
Lijun Wu & Jinshu Su
- Lijun Wu
You can also search for this author inPubMed Google Scholar
- Jinshu Su
You can also search for this author inPubMed Google Scholar
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wu, L., Su, J. (2007). Symbolic Model Checking Temporal Logics of Knowledge in Multi-Agent System Via Extended Mu-Calculus. In: Li, K., Fei, M., Irwin, G.W., Ma, S. (eds) Bio-Inspired Computational Intelligence and Applications. LSMS 2007. Lecture Notes in Computer Science, vol 4688. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74769-7_55
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-74768-0
Online ISBN:978-3-540-74769-7
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative