DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2009-02-01 - Article/Dans un journal avec peer-review - Anglais - 15 page(s)

Brihaye Thomas , Da Costa Lopes Arnaud, Laroussinie François, Markey Nicolas, "ATL with Strategy Contexts and Bounded Memory" in Lecture Notes in Computer Science, 5407, 92-106

  • Edition : Springer, Berlin (Germany)
  • Codes CREF : Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Mathématiques effectives (S820)
Texte intégral :

Abstract(s) :

(Anglais) We extend the alternating-time temporal logics ATL and ATL* with strategy contexts and memory constraints: the first extension makes strategy quantifiers to not "forget" the strategies being executed by the other players. The second extension allows strategy quantifiers to restrict to memoryless or bounded-memory strategies. We first consider expressiveness issues. We show that our logics can express important properties such as equilibria, and we formally compare them with other similar formalisms (ATL, ATL*, Game Logic, Strategy Logic, ...). We then address the problem of model-checking for our logics, especially we provide a PSPACE algorithm for the sublogics involving only memoryless strategies and an EXPSPACE algorithm for the bounded-memory case.

Identifiants :
  • DOI : 10.1007/978-3-540-92687-0_7