Complete axiomatization and decidability of Alternating-time temporal logic

AbstractAlternating-time Temporal Logic (ATL), introduced by Alur, Henzinger and Kupferman, is a logical formalism for the specification and verification of open systems involving multiple autonomous players (agents, components). In particular, this logic allows for the explicit expression of coalition abilities in such systems, modelled as infinite transition games between the coalition and its complement.Formally, ATL is a non-normal multi-modal extension of CTL (regarded as a one-player fragment of ATL) with temporal operators indexed by coalitions of players, and thus expressing selective quantification over those paths which can be effected as outcomes of infinite transition games between the coalition and its complement.We present a sound and complete axiomatization of the logic ATL, based on Pauly's axiomatization of his Coalition Logic, augmented with axioms and rules for fixed point formulae characterizing the temporal operators. The completeness proof is by construction of a bounded branching tree model for each ATL-consistent formula. These models can be folded into finite models, thus rendering the finite model property for ATL.We also describe an automata-based decision procedure for ATL by translating the satisfiability problem to the nonemptiness problem for alternating automata on infinite trees. When considering formulae over a fixed finite set of players the decidability problem is shown to be EXPTIME-complete