Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity

@incollection{citeulike:2759743, abstract = {The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). They strengthen the modeling power of ASP, in terms of concise problem representations. While many important problems can be encoded using nonrecursive aggregates, some relevant examples lend themselves for the use of recursive aggregates. Previous semantic definitions typically agree in the nonrecursive case, but the picture is less clear for recursion. Some proposals explicitly avoid recursive aggregates, most others differ, and many of them do not satisfy desirable criteria, such as minimality or coincidence with answer sets in the aggregate-free case. In this paper we define a semantics for disjunctive programs with arbitrary aggregates (including monotone, antimonotone, and nonmonotone aggregates). This semantics is a fully declarative, genuine generalization of the answer set semantics for disjunctive logic programming (DLP). It is defined by a natural variant of the Gelfond-Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. We prove that our semantics guarantees the minimality (and therefore the incomparability) of answer sets, and demonstrate that it coincides with the standard answer set semantics on aggregate-free programs. Finally we analyze the computational complexity of this language, paying particular attention to the impact of syntactical restrictions on programs.}, author = {Faber, Wolfgang and Leone, Nicola and Pfeifer, Gerald }, citeulike-article-id = {2759743}, journal = {Logics in Artificial Intelligence}, keywords = {datalog, logic, sql}, pages = {200--212}, posted-at = {2008-05-06 05:47:50}, priority = {4}, title = {Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity}, url = {http://www.springerlink.com/content/0ypayfkrj07y1uu3 }, year = {2004} }

TY - CHAP ID - citeulike:2759743 L3 - citeulike-article-id:2759743 TI - Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity JF - Logics in Artificial Intelligence SP - 200 EP - 212 N2 - The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). They strengthen the modeling power of ASP, in terms of concise problem representations. While many important problems can be encoded using nonrecursive aggregates, some relevant examples lend themselves for the use of recursive aggregates. Previous semantic definitions typically agree in the nonrecursive case, but the picture is less clear for recursion. Some proposals explicitly avoid recursive aggregates, most others differ, and many of them do not satisfy desirable criteria, such as minimality or coincidence with answer sets in the aggregate-free case. In this paper we define a semantics for disjunctive programs with arbitrary aggregates (including monotone, antimonotone, and nonmonotone aggregates). This semantics is a fully declarative, genuine generalization of the answer set semantics for disjunctive logic programming (DLP). It is defined by a natural variant of the Gelfond-Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. We prove that our semantics guarantees the minimality (and therefore the incomparability) of answer sets, and demonstrate that it coincides with the standard answer set semantics on aggregate-free programs. Finally we analyze the computational complexity of this language, paying particular attention to the impact of syntactical restrictions on programs. KW - datalog KW - logic KW - sql AU - Faber, Wolfgang AU - Leone, Nicola AU - Pfeifer, Gerald PY - 2004/// UR - http://www.springerlink.com/content/0ypayfkrj07y1uu3 ER -