{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T20:00:40Z","timestamp":1762027240108,"version":"build-2065373602"},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T00:00:00Z","timestamp":1600732800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Weighted Logic is a powerful tool for the specification of calculations over semirings that depend on qualitative information. Using a novel combination of Weighted Logic and Here-and-There (HT) Logic, in which this dependence is based on intuitionistic grounds, we introduce Answer Set Programming with Algebraic Constraints (ASP(<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S1471068420000393_inline1.png\"\/><jats:tex-math>$\\mathcal A \\mathcal C$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>)), where rules may contain constraints that compare semiring values to weighted formula evaluations. Such constraints provide streamlined access to a manifold of constructs available in ASP, like aggregates, choice constraints, and arithmetic operators. They extend some of them and provide a generic framework for defining programs with algebraic computation, which can be fruitfully used e.g. for provenance semantics of datalog programs. While undecidable in general, expressive fragments of ASP(<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S1471068420000393_inline1.png\"\/><jats:tex-math>$\\mathcal A \\mathcal C$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>) can be exploited for effective problem solving in a rich framework.<\/jats:p>","DOI":"10.1017\/s1471068420000393","type":"journal-article","created":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T02:43:15Z","timestamp":1600742595000},"page":"895-910","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":5,"title":["ASP (): Answer Set Programming with Algebraic Constraints"],"prefix":"10.1017","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6003-6345","authenticated-orcid":false,"given":"THOMAS","family":"EITER","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8866-3452","authenticated-orcid":false,"given":"RAFAEL","family":"KIESEL","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,9,22]]},"reference":[{"key":"S1471068420000393_ref20","unstructured":"20. Lierler, Y. and Lifschitz, V. 2009. One more decidable class of finitely ground programs. In Proc. ICLP\u201909. Springer, 489\u2013493."},{"key":"S1471068420000393_ref25","unstructured":"25. Niemel\u00e4, I. , Simons, P. , and Soininen, T. 1999. Stable model semantics of weight constraint rules. In Proc. LPNMR\u201999. Springer, 317\u2013331."},{"key":"S1471068420000393_ref1","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1017\/S147106841300032X","article-title":"Stable model semantics for founded bounds","volume":"4","author":"Aziz","year":"2013","journal-title":"Theory Pract. Log. Program. 13,"},{"key":"S1471068420000393_ref21","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/383779.383783","article-title":"Strongly equivalent logic programs","volume":"4","author":"Lifschitz","year":"2001","journal-title":"ACM TOCL 2"},{"key":"S1471068420000393_ref5","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1017\/S1471068410000517","article-title":"Functional answer set programming","volume":"2","author":"Cabalar","year":"2011","journal-title":"Theory and Practice of Logic Programming 11"},{"key":"S1471068420000393_ref2","unstructured":"2. Balai, E. , Gelfond, M. , and Zhang, Y. 2013. Sparc-sorted asp with consistency restoring rules. arXiv preprint arXiv:1301.1386."},{"key":"S1471068420000393_ref15","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1017\/S1471068414000222","article-title":"Vicious circle principle and logic programs with aggregates","volume":"4","author":"Gelfond","year":"2014","journal-title":"Theory and Practice of Logic Programming 14"},{"key":"S1471068420000393_ref24","unstructured":"24. Marek, V. W. , Niemela, I. , et al. 2006. Logic programs with monotone abstract constraint atoms. arXiv preprint cs\/0608103."},{"key":"S1471068420000393_ref13","first-page":"25","article-title":"Logic programs with propositional connectives and aggregates","volume":"4","author":"Ferraris","year":"2011","journal-title":"ACM TOCL 12"},{"key":"S1471068420000393_ref19","first-page":"1","article-title":"Relating constraint answer set programming languages and algorithms","author":"Lierler","year":"2014","journal-title":"Artificial Intelligence 207"},{"key":"S1471068420000393_ref6","unstructured":"6. Cabalar, P. , Fandinno, J. , Schaub, T. , and Wanko, P. 2020a. An ASP semantics for constraints involving conditional aggregates. arXiv preprint arXiv:2002.06911."},{"key":"S1471068420000393_ref26","unstructured":"26. Pearce, D. and Valverde, A. 2008. Quantified equilibrium logic and foundations for answer set programs. In Proc. ICLP\u201908, Garcia de la Banda, M. and Pontelli, E. , Eds. Springer, 546\u2013560."},{"key":"S1471068420000393_ref9","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/502807.502810","article-title":"Complexity and expressive power of logic programming","volume":"3","author":"Dantsin","year":"2001","journal-title":"ACM Comput. Surv. 33"},{"key":"S1471068420000393_ref11","unstructured":"11. Eiter, T. and Kiesel, R. 2020. Weighted lars for quantitative stream reasoning. In Proc. ECAI\u201920."},{"key":"S1471068420000393_ref14","unstructured":"14. Ferraris, P. and Lifschitz, V. 2010. On the stable model semantics of first-order formulas with aggregates. In Proc. International Workshop on Nonmonotonic Reasoning (NMR\u201910)."},{"key":"S1471068420000393_ref3","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.artint.2019.01.001","article-title":"First-order stable model semantics with intensional functions","author":"Bartholomew","year":"2019","journal-title":"Artificial Intelligence 273"},{"key":"S1471068420000393_ref27","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1613\/jair.2171","article-title":"Answer sets for logic programs with arbitrary abstract constraint atoms","author":"Son","year":"2007","journal-title":"Journal of Artificial Intelligence Research 29"},{"key":"S1471068420000393_ref4","unstructured":"4. Bistarelli, S. , Montanari, U. , and Rossi, F. 1997. Semiring-based constraint logic programming. In Proc. IJCAI\u201997. 352\u2013357."},{"key":"S1471068420000393_ref10","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.tcs.2007.02.055","article-title":"Weighted automata and weighted logics","volume":"1","author":"Droste","year":"2007","journal-title":"Theor.Comp.Sci. 380"},{"key":"S1471068420000393_ref12","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/j.artint.2010.04.002","article-title":"Semantics and complexity of recursive aggregates in answer set programming","volume":"1","author":"Faber","year":"2011","journal-title":"Artificial Intelligence 175"},{"key":"S1471068420000393_ref22","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1023\/A:1018978005636","article-title":"Nested expressions in logic programs","volume":"3","author":"Lifschitz","year":"1999","journal-title":"Annals of Mathematics and Artificial Intelligence 25"},{"key":"S1471068420000393_ref23","first-page":"1","article-title":"The computational complexity of probabilistic planning","author":"Littman","year":"1998","journal-title":"J. Artificial Intelligence Research 9"},{"key":"S1471068420000393_ref18","doi-asserted-by":"crossref","unstructured":"18. Kimmig, A. , Van den Broeck, G. , and De Raedt, L. 2011. An algebraic prolog for reasoning about possible worlds. In Proc. AAAI\u201911.","DOI":"10.1609\/aaai.v25i1.7852"},{"key":"S1471068420000393_ref16","unstructured":"16. Green, T. J. , Karvounarakis, G. , and Tannen, V. 2007. Provenance semirings. In Proc. ACM PODS\u201907. ACM, 31\u201340."},{"key":"S1471068420000393_ref8","unstructured":"8. Cassaigne, J. , Halava, V. , Harju, T. , and Nicolas, F. 2014. Tighter undecidability bounds for matrix mortality, zero-in-the-corner problems, and more. CoRR abs\/1404.0644."},{"key":"S1471068420000393_ref17","first-page":"125","article-title":"Answer set programming related with other solving paradigms","volume":"2","author":"Janhunen","year":"2018","journal-title":"KI 32"},{"key":"S1471068420000393_ref7","doi-asserted-by":"crossref","unstructured":"7. Cabalar, P. , Fandinno, J. , Schaub, T. , and Wanko, P. 2020b. A uniform treatment of aggregates and constraints in hybrid ASP. arXiv preprint arXiv:2003.04176.","DOI":"10.24963\/kr.2020\/20"}],"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\/S1471068420000393","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T11:41:51Z","timestamp":1668858111000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068420000393\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,22]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["S1471068420000393"],"URL":"https:\/\/doi.org\/10.1017\/s1471068420000393","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2020,9,22]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}