Concepts, Agents, and Coalitions in Alternating Time

摘要

We consider a combination of the strategic logic ATL with the description logic ALCO. In order to combine the logics in a flexible way, we assume that every individual can be (potentially) an agent. We also take the novel approach to teams by assuming that a coalition has an identity on its own, and hence its membership can vary. In terms of technical results, we show that the logic does not have the finite model property, though both ATL and ALCO do. We conjecture that the satisfiability problem may be undecidable. On the other hand, model checking of the combined logic is decidable and even tractable. Finally, we define a particular variant of realizability that combines satisfiability of ALCO with model checking of the ATL dimension, and we show that this new problem is decidable.