Strong Equivalence of Logic Programs with Ordered Disjunction: a Logical Perspective
| Autor: | ANGELOS CHARALAMBIDIS, CHRISTOS NOMIKOS, PANOS RONDOGIANNIS |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Logic in Computer Science TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Artificial Intelligence (cs.AI) Computational Theory and Mathematics Computer Science - Artificial Intelligence Artificial Intelligence Hardware and Architecture Computer Science::Logic in Computer Science Software Theoretical Computer Science Logic in Computer Science (cs.LO) |
| DOI: | 10.48550/arxiv.2205.04882 |
| Popis: | 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. A consequence of this is that certain properties of programs appear non-trivial to formalize in purely logical terms. An example of this state of affairs is the characterization of the notion of strong equivalence for LPODs. Although the results of Faber et al. (2008) are accurately developed, they fall short of characterizing strong equivalence of LPODs as logical equivalence in some specific logic. This comes in sharp contrast with the well-known characterization of strong equivalence for classical logic programs, which, as proved by Lifschitz et al. (2001), coincides with logical equivalence in the logic of here-and-there. In this paper we obtain a purely logical characterization of strong equivalence of 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 introduced by Charalambidis et al. (2021), a fact which we believe indicates that this new semantics may prove to be a useful tool in the further study of LPODs. Comment: Paper presented at the 38th International Conference on Logic Programming (ICLP 2022), 15 pages + 3 pages appendix |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|