Verification of Relational Multiagent Systems with Data Types


  • Diego Calvanese Free University of Bozen-Bolzano
  • Giorgio Delzanno University of Genova
  • Marco Montali Free University of Bozen-Bolzano



relational multiagent systems, data-aware dynamic systems, temporal logics, formal verification


We study the extension of relational multiagent systems (RMASs), where agents manipulate full-fledged relational databases, with data types and facets equipped with domain-specific, rigid relations (such as total orders). Specifically, we focus on design-time verification of RMASs against rich first-order temporal properties expressed in a variant of first-order mu-calculus with quantification across states. We build on previous decidability results under the state-bounded assumption, i.e., in each single state only a bounded number of data objects is stored in the agent databases, while unboundedly many can be encountered over time. We recast this condition, showing decidability in presence of dense, linear orders, and facets defined on top of them. Our approach is based on the construction of a finite-state, sound and complete abstraction of the original system, in which dense linear orders are reformulated as non-rigid relations working on the active domain of the system only. We also show undecidability when including a data type equipped with the successor relation.




How to Cite

Calvanese, D., Delzanno, G., & Montali, M. (2015). Verification of Relational Multiagent Systems with Data Types. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1).



AAAI Technical Track: Multiagent Systems