Verifying Computation Tree Logic of Knowledge via Knowledge-Oriented Petri Nets and Ordered Binary Decision Diagrams

keywords: Epistemic logic, model checking, Petri nets, multi-agent systems, OBDD, CTLK
Computation Tree Logic of Knowledge (CTLK) can specify many requirements of privacy and security of multi-agent systems (MAS). In our previous papers, we defined Knowledge-oriented Petri Net (KPN) to model MAS, proposed similar reachability graph to verify CTLK, gave their model checking algorithms and developed a related tool. In this paper, we use the technique of Ordered Binary Decision Diagrams (OBDD) to encode similar reachability graph in order to alleviate the state explosion problem, and verify more epistemic operators of CTLK. We design the corresponding symbolic model checking algorithms and improve our tool. We compare our model and method with MCMAS that is the state-of-the-art CTLK model checker, and experiments illustrate the advantages of our model and method. We also explain the reasons why our model and method can obtain better performances.
reference: Vol. 40, 2021, No. 5, pp. 1174–1196