Abstract

Proceedings Abstracts of the Twenty-Fourth International Joint Conference on Artificial Intelligence

On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic / 1494
Natasha Alechina, Nils Bulling, Brian Logan, Hoang Nga Nguyen
PDF

The model-checking problem for Resource Agent Logic is known to be undecidable. We review existing (un)decidability results and identify a significant fragment of the logic for which model checking is decidable. We discuss aspects which makes model checking decidable and prove undecidability of two open fragments over a class of models in which agents always have a choice of doing nothing. We also discuss the effect of structures where each agent always has an option of choosing an action that does not produce or consume resources on the decidability.