James Delgrande
Skip Abstract Section
Abstract
We address the problem of belief change in (nonmonotonic) logic programming under answer set semantics. Our formal techniques are analogous to those of distance-based belief revision in propositional logic. In particular, we build upon the model theory of logic programs furnished by SE interpretations, where an SE interpretation is a model of a logic program in the same way that a classical interpretation is a model of a propositional formula. Hence we extend techniques from the area of belief revision based on distance between models to belief change in logic programs.
We first consider belief revision: for logic programs P and Q, the goal is to determine a program R that corresponds to the revision of P by Q, denoted P * Q. We investigate several operators, including (logic program) expansion and two revision operators based on the distance between the SE models of logic programs. It proves to be the case that expansion is an interesting operator in its own right, unlike in classical belief revision where it is relatively uninteresting. Expansion and revision are shown to satisfy a suite of interesting properties; in particular, our revision operators satisfy all or nearly all of the AGM postulates for revision.
We next consider approaches for merging a set of logic programs, P1, ..., Pn. Again, our formal techniques are based on notions of relative distance between the SE models of the logic programs. Two approaches are examined. The first informally selects for each program Pi those models of Pi that vary the least from models of the other programs. The second approach informally selects those models of a program P0 that are closest to the models of programs P1, ..., Pn. In this case, P0 can be thought of as a set of database integrity constraints. We examine these operators with regards to how they satisfy relevant postulate sets.
Last, we present encodings for computing the revision as well as the merging of logic programs within the same logic programming framework. This gives rise to a direct implementation of our approach in terms of off-the-shelf answer set solvers. These encodings also reflect the fact that our change operators do not increase the complexity of the base formalism.
- Alchourrón, C., Gärdenfors, P., and Makinson, D. 1985. On the logic of theory change: Partial meet functions for contraction and revision. J. Symb. Logic 50, 2, 510--530.Google Scholar
Cross Ref
- Alferes, J., Leite, J., Pereira, L., Przymusinska, H., and Przymusinski, T. 2000. Dynamic updates of nonmonotonic knowledge bases. J. Logic Program. 45, 1--3, 43--70.Google ScholarCross Ref
- Alferes, J. J., Banti, F., Brogi, A., and Leite, J. A. 2005. The refined extension principle for semantics of dynamic logic programming. Studia Logica 79, 1, 7--32.Google ScholarCross Ref
- Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. Google ScholarDigital Library
- Baral, C., Kraus, S., and Minker, J. 1991. Combining multiple knowledge bases. IEEE Trans. Knowl. Data Eng. 3, 2, 208--220. Google ScholarDigital Library
- Baral, C., Kraus, S., Minker, J., and Subrahmanian, V. 1992. Combining multiple knowledge bases consisting of first order theories. Computational Intell. 8, 1, 45--71.Google ScholarCross Ref
- Benferhat, S., Dubois, D., Kaci, S., and Prade, H. 2003. Possibilistic merging and distance-based fusion of propositional information. Ann. Math. Artif. Intell. 34, 1--3, 217--252. Google ScholarDigital Library
- Booth, R. 2002. Social contraction and belief negotiation. In Proceedings of the 8th International Conference on the Principles of Knowledge Representation and Reasoning. D. Fensel, F. Giunchiglia, D. McGuiness, and M. Williams Eds., Morgan Kaufmann, San Francisco, 375--384.Google Scholar
- Buccafurri, F. and Gottlob, G. 2002. Multiagent compromises, joint fixpoints, and stable models. In Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part I., Springer, 561--585. Google ScholarDigital Library
- Buccafurri, F., Leone, N., and Rullo, P. 2000. Enhancing disjunctive datalog by constraints. IEEE Trans. Knowl. Data Eng. 12, 5, 845--860. Google ScholarDigital Library
- Cabalar, P. and Ferraris, P. 2007. Propositional theories are strongly equivalent to logic programs. Theory Pract. Logic Program. 7, 6, 745--759. Google ScholarDigital Library
- Dalal, M. 1988. Investigations into theory of knowledge base revision. In Proceedings of the AAAI National Conference on Artificial Intelligence. 449--479.Google Scholar
- Dantsin, E., Eiter, T., Gottlob, G., and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Comput. Surv. 33, 3, 374--425. Google ScholarDigital Library
- Delgrande, J., Schaub, T., and Tompits, H. 2003. A framework for compiling preferences in logic programs. Theory Pract. Logic Program. 3, 2, 129--187. Google ScholarDigital Library
- Delgrande, J., Schaub, T., and Tompits, H. 2007. A preference-based framework for updating logic programs. In Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’07). C. Baral, G. Brewka, and J. Schlipf Eds., Lecture Notes in Artificial Intelligence, vol. 4483, Springer-Verlag, 71--83. Google ScholarDigital Library
- Delgrande, J., Schaub, T., Tompits, H., and Woltran, S. 2008. Belief revision of logic programs under answer set semantics. In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR’08). G. Brewka and J. Lang Eds., AAAI Press, 411--421.Google Scholar
- Delgrande, J., Schaub, T., Tompits, H., and Woltran, S. 2009. Merging logic programs under answer set semantics. In Proceedings of the 25th International Conference on Logic Programming (ICLP’09). P. Hill and D. Warren Eds., Lecture Notes in Computer Science, vol. 5649. Springer, 160--174. Google ScholarDigital Library
- Eiter, T. and Gottlob, G. 1992. On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artif. Intell. 57, 2--3, 227--270. Google ScholarDigital Library
- Eiter, T. and Wang, K. 2008. Forgetting in answer set programming. Artif. Intell. 172, 14, 1644--1672. Google ScholarDigital Library
- Eiter, T., Fink, M., Sabbatini, G., and Tompits, H. 2002. On properties of update sequences based on causal rejection. Theory Pract. Logic Program. 2, 6, 711--767. Google ScholarDigital Library
- Eiter, T., Faber, W., Leone, N., and Pfeifer, G. 2003. Computing preferred answer sets by meta-interpretation in answer set programming. Theory Pract. Logic Program. 3, 4--5, 463--498. Google ScholarDigital Library
- Eiter, T., Tompits, H., and Woltran, S. 2005. On solution correspondences in answer set programming. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI’05). 97--102. Google ScholarDigital Library
- Gabbay, D., Rodrigues, O., and Russo, A. 2008. Belief revision in non-classical logics. Rev. Symb. Logic 1, 3, 267--304.Google ScholarCross Ref
- Gärdenfors, P. 1988. Knowledge in Flux: Modelling the Dynamics of Epistemic States. The MIT Press, Cambridge, MA.Google Scholar
- Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., and Thiele, S. A user’s guide to Gringo, clasp, Clingo, and iClingo. http://potassco.sourceforge.net.Google Scholar
- Gebser, M., Pührer, J., Schaub, T., and Tompits, H. 2008. A meta-programming technique for debugging answerset programs. In Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI’08). D. Fox and C. Gomes Eds., AAAI Press, 448--453. Google ScholarDigital Library
- Gebser, M., Kaminski, R., and Schaub, T. 2011. Complex optimization in answer set programming. Theory Pract. Logic Program. 11, 4--5, 821--839.Google Scholar
- Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference and Symposium of Logic Programming (ICLP’88). R. Kowalski and K. Bowen Eds., MIT Press, 1070--1080.Google Scholar
- Hansson, S. O. 1999. A Textbook of Belief Dynamics. Applied Logic Series. Kluwer Academic Publishers.Google Scholar
- Inoue, K. and Sakama, C. 1995. Abductive framework for nonomonotonic theory change. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI’95). Morgan Kaufmann, 204--210. Google ScholarDigital Library
- Inoue, K. and Sakama, C. 1998. Negation as failure in the head. J. Logic Program. 35, 1, 39--78.Google ScholarCross Ref
- Katsuno, H. and Mendelzon, A. 1992. On the difference between updating a knowledge base and revising it. In Belief Revision, P. Gärdenfors Ed., Cambridge University Press, 183--203.Google Scholar
- Konieczny, S. and Pino Pérez, R. 2002. Merging information under constraints: A logical framework. J. Logic Comput. 12, 5, 773--808.Google ScholarCross Ref
- Konieczny, S., Lang, J., and Marquis, P. 2002. Distance-based merging: A general framework and some complexity results. In Proceedings of the 8th International Conference on the Principles of Knowledge Representation and Reasoning. D. Fensel, F. Giunchiglia, D. McGuiness, and M. Williams Eds., Morgan Kaufmann, San Francisco, 97--108.Google Scholar
- Kudo, Y. and Murai, T. 2004. A method of belief base revision for extended logic programs based on state transition diagrams. In Proceedings of the 8th International Conference on Knowledge-Based Intelligent Information and Engineering Systems (KES’04), Part I. M. G. Negoita, R. J. Howlett, and L. C. Jain Eds., Lecture Notes in Computer Science, vol. 3213, Springer, 1079--1084.Google Scholar
- Leite, J. 2003. Evolving Knowledge Bases: Specification and Semantics. IOS Press, Amsterdam.Google Scholar
- Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Logic 7, 3, 499--562. Google ScholarDigital Library
- Liberatore, P. and Schaerf, M. 1998. Arbitration (or how to merge knowledge bases). IEEE Trans. Knowl. Data Eng. 10, 1, 76--90. Google ScholarDigital Library
- Lifschitz, V. and Woo, T. 1992. Answer sets in general nonmonotonic reasoning (preliminary report). In Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR’92). B. Nebel, C. Rich, and W. Swartout Eds., Morgan Kaufmann Publishers, 603--614.Google Scholar
- Lifschitz, V., Pearce, D., and Valverde, A. 2001. Strongly equivalent logic programs. ACM Trans. Comput. Logic 2, 4, 526--541. Google ScholarDigital Library
- Lin, J. and Mendelzon, A. 1999. Knowledge base merging by majority. In Dynamic Worlds: From the Frame Problem to Knowledge Management, R. Pareschi and B. Fronhöfer Eds., Kluwer, 195--218.Google Scholar
- Marek, V. W. and Truszczyński, M. 1998. Revision programming. Theor. Comput. Sci. 190, 241--277. Google ScholarDigital Library
- Meyer, T. 2001. On the semantics of combination operations. J. Appl. Non-Classical Logics 11, 1--2, 59--84.Google ScholarCross Ref
- Nelson, D. 1949. Constructible falsity. J. Symb. Logic 14, 2, 16--26.Google ScholarCross Ref
- Osorio, M. and Cuevas, V. 2007. Updates in answer set programming: An approach based on basic structural properties. Theory Pract. Logic Program. 7, 4, 451--479. Google ScholarDigital Library
- Osorio, M. and Zacarías, F. 2004. On updates of logic programs: A properties-based approach. In Proceedings of the 3rd International Symposium on Foundations of Information and Knowledge Systems (FoIKS’04). Lecture Notes in Computer Science, vol. 2942, Springer, 231--241.Google ScholarCross Ref
- Osorio, M. and Zepeda, C. 2003. Towards the use of semantics contents in ASP for planning and diagnostic in GIS. In Proceedings of the 2nd International Workshop on Answer Set Programming (ASP’03). M. D. Vos and A. Provetti Eds., CEUR Workshop Proceedings, vol. 78, CEUR-WS.org.Google Scholar
- Przymusinski, T. and Turner, H. 1997. Update by means of inference rules. J. Logic Program. 30, 2, 125--143.Google ScholarCross Ref
- Revesz, P. 1993. On the semantics of theory change: Arbitration between old and new information. In Proceedings of the 12th ACM Symposium on Principles of Database Systems. C. Beeri Ed., 71--82. Google ScholarDigital Library
- Sakama, C. and Inoue, K. 2003. An abductive framework for computing knowledge base updates. Theory Pract. Logic Program. 3, 6, 671--713. Google ScholarDigital Library
- Sakama, C. and Inoue, K. 2006. Combining answer sets of nonmonotonic logic programs. In Proceedings of the 6th International Workshop on Computational Logic in Multi-Agent Systems. Lecture Notes in Computer Science, vol. 3900, Springer, 320--339. Google ScholarDigital Library
- Sakama, C. and Inoue, K. 2007. Constructing consensus logic programs. In Proceedings of the 16th International Symposium on Logic-Based Program Synthesis and Transformation (Lopstr’06). Revised Selected Papers, G. Puebla Ed., Lecture Notes in Computer Science, vol. 4407, Springer, 26--42. Google ScholarDigital Library
- Sakama, C. and Inoue, K. 2008. Coordination in answer set programming. ACM Trans. Comput. Logic 9, 2, 1--30. Google ScholarDigital Library
- Satoh, K. 1988. Nonmonotonic reasoning by minimal belief revision. In Proceedings of the International Conference on 5th Generation Computer Systems. 455--462.Google Scholar
- Simons, P., Niemelä, I., and Soininen, T. 2002. Extending and implementing the stable model semantics. Artif. Intell. 138, 1--2, 181--234. Google ScholarDigital Library
- Slota, M. and Leite, J. 2010. On semantic update operators for answer-set programs. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI’10). H. Coelho, R. Studer, and M. Wooldridge Eds., IOS Press, 957--962. Google ScholarDigital Library
- Spohn, W. 1988. Ordinal conditional functions: A dynamic theory of epistemic states. In Causation in Decision, Belief Change, and Statistics, W. Harper and B. Skyrms Eds., Vol. II, Kluwer Academic Publishers, 105--134.Google Scholar
- Turner, H. 2003. Strong equivalence made easy: Nested expressions and weight constraints. Theory Pract. Logic Program. 3, 4--5, 609--622. Google ScholarDigital Library
- Witteveen, C., van der Hoek, W., and de Nivelle, H. 1994. Revision of non-monotonic theories: Some postulates and an application to logic programming. In Proceedings of the 5th European Workshop on Logics in Artificial Intelligence (JELIA’94). Lecture Notes in Artificial Intelligence, vol. 838, Springer, 137--151. Google ScholarDigital Library
- Zacarías, F., Osorio, M., Acosta Guadarrama, J. C., and Dix, J. 2005. Updates in Answer Set Programming based on structural properties. In Proceedings of the 7th International Symposium on Logical Formalizations of Commonsense Reasoning. S. McIlraith, P. Peppas, and M. Thielscher Eds., Fakultät für Informatik, ISSN 1430-211X, 213--219.Google Scholar
- Zhang, Y. and Foo, N. 1997. Towards generalized rule-based updates. In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI’97). Vol. 1, Morgan Kaufmann, 82--88. Google ScholarDigital Library
- Zhang, Y. and Foo, N. 2006. Solving logic program conflict through strong and weak forgetting. Artif. Intell. 170, 739--778. Google ScholarDigital Library
- Zhang, Y. and Foo, N. Y. 1998. Updating logic programs. In Proceedings of the 13th European Conference on Artificial Intelligence (ECAI’98). 403--407.Google Scholar
Index Terms
- A Model-Theoretic Approach to Belief Change in Answer Set Programming
Recommendations
A program-level approach to revising logic programs under the answer set semantics
An approach to the revision of logic programs under the answer set semantics is presented. For programs P and Q, the goal is to determine the answer sets that correspond to the revision of P by Q, denoted P * Q. A fundamental principle of classical (AGM)...
Incorporating Belief Merging into Relevance-Sensitive Belief Structures
PCI '22: Proceedings of the 26th Pan-Hellenic Conference on InformaticsBelief structures have been introduced by Chopra and Parikh as a well-behaved and relevance-sensitive model that is perfectly suitable for representing the beliefs of resource-bounded agents. In this paper, we point out that belief structures are ...
A framework for managing uncertain inputs: An axiomization of rewarding
The success postulate in belief revision ensures that new evidence (input) is always trusted. However, admitting uncertain input has been questioned by many researchers. Darwiche and Pearl argued that strengths of evidence should be introduced to ...
Comments