License
when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICLP.2012.222
URN: urn:nbn:de:0030-drops-36246
URL: http://drops.dagstuhl.de/opus/volltexte/2012/3624/

Oetsch, Johannes ; Pührer, Jörg ; Tompits, Hans

An FLP-Style Answer-Set Semantics for Abstract-Constraint Programs with Disjunctions

pdf-format:
Dokument 1.pdf (424 KB)


Abstract

We introduce an answer-set semantics for abstract-constraint programs with disjunction in rule heads in the style of Faber, Leone, and Pfeifer (FLP). To this end, we extend the definition of an answer set for logic programs with aggregates in rule bodies using the usual FLP-reduct. Additionally, we also provide a characterisation of our semantics in terms of unfounded sets, likewise generalising the standard concept of an unfounded set. Our work is motivated by the desire to have simple and rule-based definitions of the semantics of an answer-set programming (ASP) language that is close to those implemented by the most prominent ASP solvers. The new definitions are intended as a theoretical device to allow for development methods and methodologies for ASP, e.g., debugging or testing techniques, that are general enough to work for different types of solvers. We use abstract constraints as an abstraction of literals whose truth values depend on subsets of an interpretation. This includes weight constraints, aggregates, and external atoms, which are frequently used in real-world answer-set programs. We compare the new semantics to previous semantics for abstract-constraint programs and show that they are equivalent to recent extensions of the FLP semantics to propositional and first-order theories when abstract-constraint programs are viewed as theories.

BibTeX - Entry

@InProceedings{oetsch_et_al:LIPIcs:2012:3624,
  author =	{Johannes Oetsch and J{\"o}rg P{\"u}hrer and Hans Tompits},
  title =	{{An FLP-Style Answer-Set Semantics for Abstract-Constraint Programs with Disjunctions}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{222--234},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Agostino Dovier and V{\'i}tor Santos Costa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3624},
  URN =		{urn:nbn:de:0030-drops-36246},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.ICLP.2012.222},
  annote =	{Keywords: answer-set programming, abstract constraints, aggregates, disjunction}
}

Keywords: answer-set programming, abstract constraints, aggregates, disjunction
Seminar: Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)
Issue date: 2012
Date of publication: 27.07.2012


DROPS-Home | Fulltext Search | Imprint Published by LZI