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

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 proceeding › Conference proceeding › peer-review

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 language	English
Title of host publication	Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)
Editors	Qiang Yang, Michael Wooldridge
Place of Publication	Palo Alto
Publisher	AAAI Press / International Joint Conferences on Artificial Intelligence
Pages	1494-1501
ISBN (Print)	978-1-57735-738-4
Publication status	Published - 2015
Externally published	Yes
Event	International Joint Conference on Artificial Intelligence - Buenos Aires, Argentina Duration: 25 Jul 2015 → 31 Jul 2015

Conference

Conference	International Joint Conference on Artificial Intelligence
Country/Territory	Argentina
City	Buenos Aires
Period	25/07/15 → 31/07/15

Bibliographical note

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

Access to Document

http://ijcai.org/Abstract/15/214

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). AAAI Press / International Joint Conferences on Artificial Intelligence. http://ijcai.org/Abstract/15/214

On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic. / Alechina, N.; Bulling, N.; Logan, B. et al.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015) . ed. / Qiang Yang; Michael Wooldridge. Palo Alto: AAAI Press / International Joint Conferences on Artificial Intelligence, 2015. p. 1494-1501.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding › peer-review

Alechina, N, Bulling, N, Logan, B & Nguyen, HN 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) . AAAI Press / International Joint Conferences on Artificial Intelligence, Palo Alto, pp. 1494-1501, International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, 25/07/15. <http://ijcai.org/Abstract/15/214>

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

Alechina, N. ; Bulling, N. ; Logan, B. et al. / On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015) . editor / Qiang Yang ; Michael Wooldridge. Palo Alto : AAAI Press / International Joint Conferences on Artificial Intelligence, 2015. pp. 1494-1501

@inproceedings{7bb0d0115f8f4a9d83b1ae7068441497,

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

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.",

author = "N. Alechina and N. Bulling and B. Logan and Nguyen, {Hoan Nga}",

note = "The full text is available from: http://ijcai.org/Proceedings/15/Papers/214.pdf; International Joint Conference on Artificial Intelligence ; Conference date: 25-07-2015 Through 31-07-2015",

year = "2015",

language = "English",

isbn = "978-1-57735-738-4",

pages = "1494--1501",

editor = "Qiang Yang and Wooldridge, {Michael }",

booktitle = "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)",

publisher = "AAAI Press / International Joint Conferences on Artificial Intelligence",

address = "United States",

}

TY - GEN

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

AU - Alechina, N.

AU - Bulling, N.

AU - Logan, B.

AU - Nguyen, Hoan Nga

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

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

M3 - Conference proceeding

SN - 978-1-57735-738-4

SP - 1494

EP - 1501

BT - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)

A2 - Yang, Qiang

A2 - Wooldridge, Michael

PB - AAAI Press / International Joint Conferences on Artificial Intelligence

CY - Palo Alto

T2 - International Joint Conference on Artificial Intelligence

Y2 - 25 July 2015 through 31 July 2015

ER -

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

Abstract

Conference

Bibliographical note

Access to Document

Fingerprint

Cite this