.png){kind=icon}
.png){kind=icon}
Return
Communicative commitments: Model checking and complexity analysis
.png){kind=icon}
PRE
AI
DOI：10.1016/j.knosys.2012.04.010.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We refine CTLC, a temporal logic of social commitments that extends CTL to allow reasoning about commitments agents create when communicating and their fulfillment. We present axioms of commitments and their fulfillment and provide the associated BDD-based model checking algorithms. We also analyze the time complexity of CTLC model checking in explicit models (i.e., Kripke-like structures) and its space complexity for concurrent programs, which provide compact representations. We prove that although CTLC extends CTL, their model checking algorithms still have the same time complexity for explicit models, which is P-complete with regard to the size of the model and length of the formula, and the same complexity for concurrent programs, which is PSPACE-complete with regard to the size of the components of these programs. We fully implemented the proposed algorithms on top of MCMAS, a model checker for the verification of multi-agent systems, and provide in this paper simulation results of an industrial case study. (C) 2012 Elsevier B.V. All rights reserved.
Keywords:
Multi-agent systems
Social commitments
Agent communication
Model checking
Complexity
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
K
IF:
7.6
Papers:
1.2W
Citations:
4.5W