2009 | OriginalPaper | Buchkapitel
ATL with Strategy Contexts and Bounded Memory
verfasst von : Thomas Brihaye, Arnaud Da Costa, François Laroussinie, Nicolas Markey
Erschienen in: Logical Foundations of Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.