Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-14T15:53:32.912Z Has data issue: false hasContentIssue false
  • English
  • Français

The rise and fall of semantic rule updates based on SE-models*

Published online by Cambridge University Press:  07 August 2013

MARTIN SLOTA  and
JOÃO LEITE
MARTIN SLOTA
Affiliation:
CENTRIA and Departamento de Informática, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal e-mail: jleite@fct.unl.pt
JOÃO LEITE
Affiliation:
CENTRIA and Departamento de Informática, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal e-mail: jleite@fct.unl.pt
Get access Rights & Permissions [Opens in a new window]

Abstract

Logic programs under the stable model semantics, or answer-set programs, provide an expressive rule-based knowledge representation framework, featuring a formal, declarative and well-understood semantics. However, handling the evolution of rule bases is still a largely open problem. The Alchourrón, Gärdenfors and Makinson (AGM) framework for belief change was shown to give inappropriate results when directly applied to logic programs under a non-monotonic semantics such as the stable models. The approaches to address this issue, developed so far, proposed update semantics based on manipulating the syntactic structure of programs and rules.

More recently, AGM revision has been successfully applied to a significantly more expressive semantic characterisation of logic programs based on SE-models. This is an important step, as it changes the focus from the evolution of a syntactic representation of a rule base to the evolution of its semantic content.

In this paper, we borrow results from the area of belief update to tackle the problem of updating (instead of revising) answer-set programs. We prove a representation theorem which makes it possible to constructively define any operator satisfying a set of postulates derived from Katsuno and Mendelzon's postulates for belief update. We define a specific operator based on this theorem, examine its computational complexity and compare the behaviour of this operator with syntactic rule update semantics from the literature. Perhaps surprisingly, we uncover a serious drawback of all rule update operators based on Katsuno and Mendelzon's approach to update and on SE-models.

Keywords

belief updateanswer-set programsrule updateSE-modelssupportliteral inertia
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Issue 6 , November 2014 , pp. 869 - 907
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

This is an extended version of Slota and Leite (2010).

References

