Joost Vennekens
Abstract
It is well known that, under certain conditions, it is possible to split logic programs under stable model semantics, that is, to divide such a program into a number of different “levels”, such that the models of the entire program can be constructed by incrementally constructing models for each level. Similar results exist for other nonmonotonic formalisms, such as auto-epistemic logic and default logic. In this work, we present a general, algebraic splitting theory for logics with a fixpoint semantics. Together with the framework of approximation theory, a general fixpoint theory for arbitrary operators, this gives us a uniform and powerful way of deriving splitting results for each logic with a fixpoint semantics. We demonstrate the usefulness of these results, by generalizing existing results for logic programming, auto-epistemic logic and default logic.
- Apt, K., Blair, H., and Walker, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, J. Minker, Ed. Morgan-Kaufmann, Los Alamitos, CA.]] Google Scholar
- Baral, C. and Subrahmanian, V. 1991. Duality between alternative semantics of logic programs and nonmonotonic formalisms. In Proceedings of the International Workshop on Logic Programming and Nonmonotonic Reasoning (Washington DC), A. Nerode, W. Marek, and V. Subrahmanian, Eds. MIT Press, Cambridge, MA, 69--86.]]Google Scholar
- Denecker, M. 2000. Extending classical logic with inductive definitions. In Proceedings of the 1st International Conference on Computational Logic (CL2000) (London, UK), J. Lloyd et al., Ed. Lecture Notes in Artificial Intelligence, vol. 1861. Springer-Verlag, New York, 703--717.]] Google Scholar
- Denecker, M., Marek, V., and Truszczynski, M. 1998. Fixpoint 3-valued semantics for autoepistemic logic. In Proceedings of the 15th National Conference on Artificial Intelligence. MIT Press/AAAI-Press, 840--845.]] Google Scholar
- Denecker, M., Marek, V., and Truszczynski, M. 2000. Approximating operators, stable operators, well-founded fixpoints and applications in non-monotonic reasoning. In Logic-Based Artificial Intelligence. The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, MA, 127--144.]] Google Scholar
- Denecker, M., Marek, V., and Truszczynski, M. 2003. Uniform semantic treatment of default and autoepistemic logics. Artif. Intel. 143, 1 (Jan.), 79--122.]] Google Scholar
- Denecker, M. and Ternovska, E. 2004. A logic of non-monotone inductive definitions and its modularity properties. In LPNMR. 47--60.]]Google Scholar
- Dix, J. 1995. A classification theory of semantics normal logic programs: II. weak properties. Fund. Inf. XXII, 257--288.]]Google Scholar
- Eiter, T., Gottlob, G., and Mannila, H. 1997. Disjunctive datalog. ACM Trans. Database Systems (TODS) 22, 364--418.]] Google Scholar
- Erdoğan, S. and Lifschitz, V. 2004. Definitions in answer set programming. In Proc. Logic Programming and Non Monotonic Reasoning, LPNMR'04. Lecture Notes in Artificial Itelligence, vol. 2923. Springer-Verlag, New York, 185--197.]]Google Scholar
- Etherington, D. 1988. Reasoning with incomplete information. Research notes in Artificial Intelligence. Morgan-Kaufmann, Reading, MA.]] Google Scholar
- Fitting, M. 1985. A Kripke-Kleene semantics for logic programs. J. Logic Prog. 2, 4, 295--312.]]Google Scholar
- Fitting, M. 1991. Bilattices and the semantics of logic programming. J. Logic Prog. 11, 91--116.]] Google Scholar
- Gelfond, M. 1987. On stratified autoepistemic theories. In Proceedings of AAAI87. Morgan-Kaufman, Los Altos, CA, 207--211.]]Google Scholar
- Gelfond, M. and Przymusinska, H. 1992. On consistency and completeness of autoepistemic theories. Fund. Inf. 16, 1, 59--92.]] Google Scholar
- Ginsberg, M. 1988. Multivalued logics: A uniform approach to reasoning in artificial intelligence. Computat. Intell. 4, 265--316.]]Google Scholar
- Konolige, K. 1987. On the relation between default and autoepistemic logic. In Readings in Nonmonotonic Reasoning, M. L. Ginsberg, Ed. Morgan-Kaufmann, Los Altos, CA, 195--226.]] Google Scholar
- Leone, N., Rullo, P., and Scarcello, F. 1995. Declarative and fixpoints characterizations of disjunctive stable models. In Proceedings of the International Logic Programming Symposium (ILPS '95). MIT Press, Cambridge, MA, 399--413.]]Google Scholar
- Lifschitz, V. and Turner, H. 1994. Splitting a logic program. In Proceedings of the 11th International Conference on Logic Programming. MIT Press, Cambridge, MA, 23--37.]] Google Scholar
- Lloyd, J. 1987. Foundations of Logic Programming. Springer-Verlag, New York.]] Google Scholar
- Meyer, J.-J.Ch. and van der Hoek, W. 1995. Epistemic Logic for Computer Science and Artificial Intelligence. Cambridge University Press.]] Google Scholar
- Moore, R. C. 1984. Possible-world semantics for autoepistemic logic. In Proceedings of the Non-Monotonic Reasoning Workshop. AAAI, Mohonk, NY, 344--354.]]Google Scholar
- Pelov, N. and Truszczynski, M. 2004. Semantics of disjunctive programs with monotone aggregates - an operator-based approach. In Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR 2004), Whistler, B.C., Canada, June 6--8, J. P. Delgrande and T. Schaub, Eds. 327--334.]]Google Scholar
- Niemelä, I. and Rintanen, J. 1994. On the impact of stratification on the complexity of nonmonotonic reasoning. J. Appl. Non-Classical Log. 4, 2.]]Google Scholar
- Przymusinski, T. 1998. Every logic program has a natural stratification and an iterated least fixed point model. In Proceedings of the 8th Symposium on Principles of Database Systems (PODS). 11--21.]] Google Scholar
- Reiter, R. 1980. A logic for default reasoning. Artif. Intell. 13, 1--2, 81--132.]]Google Scholar
- Tarski, A. 1955. Lattice-theoretic fixpoint theorem and its applications. Pac. J. Math. 5, 285--309.]]Google Scholar
- Turner, H. 1996. Splitting a default theory. In Proceedings of the 13th National Conference on Artificial Intelligence and the 8th Innovative Applications of Artificial Intelligence Conference. AAAI Press, 645--651.]]Google Scholar
- Van Gelder, A., Ross, K., and Schlipf, J. 1991. The well-founded semantics for general logic programs. J. ACM 38, 3, 620--650.]] Google Scholar
- Vennekens, J., Gilis, D., and Denecker, M. 2004a. Splitting an operator: An algebraic modularity result and its application to auto-epistemic logic. In Proceedings of International Workshop on Non-Monotonic Reasoning, Whistler, B.C., Canada.]]Google Scholar
- Vennekens, J., Gilis, D., and Denecker, M. 2004b. Splitting an operator: An algebraic modularity result and its applications to logic programming. In Proceedings of the 20th International Conference on Logic Programming (ICLP 2004). Lecture Notes in Computer Science, vol. 3132. Springer-Verlag, New York, 195--209.]]Google Scholar
- Verbaeten, S., Denecker, M., and Schreye, D. D. 2000. Compositionality of normal open logic programs. J. Logic Prog. 41, 151--183.]]Google Scholar
Index Terms
- Splitting an operator: Algebraic modularity results for logics with fixpoint semantics
Recommendations
Meta-logic programming for the extensions of default theories
CI '07: Proceedings of the Third IASTED International Conference on Computational IntelligenceLogic programming is given for the extensions of default theories such that the consequent of a default is a clause and the prerequisite is the conjunction of clauses. The default theories include both the classical negation and the not symbol. Meta-...
Disjunction and modular goal-directed proof search
This article explores goal-directed proof search in first-order multimodal logic. I focus on a family of modal logics which offer the expressive power to specify modular goals and local assumptions. A modular goal must be proved from designated ...
Ordering default theories and nonmonotonic logic programs
First-order theories are ordered under logical entailment based on the amount of information derived from theories. In default logic, on the other hand, a theory contains default information as well as definite information. To order default theories, ...
Comments