{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T03:55:14Z","timestamp":1762055714315,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2022,6,8]],"date-time":"2022-06-08T00:00:00Z","timestamp":1654646400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Cooperation in Science &amp; Technology (COST) Action","award":["CA17124","2020-116201GB-I00","ED431B-2022\/23","ED431G-2019\/01","Y698"],"award-info":[{"award-number":["CA17124","2020-116201GB-I00","ED431B-2022\/23","ED431G-2019\/01","Y698"]}]},{"name":"Ministerio de Ciencia e Innovaci\u00f3n, Spain","award":["CA17124","2020-116201GB-I00","ED431B-2022\/23","ED431G-2019\/01","Y698"],"award-info":[{"award-number":["CA17124","2020-116201GB-I00","ED431B-2022\/23","ED431G-2019\/01","Y698"]}]},{"name":"Conseller\u00eda de Educaci\u00f3n, Universidade e Formaci\u00f3n Profesiona","award":["CA17124","2020-116201GB-I00","ED431B-2022\/23","ED431G-2019\/01","Y698"],"award-info":[{"award-number":["CA17124","2020-116201GB-I00","ED431B-2022\/23","ED431G-2019\/01","Y698"]}]},{"name":"Austrian Science Fund (FWF)","award":["CA17124","2020-116201GB-I00","ED431B-2022\/23","ED431G-2019\/01","Y698"],"award-info":[{"award-number":["CA17124","2020-116201GB-I00","ED431B-2022\/23","ED431G-2019\/01","Y698"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Answer Set Programming (ASP) is a well established logical approach in artificial intelligence that is widely used for knowledge representation and problem solving. Equilibrium logic extends answer set semantics to more general classes of programs and theories. When intertheory relations are studied in ASP, or in the more general form of equilibrium logic, they are usually understood in the form of comparisons of the answer sets or equilibrium models of theories or programs. This is the case for strong and uniform equivalence and their relativised and projective versions. However, there are many potential areas of application of ASP for which query answering is relevant and a comparison of programs in terms of what can be inferred from them may be important. We formulate and study some natural equivalence and entailment concepts for programs and theories that are couched in terms of inference and query answering. We show that, for the most part, these new intertheory relations coincide with their model-theoretic counterparts. We also extend some previous results on projective entailment for theories and for the new connective called fork.<\/jats:p>","DOI":"10.3390\/a15060201","type":"journal-article","created":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T10:49:14Z","timestamp":1654771754000},"page":"201","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Comparing the Reasoning Capabilities of Equilibrium Theories and Answer Set Programs"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3917-8717","authenticated-orcid":false,"given":"Jorge","family":"Fandinno","sequence":"first","affiliation":[{"name":"College of Information Science & Technology, University of Nebraska Omaha, 6001 Dodge St., Omaha, NE 68182, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7407-326X","authenticated-orcid":false,"given":"David","family":"Pearce","sequence":"additional","affiliation":[{"name":"Departamento de Inteligencia Artificial, Universidad Polit\u00e9cnica de Madrid, 28040 Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5561-6406","authenticated-orcid":false,"given":"Concepci\u00f3n","family":"Vidal","sequence":"additional","affiliation":[{"name":"Computer Science and Information Technologies, University of Corunna, 15008 A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1594-8972","authenticated-orcid":false,"given":"Stefan","family":"Woltran","sequence":"additional","affiliation":[{"name":"Databases and Artificial Intelligence Group (E192-02), Institute of Logic and Computation, Technische Universit\u00e4t Wien, 1040 Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,6,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10472-006-9028-z","article-title":"Equilibrium logic","volume":"47","author":"Pearce","year":"2006","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/383779.383783","article-title":"Strongly equivalent logic programs","volume":"2","author":"Lifschitz","year":"2001","journal-title":"ACM Trans. Comput. Log."},{"key":"ref_3","unstructured":"Kaelbling, L.P., and Saffiotti, A. (August, January 30). On solution correspondences in answer-set programming. Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI\u201905), Edinburgh, UK."},{"key":"ref_4","first-page":"224","article-title":"Uniform equivalence of logic programs under the stable model semantics","volume":"Volume 2916","author":"Palamidessi","year":"2003","journal-title":"Logic Programming, Proceedings of the 19th International Conference, ICLP 2003, Mumbai, India, 9\u201313, December 2003"},{"key":"ref_5","first-page":"161","article-title":"Characterizations for relativized notions of equivalence in answer set programming","volume":"Volume 3229","author":"Alferes","year":"2004","journal-title":"Logics in Artificial Intelligence, Proceedings of the 9th European Conference, JELIA 2004, Lisbon, Portugal, 27\u201330 September 2004"},{"key":"ref_6","unstructured":"Minker, J. (1988). Equivalences of Logic Programs. Foundations of Deductive Databases and Logic Programming, Morgan Kaufmann."},{"key":"ref_7","unstructured":"Minker, J. (1988). Optimising DATALOG Programs. Foundations of Deductive Databases and Logic Programming, Morgan Kaufmann."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10472-007-9049-2","article-title":"Strong and uniform equivalence of nonmonotonic theories\u2014An algebraic approach","volume":"48","author":"Truszczynski","year":"2006","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_9","first-page":"289","article-title":"Strong equivalence for causal theories","volume":"Volume 2923","author":"Lifschitz","year":"2004","journal-title":"Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR\u201904)"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.artint.2012.08.004","article-title":"Normal and strong expansion equivalence for argumentation frameworks","volume":"193","author":"Baumann","year":"2012","journal-title":"Artif. Intell."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1985","DOI":"10.1016\/j.artint.2011.06.003","article-title":"Characterizing strong equivalence for argumentation frameworks","volume":"175","author":"Oikarinen","year":"2011","journal-title":"Artif. Intell."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bernreiter, M., Maly, J., and Woltran, S. (2021, January 19\u201327). Choice logics and their computational properties. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, Virtual.","DOI":"10.24963\/ijcai.2021\/247"},{"key":"ref_13","unstructured":"Faber, W., and Konczak, K. (August, January 30). Strong equivalence for logic programs with preferences. Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, UK."},{"key":"ref_14","unstructured":"des Jardins, M., and Littman, M.L. (2013, January 14\u201318). Abstract preference frameworks\u2014A unifying perspective on separability and strong equivalence. Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, Bellevue, WA, USA."},{"key":"ref_15","first-page":"87","article-title":"Simplifying logic programs under uniform and strong equivalence","volume":"Volume 2923","author":"Lifschitz","year":"2004","journal-title":"Proceedings of the LPNMR 2004"},{"key":"ref_16","unstructured":"Fox, M.S., and Kaminka, G.A. (September, January 29). You can\u2019t always forget what you want: On the limits of forgetting in answer set programming. Proceedings of the ECAI 2016, The Hague, The Netherlands."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Shmueli, O. (1987, January 23\u201325). Decidability and Expressiveness Aspects of Logic Queries. Proceedings of the 6th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS\u201987), San Diego, CA, USA.","DOI":"10.1145\/28659.28685"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2018.09.003","article-title":"Query inseparability for ALC ontologies","volume":"272","author":"Botoeva","year":"2019","journal-title":"Artif. Intell."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1017\/S1471068415000277","article-title":"A denotational semantics for equilibrium logic","volume":"15","author":"Aguado","year":"2015","journal-title":"Theory Pract. Log. Program."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1016\/j.artint.2019.07.005","article-title":"Forgetting auxiliary atoms in forks","volume":"275","author":"Aguado","year":"2019","journal-title":"Artif. Intell."},{"key":"ref_21","first-page":"42","article-title":"Die formalen Regeln der intuitionistischen Logik","volume":"16","author":"Heyting","year":"1930","journal-title":"Sitzungsberichte der Preussischen Akademie der Wissenschaften zu Berlin"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1080\/11663081.2018.1439358","article-title":"Stable reasoning","volume":"27","author":"Cabalar","year":"2017","journal-title":"J. Appl. Non Class. Logics"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"van Dalen, D. (2013). Logic and Structure, Springer.","DOI":"10.1007\/978-1-4471-4558-5"},{"key":"ref_24","first-page":"57","article-title":"A new logical characterisation of stable models and answer sets","volume":"Volume 1216","author":"Dix","year":"1996","journal-title":"Non-Monotonic Extensions of Logic Programming, Proceedings of the NMELP \u201996, Bad Honnef, Germany, 5\u20136 September 1996"},{"key":"ref_25","unstructured":"Kowalski, R., and Bowen, A. (1988, January 15\u201319). The stable models semantics for logic programming. Proceedings of the 5th International Conference on Logic Programming, Seattle, WA, USA."},{"key":"ref_26","first-page":"99","article-title":"Equivalences in answer-set programming by countermodels in the logic of here-and-there","volume":"Volume 5366","author":"Banda","year":"2008","journal-title":"Logic Programming, Proceedings of the 24th International Conference, ICLP 2008, Udine, Italy, 9\u201313 December 2008"},{"key":"ref_27","first-page":"194","article-title":"Uniform equivalence for equilibrium logic and logic programs","volume":"Volume 2923","author":"Lifschitz","year":"2004","journal-title":"Logic Programming and Nonmonotonic Reasoning, Proceedings of the 7th International Conference, LPNMR 2004, Fort Lauderdale, FL, USA, 6\u20138 January 2004"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2:1","DOI":"10.1145\/3422361","article-title":"Beyond uniform equivalence between answer-set programs","volume":"22","author":"Oetsch","year":"2021","journal-title":"ACM Trans. Comput. Log."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"107","DOI":"10.3233\/JCS-1993-22-304","article-title":"Authorization in distributed systems: A new approach","volume":"2","author":"Woo","year":"1993","journal-title":"J. Comput. Secur."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Chomicki, J., Meyden, R.V., and Saake, G. (2003). Logics for authorization and security. Logics for Emerging Applications of Databases, Springer.","DOI":"10.1007\/978-3-642-18690-5"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"de Moor, O., Gottlob, G., Furche, T., and Sellers, A. (2011). Datalog for security, privacy and trust. Datalog Reloaded, Springer.","DOI":"10.1007\/978-3-642-24206-9"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Henk, C., van Tilborg, A., and Jajodia, S. (2011). Logic-based authorization languages. Encyclopedia of Cryptography and Security, Springer. [2nd ed.].","DOI":"10.1007\/978-1-4419-5906-5"},{"key":"ref_33","unstructured":"Li, W., Susilo, W., Tupakula, U.K., Safavi-Naini, R., and Varadharajan, V. (2009, January 10\u201312). Expressive policy analysis with enhanced system dynamicity. Proceedings of the 2009 ACM Symposium on Information, Computer and Communications Security, ASIACCS 2009, Sydney, Australia."},{"key":"ref_34","first-page":"22","article-title":"Authorization and obligation policies in dynamic systems","volume":"Volume 5366","author":"Banda","year":"2008","journal-title":"Logic Programming, Proceedings of the 24th International Conference, ICLP 2008, Udine, Italy, 9\u201313 December2008, Proceedings"},{"key":"ref_35","unstructured":"Pearce, D., Tompits, H., and Woltran, S. (2007, January 14). Relativised equivalence in equilibrium logic and its applications to prediction and explanation: Preliminary report. Proceedings of the LPNMR\u201907 Workshop on Correspondence and Equivalence for Nonmonotonic Theories (CENT2007), Tempe, AZ, USA."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/978-3-540-72200-7_17","article-title":"A characterization of strong equivalence for logic programs with variables","volume":"Volume 4483","author":"Baral","year":"2007","journal-title":"Logic Programming and Nonmonotonic Reasoning, Proceedings of the 9th International Conference, LPNMR 2007, Tempe, AZ, USA, 15\u201317 May 2007"},{"key":"ref_37","first-page":"542","article-title":"Characterising relativised strong equivalence with projection for non-ground answer-set programs","volume":"Volume 11468","author":"Calimeri","year":"2019","journal-title":"Logics in Artificial Intelligence, Proceedings of the 16th European Conference, JELIA 2019, Rende, Italy, 7\u201311 May 2019"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/6\/201\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:26:23Z","timestamp":1760138783000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/6\/201"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,8]]},"references-count":37,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2022,6]]}},"alternative-id":["a15060201"],"URL":"https:\/\/doi.org\/10.3390\/a15060201","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,6,8]]}}}