An Abstraction Technique for the Verification of Multi-Agent Systems against ATL Specifications

ABSTRACT. We introduce an abstraction methodology for the verification of multi-agent systems against specifications in alternating time temporal logic (ATL). Inspired by methodologies such as predicate abstraction, we define a three-valued semantics for the interpretation of ATL formulas on concurrent game structures and compare it to the standard two-valued semantics. We define abstract models and establish preservation results on the three-valued semantics between abstract models and their concrete counterparts. We illustrate the methodology on the large state spaces resulting from a card game.