Scalable Verification of Strategy Logic through Three-Valued Abstraction

Francesco Belardinelli; Angelo Ferrando; Wojciech Jamroga; Vadim Malvone; Aniello Murano

IJCAI 2023poster6 citations

Scalable Verification of Strategy Logic through Three-Valued Abstraction

Francesco Belardinelli, Angelo Ferrando, Wojciech Jamroga, Vadim Malvone, Aniello Murano

Abstract

The model checking problem for multi-agent systems against Strategy Logic specifications is known to be non-elementary. On this logic several fragments have been defined to tackle this issue but at the expense of expressiveness. In this paper, we propose a three-valued semantics for Strategy Logic upon which we define an abstraction method. We show that the latter semantics is an approximation of the classic two-valued one for Strategy Logic. Furthermore, we extend MCMAS, an open-source model checker for multi-agent specifications, to incorporate our abstraction method and present some promising experimental results.

Agent-based and Multi-agent Systems: MAS: Formal verification, validation and synthesisKnowledge Representation and Reasoning: KRR: Automated reasoning and theorem provingKnowledge Representation and Reasoning: KRR: Qualitative, geometric, spatial, and temporal reasoning

BibTeX

@inproceedings{ijcai2023p6,
  title     = {Scalable Verification of Strategy Logic through Three-Valued Abstraction},
  author    = {Belardinelli, Francesco and Ferrando, Angelo and Jamroga, Wojciech and Malvone, Vadim and Murano, Aniello},
  booktitle = {Proceedings of the Thirty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-23}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Edith Elkind},
  pages     = {46--54},
  year      = {2023},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2023/6},
  url       = {https://doi.org/10.24963/ijcai.2023/6},
}