Predicate Introduction for Logics with a Fixpoint Semantics. Part I: Logic Programming

• Autorzy: Vennekens J. , Wittocx J. , Mariën M. , Denecker M.
• Języki publikacji: EN

Abstrakty

EN

We study the transformation of "predicate introduction" in non-monotonic logics. By this, we mean the act of replacing a complex formula by a newly defined predicate. From a knowledge representation perspective, such transformations can be used to eliminate redundancy or to simplify a theory. From a more practical point of view, they can also be used to transform a theory into a normal form imposed by certain inference programs or theorems. In this paper, we study predicate introduction in the algebraic framework of "approximation theory"; this is a fixpoint theory for non-monotone operators that generalizes all main semantics of various non-monotonic logics, including logic programming, default logic and autoepistemic logic. We prove an abstract, algebraic equivalence result in this framework. This can then be used to show that, in logic programming, certain transformations are equivalence preserving under, among others, both the stable and well-founded semantics. Based on this result, we develop a general method of eliminating universal quantifiers in the bodies of rules. Our work is, however, also applicable beyond logic programming. In a companion paper, we demonstrate this, by using the same algebraic results to derive a transformation which reduces the nesting depth of the modal operator K in autoepistemic logic.

Słowa kluczowe

EN

Logic Programming (LP); approximation; fixpoint extension

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 1-2
• Strony: 187--208
• Opis fizyczny: bibliogr. 20 poz.

Twórcy

autor

Vennekens J.

autor

Wittocx J.

autor

Mariën M.

autor

Denecker M.

• Department of Computer Science, K.U. Leuven, Celestijnlaan 200A, B-3001 Leuven, Belgium,

Bibliografia

• [1] Balduccini, M., Gelfond, M.: Diagnostic reasoning with A-Prolog., Theory and Practice of Logic Programming (TPLP), 3(4-5), 2003, 425-461.
• [2] Belnap, N. D.: A useful four-valued logic, in: Modern uses of multiple-valued logic, Reidel, Dordrecht, NL, 1977, 5-37.
• [3] Clark, K. L.: Negation as failure, in: Logic and Databases (H. Gallaire, J. Minker, Eds.), Plenum Press, 1978, 293-322.
• [4] Denecker, M., Marek, V., Truszczyński, M.: Approximating operators, stable operators, well-founded fixpoints and applications in nonmonotonic reasoning, in: Logic-based Artificial Intelligence (J. Minker, Ed.), chapter 6, Kluwer Academic Publishers, 2000, 127-144.
• [5] Denecker,M.,Marek, V., Truszczyński,M.: Uniform semantic treatment of default and autoepistemic logics, Artificial Intelligence, 143(1), 2003, 79-122.
• [6] Denecker, M., Ternovska, E.: A Logic of Non-Monotone Inductive Definitions and its Modularity Properties, Seventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'7) (V. Lifschitz, I. Niemelä, Eds.), 2004.
• [7] Dix, J.: A Classification Theory of Semantics of Normal Logic Programs: II.Weak Properties., Fundamenta Informaticae, 22(3), 1995, 257-288.
• [8] Dix, J., Müller,M.: Partial Evaluation and Relevance for Approximations of Stable Semantics., ISMIS (Z.W. Ras, M. Zemankova, Eds.), 869, Springer, 1994, ISBN 3-540-58495-1.
• [9] Fitting, M.: A Kripke-Kleene Semantics for Logic Programs, Journal of Logic Programming, 2(4), 1985, 295-312.
• [10] Fitting, M.: Fixpoint semantics for logic programming - a survey, Theoretical Computer Science, 278, 2002, 25-51.
• [11] Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming, International Joint Conference and Symposium on Logic Programming (JICSLP'88),MIT Press, 1988.
• [12] Gelfond,M., Przymusinska, H.: Towards a Theory of Elaboration Tolerance: Logic Programming Approach, Journal on Software and Knowledge Engineering, 6(1), 1996, 89-112.
• [13] Lloyd, J., Topor, R.: Making Prolog more expressive, Journal of Logic Programming, 1(3), 1984, 225-240.
• [14] Pawlak, Z.: Rough Sets: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Norwell, MA, USA, 1992, ISBN 0792314727.
• [15] Schrijvers, T., Serebrenik, A.: Improving Prolog Programs: Refactoring for Prolog, Logic Programming, 20th International Conference, ICLP 2004, Proceedings, 3132, 2004.
• [16] Truszczyński, M.: Strong and uniform equivalence of nonmonotonic theories - an algebraic approach, Principles of Knowledge Representation and Reasoning, Proceedings of the Tenth International Conference (KR2006), 2006.
• [17] Van Gelder, A.: The Alternating Fixpoint of Logic Programswith Negation, Journal of Computer and System Sciences, 47(1), 1993, 185-221.
• [18] Vennekens, J., Gilis, D., Denecker, M.: Splitting an operator: Algebraic modularity results for logics with fixpoint semantics, ACM Transactions on computational logic (TOCL), 7(4), 2006, 765-797.
• [19] Vennekens, J., Wittocx, J., Mari¨en, M., Denecker, M., Bruynooghe, M.: Predicate Introduction for Logics with Fixpoint Semantics. Part II: Autoepistemic Logic, Fundamenta Informaticae.
• [20] Wittocx, J., Vennekens, J., Mari¨en, M., Denecker, M., Bruynooghe,M.: Predicate Introduction under Stable and Well-founded Semantics, Proceedings of the 22nd International Conference on Logic Programming (ICLP'06) (S. Etalle, M. Truszczyński, Eds.), 4079, Springer, 2006.