Strategic Reasoning with a Bounded Number of Resources: the Quest for Tractability - Informatique, Biologie Intégrative et Systèmes Complexes 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⟩
172 Consultations
138 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More