Skip Navigation


Journal of Logic and Computation Advance Access originally published online on August 22, 2008
Journal of Logic and Computation 2009 19(4):539-564; doi:10.1093/logcom/exn040
This Article
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
19/4/539    most recent
exn040v1
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Gebser, M.
Right arrow Articles by Schaub, T.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

This article appears in the following Journal of Logic and Computation issue: Special Issue: Answer Set Programming [View the issue table of contents]

Original Papers

Monotonic Answer Set Programming*

Martin Gebser

Institut für Informatik, Universität Potsdam, August-Bebel-Str. 89, D-14482 Potsdam, Germany. E-mail: gebser{at}cs.uni-potsdam.de

Mona Gharib

Institut für Informatik, Universität Potsdam, August-Bebel-Str. 89, D-14482 Potsdam, Germany and Mathematics Department, Faculty of Science, Zagazig University, Zagazig, Egypt. E-mail: mona{at}cs.uni-potsdam.de

Robert Mercer

Computer Science Department, The University of Western, Ontario, London, Ontario, Canada N6A 5B7, Canada. E-mail: mercer{at}csd.uwo.ca

Torsten Schaub

Institut für Informatik, Universität Potsdam, August-Bebel-Str. 89, D-14482 Potsdam, Germany. E-mail: torsten{at}cs.uni-potsdam.de

Received 2 January 2008.


  Abstract

Answer set programming (ASP) does not allow for incrementally constructing answer sets or locally validating constructions like proofs by only looking at a part of the given program. In this article, we elaborate upon an alternative approach to ASP that allows for incremental constructions. Our approach draws its basic intuitions from the area of default logics. We investigate the feasibility of the concept of semi-monotonicity known from default logics as a basis of incrementality. On the one hand, every logic program has at least one answer set in our alternative setting, which moreover can be constructed incrementally based on generating rules. On the other hand, the approach may produce answer sets lacking characteristic properties of standard answer sets, such as being a model of the given program. We show how integrity constraints can be used to re-establish such properties, even up to correspondence with standard answer sets. Furthermore, we develop an SLD-like proof procedure for our incremental approach to ASP, which allows for query-oriented computations. Also, we provide a characterization of our definition of answer sets via a modification of Clark's completion. Based on this notion of program completion, we present an algorithm for computing the answer sets of a logic program in our approach.

Keywords: Logic Programming; Answer Set Programming; Monotonicity

*This article combines and refines preliminary versions in [13, 18].


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.