{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,13]],"date-time":"2025-09-13T16:22:43Z","timestamp":1757780563179,"version":"3.40.5"},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"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":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Logic Programs with Ordered Disjunction (LPODs) extend classical logic programs with the capability of expressing preferential disjunctions in the heads of program rules. The initial semantics of LPODs, although simple and quite intuitive, is not purely model-theoretic. As a result, certain properties of programs appear non-trivial to formalize in purely logical terms. For example, the current characterization of strong equivalence for LPODs, does not coincide with logical equivalence in some specific logic. This comes in sharp contrast with the well-known characterization of strong equivalence for classical logic programs, which coincides with logical equivalence in the logic of here-and-there. In this paper we obtain a purely logical characterization of strong equivalence for LPODs as logical equivalence in a four-valued logic. Moreover, we provide a new proof of the coNP-completeness of strong equivalence for LPODs, which has an interest in its own right since it relies on the special structure of such programs. Our results are based on the recent logical semantics of LPODs, a fact which we believe indicates that this new semantics may prove to be a useful tool in the further study of LPODs.<\/jats:p>","DOI":"10.1017\/s1471068422000242","type":"journal-article","created":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T10:56:05Z","timestamp":1656672965000},"page":"708-722","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Strong Equivalence of Logic Programs with Ordered Disjunction: A Logical Perspective"],"prefix":"10.1017","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7437-410X","authenticated-orcid":false,"given":"ANGELOS","family":"CHARALAMBIDIS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHRISTOS","family":"NOMIKOS","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PANOS","family":"RONDOGIANNIS","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,7,1]]},"reference":[{"key":"S1471068422000242_ref5","doi-asserted-by":"publisher","DOI":"10.1111\/j.0824-7935.2004.00241.x"},{"key":"S1471068422000242_ref9","unstructured":"Faber, W. , Truszczynski, M. and Woltran, S. 2013. Abstract preference frameworks - a unifying perspective on separability and strong equivalence. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA, M. desJardins and M. L. Littman, Eds. AAAI Press."},{"key":"S1471068422000242_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068421000235"},{"key":"S1471068422000242_ref8","unstructured":"Faber, W. , Tompits, H. and Woltran, S. 2008. Notions of strong equivalence for logic programs with ordered disjunction. In Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference, KR 2008, Sydney, Australia, September 16-19, 2008, G. Brewka and J. Lang, Eds. AAAI Press, 433\u2013443."},{"key":"S1471068422000242_ref14","doi-asserted-by":"crossref","unstructured":"Pearce, D. 1999. From Here to There: Stable Negation in Logic Programming. Applied Logic Series. Springer Netherlands, Dordrecht, 161\u2013181.","DOI":"10.1007\/978-94-015-9309-0_8"},{"key":"S1471068422000242_ref15","unstructured":"Pearce, D. , Tompits, H. and Woltran, S. 2001. Encodings for equilibrium logic and logic programs with nested expressions. In Progress in Artificial Intelligence, Knowledge Extraction, Multi-agent Systems, Logic Programming and Constraint Solving, 10th Portuguese Conference on Artificial Intelligence, EPIA 2001, Porto, Portugal, December 17-20, 2001, Proceedings, P. Brazdil and A. Jorge, Eds., vol. 2258. Lecture Notes in Computer Science. Springer, 306\u2013320."},{"key":"S1471068422000242_ref3","unstructured":"Brewka, G. 2002. Logic programming with ordered disjunction. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28 - August 1, 2002, Edmonton, Alberta, Canada 2002. AAAI Press\/The MIT Press, 100\u2013105."},{"key":"S1471068422000242_ref12","unstructured":"Lin, F. 2002. Reducing strong equivalence of logic programs to entailment in classical propositional logic. In Proceedings of the Eights International Conference on Principles and Knowledge Representation and Reasoning (KR-02), Toulouse, France, April 22-25, 2002, D. Fensel, F. Giunchiglia, D. L. McGuinness and M. Williams, Eds. Morgan Kaufmann, 170\u2013176."},{"key":"S1471068422000242_ref2","doi-asserted-by":"crossref","unstructured":"Bernreiter, M. , Maly, J. and Woltran, S. 2021. Choice logics and their computational properties. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event\/Montreal, Canada, 19-27 August 2021, Zhou, Z. , Ed. ijcai.org, 1794\u20131800.","DOI":"10.24963\/ijcai.2021\/247"},{"key":"S1471068422000242_ref6","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-2011-0494"},{"key":"S1471068422000242_ref13","doi-asserted-by":"crossref","unstructured":"Pearce, D. 1966. A new logical characterisation of stable models and answer sets. In Non-Monotonic Extensions of Logic Programming, NMELP \u201996, Bad Honnef, Germany, September 5-6, 1996, Selected Papers, vol. 1216. Lecture Notes in Computer Science. Springer, 57\u201370.","DOI":"10.1007\/BFb0023801"},{"key":"S1471068422000242_ref1","unstructured":"Balduccini, M. and Mellarkod, V. S. 2003. Cr-prolog with ordered disjunction. In Answer Set Programming, Advances in Theory and Implementation, Proceedings of the 2nd Intl. ASP\u201903 Workshop, Messina, Italy, September 26-28, 2003, vol. 78. CEUR Workshop Proceedings. CEUR-WS.org."},{"key":"S1471068422000242_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/383779.383783"},{"key":"S1471068422000242_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.04.006"},{"key":"S1471068422000242_ref10","unstructured":"Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, USA, August 15\u201319, 1988 (2 Volumes). MIT Press, 1070\u20131080."}],"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\/S1471068422000242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T01:07:19Z","timestamp":1660525639000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068422000242\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,1]]},"references-count":15,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["S1471068422000242"],"URL":"https:\/\/doi.org\/10.1017\/s1471068422000242","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2022,7,1]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. 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, provided the original article 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"}]}}