Strong equivalence of logic programs under the infinite-valued semantics |
| |
Authors: | Christos Nomikos William W Wadge |
| |
Affiliation: | a Department of Computer Science, University of Ioannina, P.O. Box 1186, 45110 Ioannina, Greece b Department of Informatics & Telecommunications, University of Athens, Panepistimiopolis, 157 84 Athens, Greece c Department of Computer Science, University of Victoria, P.O. Box 3055, STN CSC, Victoria, BC, Canada V8W 3P6 |
| |
Abstract: | We consider the notion of strong equivalence V. Lifschitz, D. Pearce, A. Valverde, Strongly equivalent logic programs, ACM Transactions on Computational Logic 2 (4) (2001) 526-541] of normal propositional logic programs under the infinite-valued semantics P. Rondogiannis, W.W. Wadge, Minimum model semantics for logic programs with negation-as-failure, ACM Transactions on Computational Logic 6 (2) (2005) 441-467] (which is a purely model-theoretic semantics that is compatible with the well-founded one). We demonstrate that two such programs are strongly equivalent under the infinite-valued semantics if and only if they are logically equivalent in the corresponding infinite-valued logic. In particular, we show that strong equivalence of normal propositional logic programs is decidable, and more specifically coNP-complete. Our results have a direct implication for the well-founded semantics since, as we demonstrate, if two programs are strongly equivalent under the infinite-valued semantics, then they are also strongly equivalent under the well-founded semantics. |
| |
Keywords: | Formal semantics Negation in logic programming Strong equivalence |
本文献已被 ScienceDirect 等数据库收录! |
|