Alchourrón, C. E., Gärdenfors, P. and Makinson, D. 1985. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic 50, 2, 510–530.Google Scholar
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.CrossRefGoogle Scholar
Alferes, J. J., Brogi, A., Leite, J. A. and Pereira, L. M. 2003. An evolvable rule-based e-mail agent. In Proc. of the 11th Portuguese Conference Artificial Intelligence (EPIA 2003), Moura-Pires, F. and Abreu, S., Eds. Lecture Notes in Computer Science, vol. 2902. Springer, Beja, Portugal, 394–408.Google Scholar
Alferes, J. J., Leite, J. A., Pereira, L. M., Przymusinska, H. and Przymusinski, T. C. 2000. Dynamic updates of non-monotonic knowledge bases. The Journal of Logic Programming 45, 1–3(September/October), 43–70.Google Scholar
Alferes, J. J. and Pereira, L. M. 1996. Update-programs can update programs. In Non-Monotonic Extensions of Logic Programming (NMELP '96), Selected Papers, Dix, J., Pereira, L. M. and Przymusinski, T. C., Eds. Lecture Notes in Computer Science, vol. 1216. Springer, Bad Honnef, Germany, 110–131.Google Scholar
Apt, K. R., Blair, H. A. and Walker, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, Minker, J., Ed. Morgan Kaufmann, San Francisco, CA, USA. 89–148.Google Scholar
Baral, C. 2003. Knowledge Representation, Reasoning, and Declarative Problem Solving. Cambridge University Press, Cambridge, United Kingdom.Google Scholar
Cabalar, P. and Ferraris, P. 2007. Propositional theories are strongly equivalent to logic programs. Theory and Practice of Logic Programming 7, 6, 745–759.Google Scholar
Delgrande, J. P. 2010. A program-level approach to revising logic programs under the answer set semantics. Theory and Practice of Logic Programming, 26th Intl. Conference on Logic Programming (ICLP'10) Special Issue 10, 4–6 (July), 565–580.Google Scholar
Delgrande, J. P., Schaub, T. and Tompits, H. 2007. A preference-based framework for updating logic programs. In Proc. of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2007), Baral, C., Brewka, G. and Schlipf, J. S., Eds. Lecture Notes in Computer Science, vol. 4483. Springer, Tempe, AZ, USA, 71–83.Google Scholar
Delgrande, J. P., Schaub, T., Tompits, H. and Woltran, S. 2008. Belief revision of logic programs under answer set semantics. In Proc. of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), Brewka, G. and Lang, J., Eds. AAAI Press, Sydney, Australia, 411–421.Google Scholar
Dix, J. 1995a. A classification theory of semantics of normal logic programs: I. Strong properties. Fundamenta Informaticae 22, 3, 227–255.Google Scholar
Dix, J. 1995b. A classification theory of semantics of normal logic programs: II. Weak properties. Fundamenta Informaticae 22, 3, 257–288.Google Scholar
Eiter, T., Fink, M., Sabbatini, G. and Tompits, H. 2002. On properties of update sequences based on causal rejection. Theory and Practice of Logic Programming 2, 6, 721–777.Google Scholar
Eiter, T. and Gottlob, G. 1992. On the complexity of propositional knowledge base revision, updates, and counterfactuals. In Proc. of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 1992). ACM Press, San Diego, CA, USA, 261–273.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of the 5th International Conference and Symposium on Logic Programming (ICLP/SLP 1988), Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, Seattle, Washington, 1070–1080.Google Scholar
Herzig, A. and Rifi, O. 1999. Propositional belief base update and minimal change. Artificial Intelligence 115, 1, 107–138.Google Scholar
Heyting, A. 1930. Die formalen Regeln der intuitionistischen Logik. Sitzungsberichte der Preussischen Akademie der Wissenschaften, 42–56. Reprint in Logik-Texte: Kommentierte Auswahl zur Geschichte der Modernen Logik, Akademie-Verlag, Berlin, Germany, 1986.Google Scholar
Ilic, M., Leite, J. and Slota, M. 2008. Explicit dynamic user profiles for a collaborative filtering recommender system. In Proc. of the 11th Ibero-American Conference on Artificial Intelligence (IBERAMIA'08), Geffner, H., Prada, R., Alexandre, I. M. and David, N., Eds. Vol. LNAI 5290. Springer-Verlag, Berlin, Heidelberg, 352–361.Google Scholar
Katsuno, H. and Mendelzon, A. O. 1991. On the difference between updating a knowledge base and revising it. In Proc. of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR'91), Allen, J. F., Fikes, R., and Sandewall, E., Eds. Morgan Kaufmann Publishers, Cambridge, MA, USA, 387–394.Google Scholar
Katsuno, H. and Mendelzon, A. O. 1992. Propositional knowledge base revision and minimal change. Artificial Intelligence 52, 3, 263–294.Google Scholar
Keller, A. M. and Winslett, M. 1985. On the use of an extended relational model to handle changing incomplete information. IEEE Transactions on Software Engineering 11, 7, 620–633.Google Scholar
Krümpelmann, P. and Kern-Isberner, G. 2010. On belief dynamics of dependency relations for extended logic programs. In Proc. of the 13th International Workshop on Non-Monotonic Reasoning. Toronto, Canada.Google Scholar
Leite, J. A. 2003. Evolving Knowledge Bases: Frontiers of Artificial Intelligence and Applications, xviii + 307 p. Hardcover, Amsterdam, The Netherlands, vol. 81. IOS Press.Google Scholar
Leite, J. A. and Pereira, L. M. 1998. Generalizing updates: From models to programs. In Proc. of the 3rd International Workshop on Logic Programming and Knowledge Representation (LPKR '97), October 17, 1997, Port Jefferson, New York, USA, Dix, J., Pereira, L. M. and Przymusinski, T. C., Eds. Lecture Notes in Computer Science, vol. 1471. Springer, New York, USA, 224–246.Google Scholar
Lifschitz, V., Pearce, D. and Valverde, A. 2001. Strongly equivalent logic programs. ACM Transactions on Computational Logic (TOCL) 2, 4, 526–541.Google Scholar
Łukasiewicz, J. 1941. 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, 82–100.Google Scholar
Meyer, A. R. and Stockmeyer, L. J. 1972. The equivalence problem for regular expressions with squaring requires exponential space. In Proc. of the 13th Annual Symposium on Switching and Automata Theory (SWAT) (October 25–27). IEEE Computer Society, College Park, Maryland, USA, 125–129.Google Scholar
Osorio, M. and Cuevas, V. 2007. Updates in answer set programming: An approach based on basic structural properties. Theory and Practice of Logic Programming 7, 4, 451–479.Google Scholar
Pearce, D. 1997. A new logical characterisation of stable models and answer sets. In Proc. of the 6th Workshop on Non-Monotonic Extensions of Logic Programming (NMELP '96), Dix, J., Pereira, L. M. and Przymusinski, T. C., Eds. Lecture Notes in Computer Science, vol. 1216. Springer, Bad Honnef, Germany, 57–70.CrossRefGoogle Scholar
Saias, J. and Quaresma, P. 2004. A methodology to create legal ontologies in a logic programming based web information retrieval system. Artificial Intelligence and Law 12, 4, 397–417.CrossRefGoogle Scholar
Sakama, C. and Inoue, K. 2003. An abductive framework for computing knowledge base updates. Theory and Practice of Logic Programming 3, 6, 671–713.Google Scholar
efránek, J. 2006. Irrelevant updates and nonmonotonic assumptions. In Proc. of the 10th European Conference on Logics in Artificial Intelligence (JELIA 2006), Fisher, M., van der Hoek, W., Konev, B. and Lisitsa, A., Eds. Lecture Notes in Computer Science, vol. 4160. Springer, Liverpool, UK, 426–438.Google Scholar
efránek, J. 2011. Static and dynamic semantics: Preliminary report. In Mexican International Conference on Artificial Intelligence, Puebla, 36–42.Google Scholar
Siska, J. 2006. Dynamic logic programming and world state evaluation in computer games. In Proc. of the 20th Workshop on Logic Programming, Fink, M., Tompits, H., and Woltran, S., Eds. INFSYS Research Report, vol. 1843-06-02. Technische Universität Wien, Austria, Vienna, Austria, 64–70.Google Scholar
Slota, M. and Leite, J. 2010. On semantic update operators for answer-set programs. In Proc. of the 19th European Conference on Artificial Intelligence (ECAI 2010), Coelho, H., Studer, R. and Wooldridge, M., Eds. Frontiers in Artificial Intelligence and Applications, vol. 215. IOS Press, Lisbon, Portugal, 957–962.Google Scholar
Slota, M. and Leite, J. 2012. Robust equivalence models for semantic updates of answer-set programs. In Proc. of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), Brewka, G., Eiter, T. and McIlraith, S. A., Eds. AAAI Press, Rome, Italy, 158–168.Google Scholar
Slota, M., Leite, J. and Swift, T. 2011. Splitting and updating hybrid knowledge bases. Theory and Practice of Logic Programming, 27th Intl. Conference on Logic Programming (ICLP'11) Special Issue 11, 4–5, 801–819.Google Scholar
Stockmeyer, L. J. 1976. The polynomial-time hierarchy. Theoretical Computer Science 3, 1, 1–22.Google Scholar
Turner, H. 2003. Strong equivalence made easy: Nested expressions and weight constraints. Theory and Practice of Logic Programming 3, 4–5, 609–622.Google Scholar
Winslett, M. 1990. Updating Logical Databases. Cambridge University Press, New York, USA.Google Scholar
Zhang, Y. 2006. Logic program-based updates. ACM Transactions on Computational Logic 7, 3, 421–472.Google Scholar
Zhang, Y. and Foo, N. Y. 2005. A unified framework for representing logic program updates. In Proc. of the 20th National Conference on Artificial Intelligence (AAAI 2005), Veloso, M. M. and Kambhampati, S., Eds. AAAI Press/The MIT Press, Pittsburgh, Pennsylvania, USA, 707–713.Google Scholar