Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Symbolic Model Checking Temporal Logics of Knowledge in Multi-Agent System Via Extended Mu-Calculus

  • Conference paper

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.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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)

    Chapter  Google Scholar 

  2. 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)

    Google Scholar 

  3. 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)

    Google Scholar 

  4. 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)

    Chapter  Google Scholar 

  5. Su, K.: Model Checking Temporal Logics of Knowledge in Distributed Systems. In: AAAI 2004. The Nineteenth National Conference on Artificial Intelligence (2004)

    Google Scholar 

  6. 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)

    Google Scholar 

  7. Kozen, D.: Results on the prepositional mu-calculus. Theoretical Computer Science 27, 333–354 (1983)

    Article MATH MathSciNet  Google Scholar 

  8. Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transaction on computers 35(8), 687–691 (1986)

    Article  Google Scholar 

  9. Clarke, E.M., Grumberg, O., Peled, D.A.: Model checking, 1st edn. MIT Press, Cambridge (1999)

    Google Scholar 

  10. Burch, J.R., Clarke, E.M., McMillan, K.L.: Symbolic model checking: 1020 states and beyond. Information and Computation 2, 142–170 (1998)

    MathSciNet  Google Scholar 

  11. Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning about Knowledge, 1st edn., pp. 111–120. MIT Press, Cambridge (1995)

    MATH  Google Scholar 

  12. Mitchell, J.C., Shmatikov, V., Stern, U.: Finite-state analysis of SSL 3.0. In: Proc. 7th USENIX Security Symposium, pp. 201–215 (1998)

    Google Scholar 

  13. 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)

    Google Scholar 

  14. 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)

    Google Scholar 

  15. 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)

    Google Scholar 

  16. Su, K., Sattar, A., Wang, K., Luo, X., Governatori, G., Padmanabhan, V.: Observation-based model for BDI-agents. In: AAAI 2005 (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, National University of Defense and Technology, 410073 Changsha, China

    Lijun Wu & Jinshu Su

Authors
  1. Lijun Wu

    You can also search for this author inPubMed Google Scholar

  2. Jinshu Su

    You can also search for this author inPubMed Google Scholar

Editor information

Kang Li Minrui Fei George William Irwin Shiwei Ma

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

Publish with us


[8]ページ先頭

©2009-2025 Movatter.jp