{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T07:26:53Z","timestamp":1648884413426},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2011,6,30]],"date-time":"2011-06-30T00:00:00Z","timestamp":1309392000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Weight constraint and aggregate programs are among the most widely used logic programs with constraints. In this paper, we relate the semantics of these two classes of programs, namely, the stable model semantics for weight constraint programs and the answer set semantics based on conditional satisfaction for aggregate programs. Both classes of programs are instances of logic programs with constraints, and in particular, the answer set semantics for aggregate programs can be applied to weight constraint programs. We show that the two semantics are closely related. First, we show that for a broad class of weight constraint programs, called <jats:italic>strongly satisfiable programs<\/jats:italic>, the two semantics coincide. When they disagree, a stable model admitted by the stable model semantics may be circularly justified. We show that the gap between the two semantics can be closed by transforming a weight constraint program to a strongly satisfiable one so that no circular models may be generated under the current implementation of the stable model semantics. We further demonstrate the close relationship between the two semantics by formulating a transformation from weight constraint programs to logic programs with nested expressions, which preserves the answer set semantics. Our study on the semantics leads to an investigation of a methodological issue, namely, the possibility of compact representation of aggregate programs by weight constraint programs. We show that almost all standard aggregates can be encoded by weight constraints compactly. This makes it possible to compute the answer sets of aggregate programs using the answer set programming solvers for weight constraint programs. This approach is compared experimentally with the ones where aggregates are handled more explicitly, which show that the weight constraint encoding of aggregates enables a competitive approach to answer set computation for aggregate programs.<\/jats:p>","DOI":"10.1017\/s147106841100038x","type":"journal-article","created":{"date-parts":[[2011,6,30]],"date-time":"2011-06-30T12:44:29Z","timestamp":1309437869000},"page":"1-31","source":"Crossref","is-referenced-by-count":2,"title":["Relating weight constraint and aggregate programs: Semantics and representation"],"prefix":"10.1017","volume":"13","author":[{"given":"GUOHUA","family":"LIU","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JIA-HUAI","family":"YOU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,6,30]]},"reference":[{"key":"S147106841100038X_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002973"},{"key":"S147106841100038X_ref17","unstructured":"Gelfond M. and Lifschitz V. 1988. The stable model semantics for logic programming. In Proc. of International Conference on Logic Programming (ICLP), 1070\u20131080."},{"key":"S147106841100038X_ref7","unstructured":"Denecker M. , Vennekens J. , Bond S. , Gebser M. and Truszczynski M. 2009. The second answer set programming competition. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR), 637\u2013654."},{"key":"S147106841100038X_ref38","unstructured":"You J. , Yuan L. Y. , Liu G. and Shen Y. 2007. Logic programs with abstract constraints: Representation, disjunction and complexities. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR '07), 228\u2013240."},{"key":"S147106841100038X_ref35","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1613\/jair.2171","article-title":"Answer sets for logic programs with arbitrary abstract constraint atoms","volume":"29","author":"Son","year":"2007","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S147106841100038X_ref36","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116838"},{"key":"S147106841100038X_ref32","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068409990056"},{"key":"S147106841100038X_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068406002936"},{"key":"S147106841100038X_ref30","unstructured":"Pelov N. , Denecker M. and Bruynooghe M. 2004. Partial stable models for logic programs with aggregates. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR '04), 207\u2013219."},{"key":"S147106841100038X_ref25","unstructured":"Marek V. and Truszczy\u0144ski M. 2004. Logic programs with abstract constraint atoms. In Proc. of Association for the Advancement of Artificial Intelligence (AAAI '04), 86\u201391."},{"key":"S147106841100038X_ref3","unstructured":"Caldiran O. , Haspalamutgil K. , Ok A. , Palaz C. , Erdem E. and Patoglu V. 2009. Bridging the gap between high-level reasoning and low-level control. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR), 342\u2013354."},{"key":"S147106841100038X_ref23","unstructured":"Liu G. and You J. 2008. Lparse programs revisited: semantics and representation of aggregates. In Proc. of International Conference on Logic Programming (ICLP '08), 347\u2013361."},{"key":"S147106841100038X_ref6","unstructured":"Denecker M. , Pelov N. and Bruynooghe M. 2001. Ultimate well-founded and stable semantics for logic programs with aggregates. In Proc. of International Conference on Logic Programming (ICLP '01), 212\u2013226."},{"key":"S147106841100038X_ref2","unstructured":"Balduccini M. , Gelfond M. , Watson R. and Nogueira M. 2001. The USA-advisor: A case study in answer set planning. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR), 439\u2013442."},{"key":"S147106841100038X_ref5","unstructured":"Delgrande J. P. , Grote T. and Hunter A. 2009. A general approach to the verification of cryptographic protocols using answer set programming. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR), 355\u2013367."},{"key":"S147106841100038X_ref8","unstructured":"Elkabani I. , Pontelli E. and Son T. C. 2005. SmodelsA\u2014A system for computing answer sets of logic programs with aggregates. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR '05), 427\u2013431."},{"key":"S147106841100038X_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-006-9033-2"},{"key":"S147106841100038X_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2009.11.016"},{"key":"S147106841100038X_ref22","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1613\/jair.2009","article-title":"Properties and applications of programs with monotone and convex constraints","volume":"7","author":"Liu","year":"2006","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S147106841100038X_ref12","unstructured":"Ferraris P. 2005. Answer sets for propositional theories. In Proc. Logic Programming and Non-Monotonic Reasoning (LPNMR '05), 119\u2013131."},{"key":"S147106841100038X_ref27","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"key":"S147106841100038X_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04238-6"},{"key":"S147106841100038X_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00187-X"},{"key":"S147106841100038X_ref37","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2007.1008"},{"key":"S147106841100038X_ref20","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018978005636"},{"key":"S147106841100038X_ref10","unstructured":"Faber W. , Leone N. and Pfeifer G. 2004. Recursive aggregates in disjunctive logic programs. In Proc. of European Conference on Logics in Artificial Intelligence (JELIA '04), 200\u2013212."},{"key":"S147106841100038X_ref11","first-page":"51","article-title":"Consistency of Clark's completion and existence of stable models","volume":"1","author":"Fages","year":"1994","journal-title":"Journal of Methods of Logic in Computer Science"},{"key":"S147106841100038X_ref19","unstructured":"Ielpa S. M. , Iiritano S. , Leone N. and Ricca F. 2009. An ASP-based system for e-tourism. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR), 368\u2013381."},{"key":"S147106841100038X_ref26","unstructured":"Marek V. W. and Remmel J. B. 2004. Set constraints in logic programming. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR '04), 167\u2013179."},{"key":"S147106841100038X_ref1","unstructured":"Armi D. , Faber W. and Ielpa G. 2003. Aggregate functions in disjunctive logic programming: Semantics, complexity, and implementation in DLV*. In Proc. of International Joint Conference on Artificial Intelligence (IJCAI '03), 847\u2013852."},{"key":"S147106841100038X_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S1574-6526(07)03007-6"},{"key":"S147106841100038X_ref4","unstructured":"Calimeri F. , Faber W. , Leone N. and Perri S. 2005. Declarative and computational properties of logic programs with aggregates. In Proc. of International Joint Conference on Artificial Intelligence (IJCAI '05), 406\u2013411."},{"key":"S147106841100038X_ref14","unstructured":"Gebser M. , Kaufmann B. , Neumann A. and Schaub T. 2007a. Conflict-driven answer set solving. In Proc. of International Joint Conference on Artificial Intelligence (IJCAI '07), 386\u2013392."},{"key":"S147106841100038X_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001923"},{"key":"S147106841100038X_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/S147106840700302X"},{"key":"S147106841100038X_ref28","unstructured":"Oetsch J. , Seidl M. , Tompits H. and Woltran S. 2009. cct on stage: Generalised uniform equivalence testing for verifying student assignment solutions. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR), 382\u2013395."},{"key":"S147106841100038X_ref15","unstructured":"Gebser M. , Liu L. , Namasivayam G. , Neumann A. , Schaub T. and Truszczy\u0144ski M. 2007b. The first answer set programming system competition. In Proc. of Logic Programming and Non-Monotonic Reasoning (LPNMR '07), 1\u201317."},{"key":"S147106841100038X_ref29","unstructured":"Pelov N. , Denecker M. and Bruynooghe M. 2003. Translation of aggregate programs to normal logic programs. In Proc. of Answer Set Programming (ASP '03), 29\u201342."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S147106841100038X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T19:58:05Z","timestamp":1556135885000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S147106841100038X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,30]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["S147106841100038X"],"URL":"https:\/\/doi.org\/10.1017\/s147106841100038x","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,30]]}}}