Communicating ASP and the Polynomial Hierarchy

Kim Bauters, Steven Schockaert, Dirk Vermeir, Martine De Cock

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

3 Citations (Scopus)

Abstract

Communicating answer set programming is a framework to represent and reason about the combined knowledge of multiple agents using the idea of stable models. The semantics and expressiveness of this framework crucially depends on the nature of the communication mechanism that is adopted. The communication mechanism we introduce in this paper allows us to focus on a sequence of programs, where each program in the sequence may successively eliminate some of the remaining models. The underlying intuition is that of leaders and followers: each agent’s decisions are limited by what its leaders have previously decided. We show that extending answer set programs in this way allows us to capture the entire polynomial hierarchy.
Original languageEnglish
Title of host publicationLogic Programming and Nonmonotonic Reasoning: Proceedings of the 11th International Conference, LPNMR
EditorsJames P. Delgrande, Wolfgang Faber
PublisherSpringer-Verlag
Pages67-79
Number of pages13
Volume6645
ISBN (Electronic)978-3-642-20895-9
ISBN (Print)978-3-642-20894-2
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6645
ISSN (Print)0302-9743

Fingerprint

Polynomials
Communication
Multiple agents
Intuition
Follower
Programming

Cite this

Bauters, K., Schockaert, S., Vermeir, D., & Cock, M. D. (2011). Communicating ASP and the Polynomial Hierarchy. In J. P. Delgrande, & W. Faber (Eds.), Logic Programming and Nonmonotonic Reasoning: Proceedings of the 11th International Conference, LPNMR (Vol. 6645, pp. 67-79). (Lecture Notes in Computer Science; Vol. 6645). Springer-Verlag. https://doi.org/10.1007/978-3-642-20895-9_8
Bauters, Kim ; Schockaert, Steven ; Vermeir, Dirk ; Cock, Martine De. / Communicating ASP and the Polynomial Hierarchy. Logic Programming and Nonmonotonic Reasoning: Proceedings of the 11th International Conference, LPNMR. editor / James P. Delgrande ; Wolfgang Faber. Vol. 6645 Springer-Verlag, 2011. pp. 67-79 (Lecture Notes in Computer Science).
@inproceedings{dae8d1b2003340d7aaffa2df19294fba,
title = "Communicating ASP and the Polynomial Hierarchy",
abstract = "Communicating answer set programming is a framework to represent and reason about the combined knowledge of multiple agents using the idea of stable models. The semantics and expressiveness of this framework crucially depends on the nature of the communication mechanism that is adopted. The communication mechanism we introduce in this paper allows us to focus on a sequence of programs, where each program in the sequence may successively eliminate some of the remaining models. The underlying intuition is that of leaders and followers: each agent’s decisions are limited by what its leaders have previously decided. We show that extending answer set programs in this way allows us to capture the entire polynomial hierarchy.",
author = "Kim Bauters and Steven Schockaert and Dirk Vermeir and Cock, {Martine De}",
year = "2011",
doi = "10.1007/978-3-642-20895-9_8",
language = "English",
isbn = "978-3-642-20894-2",
volume = "6645",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag",
pages = "67--79",
editor = "Delgrande, {James P.} and Wolfgang Faber",
booktitle = "Logic Programming and Nonmonotonic Reasoning: Proceedings of the 11th International Conference, LPNMR",

}

Bauters, K, Schockaert, S, Vermeir, D & Cock, MD 2011, Communicating ASP and the Polynomial Hierarchy. in JP Delgrande & W Faber (eds), Logic Programming and Nonmonotonic Reasoning: Proceedings of the 11th International Conference, LPNMR. vol. 6645, Lecture Notes in Computer Science, vol. 6645, Springer-Verlag, pp. 67-79. https://doi.org/10.1007/978-3-642-20895-9_8

Communicating ASP and the Polynomial Hierarchy. / Bauters, Kim; Schockaert, Steven; Vermeir, Dirk; Cock, Martine De.

Logic Programming and Nonmonotonic Reasoning: Proceedings of the 11th International Conference, LPNMR. ed. / James P. Delgrande; Wolfgang Faber. Vol. 6645 Springer-Verlag, 2011. p. 67-79 (Lecture Notes in Computer Science; Vol. 6645).

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

TY - GEN

T1 - Communicating ASP and the Polynomial Hierarchy

AU - Bauters, Kim

AU - Schockaert, Steven

AU - Vermeir, Dirk

AU - Cock, Martine De

PY - 2011

Y1 - 2011

N2 - Communicating answer set programming is a framework to represent and reason about the combined knowledge of multiple agents using the idea of stable models. The semantics and expressiveness of this framework crucially depends on the nature of the communication mechanism that is adopted. The communication mechanism we introduce in this paper allows us to focus on a sequence of programs, where each program in the sequence may successively eliminate some of the remaining models. The underlying intuition is that of leaders and followers: each agent’s decisions are limited by what its leaders have previously decided. We show that extending answer set programs in this way allows us to capture the entire polynomial hierarchy.

AB - Communicating answer set programming is a framework to represent and reason about the combined knowledge of multiple agents using the idea of stable models. The semantics and expressiveness of this framework crucially depends on the nature of the communication mechanism that is adopted. The communication mechanism we introduce in this paper allows us to focus on a sequence of programs, where each program in the sequence may successively eliminate some of the remaining models. The underlying intuition is that of leaders and followers: each agent’s decisions are limited by what its leaders have previously decided. We show that extending answer set programs in this way allows us to capture the entire polynomial hierarchy.

U2 - 10.1007/978-3-642-20895-9_8

DO - 10.1007/978-3-642-20895-9_8

M3 - Conference contribution

SN - 978-3-642-20894-2

VL - 6645

T3 - Lecture Notes in Computer Science

SP - 67

EP - 79

BT - Logic Programming and Nonmonotonic Reasoning: Proceedings of the 11th International Conference, LPNMR

A2 - Delgrande, James P.

A2 - Faber, Wolfgang

PB - Springer-Verlag

ER -

Bauters K, Schockaert S, Vermeir D, Cock MD. Communicating ASP and the Polynomial Hierarchy. In Delgrande JP, Faber W, editors, Logic Programming and Nonmonotonic Reasoning: Proceedings of the 11th International Conference, LPNMR. Vol. 6645. Springer-Verlag. 2011. p. 67-79. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-20895-9_8