Abstract
Rules in logic programming encode information about mutual interdependencies between literals that is not captured by any of the commonly used semantics. This information becomes essential as soon as a program needs to be modified or further manipulated.
We argue that, in these cases, a program should not be viewed solely as the set of its models. Instead, it should be viewed and manipulated as the set of sets of models of each rule inside it. With this in mind, we investigate and highlight relations between the SE-model semantics and individual rules. We identify a set of representatives of rule equivalence classes induced by SE-models, and so pinpoint the exact expressivity of this semantics with respect to a single rule. We also characterise the class of sets of SE-interpretations representable by a single rule. Finally, we discuss the introduction of two notions of equivalence, both stronger than strong equivalence [1] and weaker than strong update equivalence [2], which seem more suitable whenever the dependency information found in rules is of interest.
An extended version of this paper with all the proofs is available at http://arxiv.org/abs/1102.5385
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
Lifschitz, V., Pearce, D., Valverde, A.: Strongly equivalent logic programs. ACM Transactions on Computational Logic 2(4), 526–541 (2001)
Inoue, K., Sakama, C.: Equivalence of logic programs under updates. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 174–186. Springer, Heidelberg (2004)
Damásio, C.V., Pereira, L.M., Schroeder, M.: REVISE: Logic programming and diagnosis. In: Fuhrbach, U., Dix, J., Nerode, A. (eds.) LPNMR 1997. LNCS, vol. 1265, pp. 354–363. Springer, Heidelberg (1997)
Alferes, J.J., Leite, J.A., Pereira, L.M., Przymusinska, H., Przymusinski, T.C.: Dynamic updates of non-monotonic knowledge bases. The Journal of Logic Programming 45(1-3), 43–70 (2000)
Eiter, T., Fink, M., Sabbatini, G., Tompits, H.: On properties of update sequences based on causal rejection. Theory and Practice of Logic Programming 2(6), 721–777 (2002)
Sakama, C., Inoue, K.: An abductive framework for computing knowledge base updates. Theory and Practice of Logic Programming 3(6), 671–713 (2003)
Zhang, Y.: Logic program-based updates. ACM Transactions on Computational Logic 7(3), 421–472 (2006)
Alferes, J.J., Banti, F., Brogi, A., Leite, J.A.: The refined extension principle for semantics of dynamic logic programming. Studia Logica 79(1), 7–32 (2005)
Delgrande, J.P., Schaub, T., Tompits, H.: A preference-based framework for updating logic programs. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS (LNAI), vol. 4483, pp. 71–83. Springer, Heidelberg (2007)
Delgrande, J.P., Schaub, T., Tompits, H., Woltran, S.: Belief revision of logic programs under answer set semantics. In: Brewka, G., Lang, J. (eds.) Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning, Sydney, Australia, September 16-19, pp. 411–421. AAAI Press, Menlo Park (2008)
Delgrande, J.P.: A Program-Level Approach to Revising Logic Programs under the Answer Set Semantics. In: Theory and Practice of Logic Programming, 26th Int’l. Conference on Logic Programming Special Issue, vol. 10(4-6), pp. 565–580 (2010)
Gärdenfors, P.: Belief Revision: An Introduction. In: Belief Revision, pp. 1–28. Cambridge University Press, Cambridge (1992)
Slota, M., Leite, J.: On semantic update operators for answer-set programs. In: Coelho, H., Studer, R., Wooldridge, M. (eds.) Proceedings of the 19th European Conference on Artificial Intelligence, Lisbon, Portugal, August 16-20. Frontiers in Artificial Intelligence and Applications, vol. 215, pp. 957–962. IOS Press, Amsterdam (2010)
Apt, K.R., Blair, H.A., Walker, A.: Towards a theory of declarative knowledge. In: Foundations of Deductive Databases and Logic Programming, pp. 89–148. Morgan Kaufmann, San Francisco (1988)
Dix, J.: A classification theory of semantics of normal logic programs: II. Weak properties. Fundamenta Informaticae 22(3), 257–288 (1995)
Łukasiewicz, J.: Die Logik und das Grundlagenproblem. In: Les Entretiens de Zürich sue les Fondements et la méthode des sciences mathématiques 1938, Zürich, pp. 82–100 (1941)
Pearce, D.: A new logical characterisation of stable models and answer sets. In: Dix, J., Przymusinski, T.C., Moniz Pereira, L. (eds.) NMELP 1996. LNCS, vol. 1216, pp. 57–70. Springer, Heidelberg (1997)
Turner, H.: Strong equivalence made easy: nested expressions and weight constraints. Theory and Practice of Logic Programming 3(4-5), 609–622 (2003)
Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Kowalski, R.A., Bowen, K.A. (eds.) Proceedings of the 5th International Conference and Symposium on Logic Programming, August 15-19, pp. 1070–1080. MIT Press, Washington (1988)
Inoue, K., Sakama, C.: Negation as failure in the head. Journal of Logic Programming 35(1), 39–78 (1998)
Cabalar, P., Pearce, D., Valverde, A.: Minimal logic programs. In: Dahl, V., Niemelä, I. (eds.) ICLP 2007. LNCS, vol. 4670, pp. 104–118. Springer, Heidelberg (2007)
Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, Cambridge (1990)
Alexandre Leite, J.: Evolving Knowledge Bases. Frontiers of Artificial Intelligence and Applications, vol. 81, xviii + 307 p. IOS Press, Amsterdam (2003); Hardcover
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Slota, M., Leite, J. (2011). Back and Forth between Rules and SE-Models. In: Delgrande, J.P., Faber, W. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2011. Lecture Notes in Computer Science(), vol 6645. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20895-9_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-20895-9_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20894-2
Online ISBN: 978-3-642-20895-9
eBook Packages: Computer ScienceComputer Science (R0)