Strategic Reasoning with a Bounded Number of Resources: the Quest for Tractability - Laboratoire Méthodes Formelles Accéder directement au contenu
Article Dans Une Revue Artificial Intelligence Année : 2021

Strategic Reasoning with a Bounded Number of Resources: the Quest for Tractability

Résumé

The resource-bounded alternating-time temporal logic RB±ATL combines strategic reasoning with reasoning about resources. Its model-checking problem is known to be 2EXPTIME-complete (the same as its proper extension RB±ATL$^⁎$) and fragments have been identified to lower the complexity. In this work, we consider the variant RB±ATL+ that allows for Boolean combinations of path formulae starting with single temporal operators, but restricted to a single resource, providing an interesting trade-off between temporal expressivity and resource analysis. We show that the model-checking problem for RB±ATL+ restricted to a single agent and a single resource is $\Delta_{2}^{P}$-complete, hence the same as for the standard branching-time temporal logic CTL+. In this case reasoning about resources comes at no extra computational cost. When a fixed finite set of linear-time temporal operators is considered, the model-checking problem drops to PTIME, which includes the special case of RB±ATL restricted to a single agent and a single resource. Furthermore, we show that, with an arbitrary number of agents and a fixed number of resources, the model-checking problem for RB±ATL+ can be solved in EXPTIME using a sophisticated Turing reduction to the parity game problem for alternating vector addition systems with states (AVASS).
Fichier principal
Vignette du fichier
main.pdf (620.38 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03298703 , version 1 (23-07-2021)

Identifiants

Citer

Francesco Belardinelli, Stéphane Demri. Strategic Reasoning with a Bounded Number of Resources: the Quest for Tractability. Artificial Intelligence, 2021, 300, pp.103557. ⟨10.1016/j.artint.2021.103557⟩. ⟨hal-03298703⟩
189 Consultations
140 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More