Abstract
This paper defines a general framework for testing equivalence of logic programs with respect to two parameters. Given two sets of rules \({\cal Q}\) and \({\cal R}\), two logic programs P 1 and P 2 are said to be update equivalent with respect to \(({\cal Q},{\cal R})\) if (P 1∖ Q)∪ R and (P 2∖ Q)∪ R have the same answer sets for any two logic programs \(Q\subseteq{\cal Q}\) and \(R\subseteq{\cal R}\). The notion of update equivalence is suitable to take program updates into account when two logic programs are compared. That is, the notion of relativity stipulates the languages of updates, and two parameters \({\cal Q}\) and \({\cal R}\) correspond to the languages for deletion and addition, respectively. Clearly, the notion of strong equivalence is a special case of update equivalence where \({\cal Q}\) is empty and \({\cal R}\) is the set of all rules in the language. In fact, the notion of update equivalence is strong enough to capture many other notions such as weak equivalence, update equivalence on common rules, and uniform equivalence. We also discuss computation and complexity of update equivalence.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brass, S., Dix, J.: Characterization of the disjunctive stable semantics by partial evaluation. Journal of Logic Programming 32(3), 207–228 (1997)
Eiter, T., Fink, M.: Uniform equivalence of logic programs under the stable model semantics. In: Palamidessi, C. (ed.) ICLP 2003. LNCS, vol. 2916, pp. 224–238. Springer, Heidelberg (2003)
Eiter, T., Fink, M., Sabbatini, G., Tompits, H.: Reasoning about evolving nonmonotonic knowledge bases. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS (LNAI), vol. 2250, pp. 407–421. Springer, Heidelberg (2001)
Eiter, T., Fink, M., Tompits, H., Woltran, S.: Simplifying logic programs under uniform and strong equivalence. In: Lifschitz, V., Niemelä, I. (eds.) LPNMR 2004. LNCS (LNAI), vol. 2923, pp. 87–99. Springer, Heidelberg (2003)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385 (1991)
Inoue, K.: A simple characterization of extended abduction. In: Palamidessi, C., Moniz Pereira, L., Lloyd, J.W., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Sagiv, Y., Stuckey, P.J. (eds.) CL 2000. LNCS (LNAI), vol. 1861, pp. 718–732. Springer, Heidelberg (2000)
Inoue, K., Sakama, C.: Negation as failure in the head. Journal of Logic Programming 35(1), 39–78 (1998)
Inoue, K., Sakama, C.: Disjunctive explanations. In: Stuckey, P.J. (ed.) ICLP 2002. LNCS, vol. 2401, pp. 317–332. Springer, Heidelberg (2002)
Kakas, C., Kowalski, R.A., Toni, F.: The role of abduction in logic programming. In: Gabbay, D.M., Hogger, C.J., Robinson, J.A. (eds.) Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 5, pp. 235–324. Oxford University Press, Oxford (1998)
Leite, J.A.: Evolving Knowledge Bases. IOS Press, Amsterdam (2003)
Lifschitz, V., Pearce, D., Valverde, A.: Strongly equivalent logic programs. ACM Transactions on Computational Logic 2, 526–541 (2001)
Lifschitz, V., Tang, L.R., Turner, H.: Nested expressions in logic programs. Annals of Mathematics and Artificial Intelligence 25, 369–389 (1999)
Lifschitz, V., Woo, T.Y.C.: Answer sets in general nonmonotonic reasoning (preliminary report). In: Proc. of KR 1992, pp. 603–614. Morgan Kaufmann, San Francisco (1992)
Lin, F.: Reducing strong equivalence of logic programs to entailment in classical propositional logic. In: Proc. of KR 2002, pp. 170–176. Morgan Kaufmann, San Francisco (2002)
Maher, M.J.: Equivalence of logic programs. In: [16], pp. 627–658 (1988)
Minker, J. (ed.): Foundations of Deductive Databases and Logic Programming. Morgan Kaufmann, San Francisco (1988)
Osorio, M., Navarro, J.A., Arrazola, J.: Equivalence in answer set programming. In: Pettorossi, A. (ed.) LOPSTR 2001. LNCS, vol. 2372, pp. 57–75. Springer, Heidelberg (2002)
Pearce, D., Tompits, H., Woltran, S.: Encodings for equilibrium logic and logic programs with nested expressions. In: Brazdil, P.B., Jorge, A.M. (eds.) EPIA 2001. LNCS (LNAI), vol. 2258, pp. 306–320. Springer, Heidelberg (2001)
Sagiv, Y.: Optimizing Datalog programs. In: [16], pp. 659–668 (1988)
Tamaki, H., Sato, T.: Unfold/fold transformation of logic programs. In: Proc. of the 2nd International Conference on Logic Programming, pp. 127–138 (1984)
Turner, H.: Strong equivalence made easy: nested expressions and weight constraints. Theory and Practice of Logic Programming 3(4-5), 609–622 (2003)
Woltran, S.: Characterizations for relativized notions of equivalence in answer set programming. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 161–173. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Inoue, K., Sakama, C. (2004). Equivalence of Logic Programs Under Updates. In: Alferes, J.J., Leite, J. (eds) Logics in Artificial Intelligence. JELIA 2004. Lecture Notes in Computer Science(), vol 3229. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30227-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-30227-8_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23242-1
Online ISBN: 978-3-540-30227-8
eBook Packages: Springer Book Archive