Ghent University Academic Bibliography

Advanced

Expressiveness of communication in answer set programming

Kim Bauters UGent, Steven Schockaert UGent, Jeroen Janssen, Dirk Vermeir and Martine De Cock UGent (2013) THEORY AND PRACTICE OF LOGIC PROGRAMMING. 13(3). p.361-394
abstract
Answer set programming (ASP) is a form of declarative programming that allows to succinctly formulate and efficiently solve complex problems. An intuitive extension of this formalism is communicating ASP, in which multiple ASP programs collaborate to solve the problem at hand. However, the expressiveness of communicating ASP has not been thoroughly studied. In this paper, we present a systematic study of the additional expressiveness offered by allowing ASP programs to communicate. First, we consider a simple form of communication where programs are only allowed to ask questions to each other. For the most part, we deliberately only consider simple programs, i.e. programs for which computing the answer sets is in P. We find that the problem of deciding whether a literal is in some answer set of a communicating ASP program using simple communication is NP-hard. In other words: we move up a step in the polynomial hierarchy due to the ability of these simple ASP programs to communicate and collaborate. Second, we modify the communication mechanism to also allow us to focus on a sequence of communicating programs, where each program in the sequence may successively remove some of the remaining models. This mimics a network of leaders, where the first leader has the first say and may remove models that he or she finds unsatisfactory. Using this particular communication mechanism allows us to capture the entire polynomial hierarchy. This means, in particular, that communicating ASP could be used to solve problems that are above the second level of the polynomial hierarchy, such as some forms of abductive reasoning as well as PSPACE-complete problems such as STRIPS planning.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
logic programming, answer set programming, multi-agent reasoning, COMPLEXITY, LOGICS, MODEL
journal title
THEORY AND PRACTICE OF LOGIC PROGRAMMING
Theory Pract. Log. Program.
volume
13
issue
3
pages
361 - 394
Web of Science type
Article
Web of Science id
000318311900002
JCR category
LOGIC
JCR impact factor
0.896 (2013)
JCR rank
2/20 (2013)
JCR quartile
1 (2013)
ISSN
1471-0684
DOI
10.1017/S1471068411000561
language
English
UGent publication?
yes
classification
A1
copyright statement
I have transferred the copyright for this publication to the publisher
id
1984132
handle
http://hdl.handle.net/1854/LU-1984132
date created
2012-01-12 10:04:55
date last changed
2016-12-19 15:46:41
@article{1984132,
  abstract     = {Answer set programming (ASP) is a form of declarative programming that allows to succinctly formulate and efficiently solve complex problems. An intuitive extension of this formalism is communicating ASP, in which multiple ASP programs collaborate to solve the problem at hand. However, the expressiveness of communicating ASP has not been thoroughly studied. In this paper, we present a systematic study of the additional expressiveness offered by allowing ASP programs to communicate. First, we consider a simple form of communication where programs are only allowed to ask questions to each other. For the most part, we deliberately only consider simple programs, i.e. programs for which computing the answer sets is in P. We find that the problem of deciding whether a literal is in some answer set of a communicating ASP program using simple communication is NP-hard. In other words: we move up a step in the polynomial hierarchy due to the ability of these simple ASP programs to communicate and collaborate. Second, we modify the communication mechanism to also allow us to focus on a sequence of communicating programs, where each program in the sequence may successively remove some of the remaining models. This mimics a network of leaders, where the first leader has the first say and may remove models that he or she finds unsatisfactory. Using this particular communication mechanism allows us to capture the entire polynomial hierarchy. This means, in particular, that communicating ASP could be used to solve problems that are above the second level of the polynomial hierarchy, such as some forms of abductive reasoning as well as PSPACE-complete problems such as STRIPS planning.},
  author       = {Bauters, Kim and Schockaert, Steven and Janssen, Jeroen and Vermeir, Dirk and De Cock, Martine},
  issn         = {1471-0684},
  journal      = {THEORY AND PRACTICE OF LOGIC PROGRAMMING},
  keyword      = {logic programming,answer set programming,multi-agent reasoning,COMPLEXITY,LOGICS,MODEL},
  language     = {eng},
  number       = {3},
  pages        = {361--394},
  title        = {Expressiveness of communication in answer set programming},
  url          = {http://dx.doi.org/10.1017/S1471068411000561},
  volume       = {13},
  year         = {2013},
}

Chicago
Bauters, Kim, Steven Schockaert, Jeroen Janssen, Dirk Vermeir, and Martine De Cock. 2013. “Expressiveness of Communication in Answer Set Programming.” Theory and Practice of Logic Programming 13 (3): 361–394.
APA
Bauters, Kim, Schockaert, S., Janssen, J., Vermeir, D., & De Cock, M. (2013). Expressiveness of communication in answer set programming. THEORY AND PRACTICE OF LOGIC PROGRAMMING, 13(3), 361–394.
Vancouver
1.
Bauters K, Schockaert S, Janssen J, Vermeir D, De Cock M. Expressiveness of communication in answer set programming. THEORY AND PRACTICE OF LOGIC PROGRAMMING. 2013;13(3):361–94.
MLA
Bauters, Kim, Steven Schockaert, Jeroen Janssen, et al. “Expressiveness of Communication in Answer Set Programming.” THEORY AND PRACTICE OF LOGIC PROGRAMMING 13.3 (2013): 361–394. Print.