Abstract
An extension of resolution for skeptical stable model semantics is introduced. Unlike previous approaches, our calculus is not derived from credulous inference and enjoys a number of properties that are not satisfied by current nonmonotonic reasoning systems. Skeptical resolution is top down, in general, and goal directed on call-consistent programs. It does not need the given program to be instantiated before reasoning. It may compute nonground answer substitutions efficiently. It is compatible with different implementations of negation as failure. Some inferences, which depend on nonground negative goals, can be drawn without resorting to negation-as-failure; as a consequence, many goals that flounder in the standard setting have a successful skeptical derivation. The paper contains a preliminary study of some interesting derivation strategies and a sketch of a prototype implementation of the calculus.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Apt, K. R., Bol, R.W., and Klop, J. W.: On the safe termination of Prolog programs, in G. Levi and M. Martelli (eds.), Proc. 6th ICLP, Mit Press, 1989, pp. 353–368.
Bell, C., Nerode, A., Ng, R., and Subrahmanian, V. S.: Implementing stable semantics by linear programming, in Proc. LPNMR'93, MIT Press, 1993, pp. 23–42.
Bonatti, P.: Autoepistemic logics as a unifying framework for the semantics of logic programs, J. Logic Programming 22(2) (1995), 91–149.
Bonatti, P. A.: Sequent calculi for default and autoepistemic logics, in Proc. TABLEAUX'96, LNAI 1071, Springer-Verlag, Berlin, 1996, pp. 127–142.
Bonatti, P. A.: Resolution for skeptical stable semantics, in [11].
Bonatti, P. A. and Olivetti, N.: A sequent calculus for skeptical default logic, in Proc. TABLEAUX'97, LNAI 1227, Springer-Verlag, 1997, pp. 107–121.
Bonatti, P. A. and Olivetti, N.: A sequent calculus for circumscription, in Proc. CSL'97, LNCS 1414, Springer-Verlag, 1998, pp. 98–114.
Chen, W. and Warren, D. S.: Tabled evaluation with delaying for general logic programs, JACM 43(1) (1996), 20–74.
Chen, W. and Warren, D. S.: Computation of stable models and its integration with logical query processing, IEEE TKDE 8(5) (1996), 742–757.
Comon, H.: Disunification: A survey, in J. L. Lassez and G. Plotkin (eds.), Computational Logic-Essays in Honor of Alan Robinson, MIT Press, 1991.
Dix, J., Furbach, U., and Nerode, A.: Logic Programming and Nonmonotonic Reasoning: 4 th International Conference, LPNMR'97, LNAI 1265, Springer-Verlag, Berlin, 1997.
Dung, P. M.: On the relation between stable and well-founded semantics of logic programs, Theoret. Comput. Sci. 105 (1992), pp. 7–25.
Gelfond, M. and Lifschitz, V.: The stable model semantics for logic programming, in Proc. 5 th ICLP, MIT Press, 1988, pp. 1070–1080.
Gottlob, G., Marcus, S., Nerode, A., Salzer, G., and Subrahmanian, V. S.: A non-ground realization of the stable and well-founded semantics, TCS 166 (1996), 221–262.
Lifschitz, V. and Turner, H.: Splitting a logic program, in Proc. ICLP'94, MIT Press, 1994, pp. 23–37.
Lloyd, J. W.: Foundations of Logic Programming, Springer-Verlag, 1984.
Marek,W. and Truszczy´nski, M.: Computing intersection of autoepistemic expansions, in Proc. LPNMR'91, MIT Press, 1991, pp. 37–52.
Niemela, I. and Simons, P.: Efficient implementation of the well-founded and stable model semantics, in Proc. JICSLP 96, MIT Press, 1996, pp. 289–303.
Niemelä, I. and Simons, P.: SMODELS-an implementation of the stable model and wellfounded semantics for normal LP, in [11].
Schaub, T. and Thielscher, M.: Skeptical query answering in constrained default logic, in Proc. Conference on Formal and Applied Practical Reasoning (FAPR'96), 1996, pp. 567–581.
Schlipf, J. S.: The expressive powers of the logic programming semantics, J. Comput. System Sci. 51 (1995), 64–86.
Subrahmanian, V. S., Nau, D. and Vago, C.: WFS+Branch and bound=Stable models, IEEE TKDE 7(3) (1995), 362–377.
Van Gelder, A., Ross, K. A. and Schlipf, J. S.: The well-founded semantics for general logic programs, J. ACM 38(3) (1991), 620–650.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bonatti, P.A. Resolution for Skeptical Stable Model Semantics. Journal of Automated Reasoning 27, 391–421 (2001). https://doi.org/10.1023/A:1011960831261
Issue Date:
DOI: https://doi.org/10.1023/A:1011960831261