Reasoning with a Bounded Number of Resources in ATL+

Francesco Belardinelli, Stéphane Demri

Abstract

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*). Several fragments have been identified to lower the complexity. In this work, we consider the variant RB±ATL+ which permits 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 Δp2-complete, hence the same as for CTL+. In this case reasoning about resources comes at no extra computational cost. Furthermore, we show that, with an arbitrary number of agents and a fixed number of resources, the problem can be solved in EXPTIME using a Turing reduction to the parity game problem for alternating vector addition systems with states.
BibTeX
@inproceedings{belardinelli2020reasoning,
  author = {Francesco Belardinelli and Stéphane Demri},
  title = {{Reasoning with a Bounded Number of Resources in ATL+}},
  booktitle = {ECAI},
  year = {2020},
  doi = {10.3233/faia200147},
}

Loading related content...

Figure