Alternating Epistemic Mu-Calculus

Bulling, Nils; Jamroga, Wojciech

doi:10.5591/978-1-57735-516-8/IJCAI11-030

Alternating Epistemic Mu-Calculus

Nils Bulling, Wojciech Jamroga

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 109-113.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-030

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.

Nils Bulling, and Wojciech Jamroga. 2011. Alternating Epistemic Mu-Calculus. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 109–113. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-030

@inproceedings{ijcai2011p30,
  title     = {Alternating Epistemic Mu-Calculus},
  author    = {Bulling, Nils and Jamroga, Wojciech},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {109--113},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-030},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-030},
}

TY  - CPAPER
TI  - Alternating Epistemic Mu-Calculus
AU  - Bulling, Nils
AU  - Jamroga, Wojciech
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 109
EP  - 113
DO  - 10.5591/978-1-57735-516-8/IJCAI11-030
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-030
ER  -