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)


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
Number of pages13
ISBN (Electronic)978-3-642-20895-9
ISBN (Print)978-3-642-20894-2
Publication statusPublished - 2011

Publication series

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


Dive into the research topics of 'Communicating ASP and the Polynomial Hierarchy'. Together they form a unique fingerprint.

Cite this