On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic

Alechina, Natasha; Bulling, Nils; Logan, Brian; Nga, Nguyen Hoang

On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic

Natasha Alechina, Nils Bulling, Brian Logan, Nguyen Hoang Nga

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 1494-1500.

Abstract

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.

Natasha Alechina, Nils Bulling, Brian Logan, and Nguyen Hoang Nga. 2015. On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 1494–1500. https://ijcai.org/proceedings/2015/214

@inproceedings{ijcai2015p214,
  title     = {On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic},
  author    = {Alechina, Natasha and Bulling, Nils and Logan, Brian and Nga, Nguyen Hoang},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {1494--1500},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/214},
}

TY  - CPAPER
TI  - On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic
AU  - Alechina, Natasha
AU  - Bulling, Nils
AU  - Logan, Brian
AU  - Nga, Nguyen Hoang
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 1494
EP  - 1500
UR  - https://ijcai.org/proceedings/2015/214
ER  -