Compactness Properties for Stable Semantics of Logic Programs

• Autorzy: Marek V.W. , Remmel J.B.
• Języki publikacji: EN

Abstrakty

EN

Logic programming with stable logic semantics (SLP) is a logical formalism that assigns to programs, i.e. sets of clauses where we allow both atoms and their negations in the body of clause, a special class of models of the program, called stable models. We show that stable logic semantics does not satisfy the natural analogue of the compactness theorem. However, we show that there are a variety of conditions which will ensure that a program satisfies the analogue of the compactness theorem.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 1-3
• Strony: 211--239
• Opis fizyczny: bibliogr. 40 poz.

Twórcy

autor

Marek V.W.

autor

Remmel J.B.

• Department of Computer Science, University of Kentucky, Lexington, KY 40506-0046, USA,

Bibliografia

• [1] K. Apt. Logic programming, In: J. van Leeuven, ed, Handbook of Theoretical Computer Science, pages 493-574,MIT Press, 1990.
• [2] K. R. Apt, H. A. Blair, Arithmetical Classification of Perfect Models of Stratified Programs, Fundamenta Informaticae 13:1-17, 1990.
• [3] K. Apt, H. Blair, and A.Walker. Towards a Theory of Declarative Knowledge. In J. Minker, ed, Foundations of Deductive Databases and Logic Programming, pages 89-142,Morgan Kaufmann, 1987.
• [4] Y. Babovich and V. Lifschitz. Cmodels, 2002. http://www.cs.utexas.edu/users/tag/cmodels.html.
• [5] P.A. Bonatti. Resolution for Skeptical StableModel Semantics. Journal of Automated Reasoning 27:391-421, 2001.
• [6] D. Cenzer and J. B. Remmel, Index Sets for _01-classes, Annals of Pure and Applied Logic 93:3-61. 1998.
• [7] D. Cenzer and J. B. Remmel, _01-classes in Mathematics, in: Handbook of Recursive Mathematics: Volume 2, Yu. L. Ershov, S.S. Goncharov, A. Nerode, and J.B. Remmel, eds. Studies in Logic and the Foundations of Mathematics, vol. 139, pages 623-822. Elsevier, 1998.
• [8] D. Cenzer, J. B. Remmel, and A. K. C. S. Vanderbilt, Locally Determined Logic Programs, in: Proceedings of the 6th international Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR99), Springer-Verlag, pages 34-49, 1999.
• [9] P. Cholewiński, Stratified default theories, in Proceedings of CSL'94, Lecture Notes in Computer Science, vol. 933, Springer-Verlag, 1995.
• [10] A. Colmerauer, H. Kanoui, R. Pasero and P. Roussel, Un Systeme de Communication Homme-machine en Francais, University of Marseille, 1973
• [11] P.M. Dung and K. Kanchanasut. A Fixpoint Approach to Declarative Semantics of Logic Programs, In: E.L. Lusk and R.A. Overbeek eds, Logic Programming, Proceedings of North American Conference, pages 604-625, 1989
• [12] A. Ferry, A topological characterization of the stable and minimal model classes of propositional logic programs, Annals of Mathematics and Artificial Intelligence 15:325-355, 1995.
• [13] M. Gelfond and V. Lifschitz. The Stable Semantics for Logic Programs. In Proceedings of the 5th International Symposium on Logic Programming, pages 1070-1080, 1988. MIT Press, 1988.
• [14] M. Gelfond. A personal communication.
• [15] K. Gödel. Űber formal unentscheibare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte Math. Phys. 38:173-198, 1931.
• [16] A. Grzegorczyk. Some classes of recursive functions. Rozprawy Matematyczne (Dissertationes Mathematicae) 4, 1953.
• [17] A. Grzegorczyk An Outline of Mathematical Logic, Reidel, Dordrecht, and PWN, Warszawa, 1974.
• [18] A. Horn, On sentences that are true of direct unions of algebras. Journal of Symbolic Logic, 16:14-21, 1951.
• [19] C.G. Jockusch, A. Lewis, and J. B. Remmel. _01 Classes and Rado's Selection Principle. Journal of Symbolic Logic, 56:684-693, 1991.
• [20] C.G. Jockusch and R.I. Soare. _01 Classes and Degrees of Theories. Transactions of American Mathematical Society, 173:33-56, 1972.
• [21] S.C. Kleene. General recursive functions of natural numbers. Mathematische Annalen, 112:727-742, 1936.
• [22] R.A. Kowalski and D. Kuehner. Linear Resolution with Selection Function. Artificial Intelligence, 2:227-260, 1970.
• [23] V. Lifschitz and H. Turner, Splitting a logic program, in: Proceedings of the Eleventh International Conference on Logic Programming, P. Van Hentenryck, ed., pages 23-37, 1994.
• [24] J. Lloyd, Foundations of Logic Programming, Springer-Verlag, 1989.
• [25] J.A. Makowsky: Why Horn FormulasMatter in Computer Science: Initial Structures and Generic Examples. Journal of Computer and System Sciences 34:266-292, 1987.
• [26] W. Marek, A. Nerode, and J.B. Remmel. Nonmonotonic Rule Systems I. Annals of Mathematics and Artificial Intelligence, 1:241-273, 1990.
• [27] W. Marek, A. Nerode, and J.B. Remmel. Nonmonotonic Rule Systems II. Annals of Mathematics and Artificial Intelligence, 5:229-264, 1992.
• [28] W. Marek, A. Nerode, and J.B. Remmel. A Context for Belief Revision: Normal Logic Programs (Extended Abstract) Proceedings, Workshop on Defeasible Reasoning and Constraint Solving, International Logic Programming Symposium, San Diego, CA., 1991.
• [29] W. Marek, A. Nerode, and J.B. Remmel. How Complicated is the Set of Stable Models of a Logic Program? Annals of Pure and Applied Logic, 56:119-136, 1992.
• [30] W. Marek, A. Nerode, and J. B. Remmel, The stable models of predicate logic programs. Journal of Logic Programming 21:129-154, 1994.
• [31] W. Marek, A. Nerode, and J. B. Remmel, Context for belief revision: Forward chaining-normal nonmonotonic rule systems, Annals of Pure and Applied Logic 67:269-324, 1994.
• [32] V.W. Marek and J. B. Remmel, Stable models and guarded- resolution rules, forthcoming.
• [33] W. Marek and M. Truszczyński, Stable semantics for logic programs and default theories, Proceedings of the North American Conference on Logic Programming,MIT Press, 243-256, 1989.
• [34] R. Reiter. A Logic for Default Reasoning. Artificial Intelligence, 13:81-132, 1980.
• [35] P. Simons, I. Niemelä, and T. Soininen. Extending and implementing the stable model semantics. Artificial Intelligence, 138:181-234, 2002.
• [36] H.J. Rogers. Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
• [37] D. Scott. completeness and axiomatizability in many-valued logics. Proceedings of Symposia in Pure Mathematics 25:431-435. AMS, 1974.
• [38] D. Scott. Domains for denotational semantics. In Proceedings of ICALP-82, pages 577-613, Springer Verlag, 1982.
• [39] R.M. Smullyan. Theory of formal systems. Annals of mathematics studies, no 47, 1961
• [40] A. Van Gelder, K.A. Ross, and J.S. Schlipf. Unfounded sets and well-founded semantics for general logic programs. Journal of the ACM, 38:620-650, 1991.