AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
Alternating Epistemic Mu-Calculus
Nils Bulling, Wojciech Jamroga

Last modified: 2011-06-28

Abstract


Alternating-time temporal logic (ATL) is a well-known logic for reasoning about strategic abilities of agents. An important feature that distinguishes variants of ATL for imperfect information scenarios is that the standard fixed point characterizations of temporal modalities do not hold anymore. In this paper, we show that adding explicit fixed point operators to the "next-time" fragment of ATL already allows to capture abilities that could not be expressed in ATL. We also illustrate that the new language allows to specify important kinds of abilities, namely ones where the agents can always recompute their strategy while executing it. Thus, the agents are not assumed to remember their strategy by definition, like in the existing variants of ATL. Last but not least, we show that verification of such abilities can be cheaper than for all the variants of `"ATL with imperfect information" considered so far.

Full Text: PDF