Towards SAT-based BMC for LTLK over Interleaved Interpreted Systems

• Autorzy: Penczek, W. , Woźna-Szcześniak, B. , Zbrzezny, A.
• Języki publikacji: EN

Abstrakty

EN

This paper makes two contributions to the verification of multi-agent systems modelled by interleaved interpreted systems. Firstly, the paper presents theoretical underpinnings of the SATbased bounded model checking (BMC) approach for LTL extended with the epistemic component (LTLK) over interleaved interpreted systems. Secondly, the BMC method has been implemented and tested on several benchmarks for MAS. The preliminary experimental results reveal advantages and disadvantages of our SAT-based BMC for LTLK and show that the method has a significant potential.

Słowa kluczowe

EN

bounded model checking; multi-agent systems

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 119, nr 3/4
• Strony: 373-392
• Opis fizyczny: Bibliogr. 23 poz., wykr.

Twórcy

autor

Penczek, W.

autor

Woźna-Szcześniak, B.

autor

Zbrzezny, A.

• IM&CS, Jan Długosz University Al. Armii Krajowej 13/15, 42-200 Częstochowa, Poland,

Bibliografia

• [1] P. A. Abdulla, P. Bjesse, and N. Eén. Symbolic reachability analysis based on SAT-solvers. In Proc. of the 6th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'00), volume 1785 of LNCS, pages 411-425. Springer-Verlag, 2000.
• [2] A. Biere, A. Cimatti, E. Clarke, O. Strichman, and Y. Zhu. Bounded model checking. In Highly Dependable Software, volume 58 of Advances in Computers. Academic Press, 2003. Pre-print.
• [3] R. Bordini, M. Fisher, C. Pardavila, W. Visser, and M. Wooldridge. Model checking multi-agent programs with CASP. In Proc. of the 15th Int. Conf. on Computer Aided Verification (CAV'03), volume 2725 of LNCS, pages 110-113. Springer-Verlag, 2003.
• [4] E. Clarke, O. Grumberg, and D. Peled. Model Checking. MIT Press, 1999.
• [5] K. Engelhardt, R. van der Meyden, and Y. Moses. Knowledge and the logic of local propositions. In Proc. of the 7th Int. Conf. on Theoretical Aspects of Rationality and Knowledge (TARK'98), pages 29-41, 1998.
• [6] R. Fagin, J. Y. Halpern, Y. Moses, and M. Vardi. Reasoning about Knowledge. MIT Press, Cambridge, 1995.
• [7] P. Gammie and R. van der Meyden. MCK: Model checking the logic of knowledge. In Proc. of the 16th Int. Conf. on Computer Aided Verification (CAV'04), volume 3114 of LNCS, pages 479-483. Springer-Verlag, 2004.
• [8] P. Gastin and D. Oddoux. Fast LTL to Büchi automata translation. In Proc. of the 13th Int. Conf. on Computer Aided Verification (CAV'01), volume 2102 of LNCS, pages 53-65. Springer-Verlag, 2001.
• [9] W. van der Hoek and M. Wooldridge. Model checking knowledge and time. In Proc. of the 9th Int. SPIN Workshop (SPIN'02), volume 2318 of LNCS, pages 95-111. Springer-Verlag, 2002.
• [10] W. van der Hoek and M. Wooldridge. Cooperation, knowledge, and time: Alternating-time temporal epistemic logic and its applications. Studia Logica, 75(1):125-157, 2003.
• [11] X. Huang, C. Luo, and R. van der Meyden. Improved bounded model checking for a fair branching-time temporal epistemic logic. In Proc. of 6th Int. Workshop on Model Checking and Artificial Intelligence (MoChArt 2010), volume 6572 of LNAI, pages 95-111. Springer, 2011.
• [12] A. Jones and A. Lomuscio. A BDD-based BMC approach for the verification of multi-agent systems. In Proc. of the Int. Workshop on Concurrency, Specification and Programming (CS&P'09), volume 1, pages 253-264. Warsaw University, 2009.
• [13] M. Kacprzak, A. Lomuscio, and W. Penczek. From bounded to unbounded model checking for temporal epistemic logic. Fundamenta Informaticae, 63(2-3):221-240, 2004.
• [14] A. Lomuscio, W. Penczek, and H. Qu. Partial order reduction for model checking interleaved multi-agent systems. In AAMAS, IFAAMAS Press, pages 659-666, 2010.
• [15] R. van der Mayden and K. Su. Symbolic model checking the knowledge of the dining cryptographers. In Proc. of the 17th IEEE Computer Security Foundations Workshop (CSFW-17), pages 280-291. IEEE Computer Society, June 2004.
• [16] A. Męski, W. Penczek, and M. Szreter. Bounded model checking linear time and knowledge using decision diagrams. In Proceedings of the International Workshop on Concurrency, Specification and Programming (CS&P'11), pages 363-375. Białystok University of Technology, 2011.
• [17] R. van der Meyden and N. V. Shilov. Model checking knowledge and time in systems with perfect recall. In Proc. of the 19th Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'99), volume 1738 of LNCS, pages 432-445. Springer-Verlag, 1999.
• [18] D. Peled. All from one, one for all: On model checking using representatives. In Proc. of the 5th Int. Conf. on Computer Aided Verification (CAV'93), volume 697 of LNCS, pages 409-423. Springer-Verlag, 1993.
• [19] W. Penczek and A. Lomuscio. Verifying epistemic properties of multi-agent systems via bounded model checking. Fundamenta Informaticae, 55(2):167-185, 2003.
• [20] F. Raimondi and A. Lomuscio. Automatic verification of multi-agent systems by model checking via OBDDs. Journal of Applied Logic, 5(2):235-251, 2007.
• [21] K. Su, Abdul Sattar, and Xiangyu Luo. Model checking temporal logics of knowledge via OBDDs. The Computer Journal, 50(4):403-420, 2007.
• [22] B. Woźna, A. Zbrzezny, and W. Penczek. Checking reachability properties for timed automata via SAT. Fundamenta Informaticae, 55(2):223-241, 2003.
• [23] A. Zbrzezny. A new translation from ECTL* to SAT. In Proceedings of the International Workshop on Concurrency, Specification and Programming (CS&P'11), pages 589-600, Pułtusk, Poland, 2011. Białystok University of Technology.