TY - GEN
T1 - Hyperequivalence of logic programs with respect to supported models
AU - Truszczyński, Mirostaw
AU - Woltran, Stefan
PY - 2008
Y1 - 2008
N2 - Recent research in nonmonotonic logic programming has focused on program equivalence relevant for program optimization and modular programming. So far, most results concern the stable-model semantics. However, other semantics for logic programs are also of interest, especially the semantics of supported models which, when properly generalized, is closely related to the autoepistemic logic of Moore. In this paper, we consider a framework of equivalence notions for logic programs under the supported (minimal) model-semantics and provide characterizations for this framework in model-theoretic terms. We use these characterizations to derive complexity results concerning testing hyperequivalence of logic programs wrt supported (minimal) models.
AB - Recent research in nonmonotonic logic programming has focused on program equivalence relevant for program optimization and modular programming. So far, most results concern the stable-model semantics. However, other semantics for logic programs are also of interest, especially the semantics of supported models which, when properly generalized, is closely related to the autoepistemic logic of Moore. In this paper, we consider a framework of equivalence notions for logic programs under the supported (minimal) model-semantics and provide characterizations for this framework in model-theoretic terms. We use these characterizations to derive complexity results concerning testing hyperequivalence of logic programs wrt supported (minimal) models.
UR - http://www.scopus.com/inward/record.url?scp=57749202886&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57749202886&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:57749202886
SN - 9781577353683
T3 - Proceedings of the National Conference on Artificial Intelligence
SP - 560
EP - 565
BT - AAAI-08/IAAI-08 Proceedings - 23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference
T2 - 23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference, AAAI-08/IAAI-08
Y2 - 13 July 2008 through 17 July 2008
ER -