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

N. Alechina, N. Bulling, B. Logan, Hoan Nga Nguyen

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

10 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)
EditorsQiang Yang, Michael Wooldridge
Place of PublicationPalo Alto
PublisherAAAI Press / International Joint Conferences on Artificial Intelligence
Pages1494-1501
ISBN (Print)978-1-57735-738-4
Publication statusPublished - 2015
Externally publishedYes
EventInternational Joint Conference on Artificial Intelligence - Buenos Aires, Argentina
Duration: 25 Jul 201531 Jul 2015

Conference

ConferenceInternational Joint Conference on Artificial Intelligence
CountryArgentina
CityBuenos Aires
Period25/07/1531/07/15

Bibliographical note

The full text is available from: http://ijcai.org/Proceedings/15/Papers/214.pdf

Fingerprint Dive into the research topics of 'On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic'. Together they form a unique fingerprint.

  • Cite this

    Alechina, N., Bulling, N., Logan, B., & Nguyen, H. N. (2015). On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic. In Q. Yang, & M. Wooldridge (Eds.), Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015) (pp. 1494-1501). Palo Alto: AAAI Press / International Joint Conferences on Artificial Intelligence.