Abstract
Logic programming under the stable model semantics is proposed as a non-monotonic language for knowledge representation and reasoning in artificial intelligence. In this paper, we explore and extend the notion of compatibility and the Λ operator, which were first proposed by Zhang to characterize default theories. First, we present a new characterization of stable models of a logic program and show that an extended notion of compatibility can characterize stable submodels. We further propose the notion of weak auto-compatibility which characterizes the Normal Forward Chaining Construction proposed by Marek, Nerode and Remmel. Previously, this construction was only known to construct the stable models of FC-normal logic programs, which turn out to be a proper subclass of weakly auto-compatible logic programs. We investigate the properties and complexity issues for weakly auto-compatible logic programs and compare them with some subclasses of logic programs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Frank Van Harmelen, Vladimir Lifschitz, Bruce Porter (eds.). Handbook of Knowledge Representation. Elsevier, 2008.
Baral C. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, 2003.
Gelfond M, Lifschitz V. The stable model semantics for logic programming. In Proc. the Fifth International Conference and Symposium on Logic Programming, Seattle, Washington, Aug. 15–19, 1988, pp.1070–1080.
Lifschitz V. Answer set programming and plan generation. Artificial Intelligence, 2002, 138(1/2): 39–54.
Marek V W, Truszczynski M. Stable models and an alternative logic programming paradigm. The Logic Programming Paradigm: A 25-Year Perspective. Apt K R, Marek V W, Truszczynski M, Warren D S (eds.), Springer-Verlag, 1999, pp.375–398.
Niemelä I. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence, 1999, 25(3/4): 241–273.
Zhao X S, Shen Y P. Comparison of semantics of disjunctive logic programs based on model-equivalent reduction. Journal of Computer Science and Technology, 2007,22(4): 562–568.
Chen W, Zhang M Y, Wu M N. Logic-program-based negotiation mechanism. Journal of Computer Science and Technology, 2009, 24(4): 753–760.
Lifschitz V. Twelve definitions of a stable model. In Proc. the 24th Int. Conf. Logic Programming, LNCS 5366, Udine, Italy, Dec. 9–13, 2008, pp.37–51.
Marek V W, Nerode A, Remmel J B. Logic programs, wellordering, and forward chaining. Annals of Pure and Applied Logic, 1999, 96(1-3): 231–276.
Reiter R. A logic for default reasoning. Artificial Intelligence, 1980, 13(1/2): 81–132.
Zhang M. A characterization of extension of general default theories. In Proc. the Ninth Canadian Conference on Artificial Intelligence, Vancouver, Canada, 1992, pp.134–139.
Zhang M. A new research into default logic. Information and Computation, 1996, 129(2): 73–85.
Dantsin E, Eiter T, Gottlob G, Voronkov A. Complexity and expressive power of logic programming. ACM Computing Surveys, 2001, 33(3): 374–425.
Marek V W, Truszczynski M. Autoepistemic logic. J. ACM, 1991, 38(3): 588–619.
Apt K R, Blair H A, Walker A. Towards a theory of declarative knowledge. Foundations of Deductive Databases and Logic Programming, Minker J (ed.), Morgan Kaufmann, Los Altos, 1988, pp.293–322.
Lin F, Zhao X. On odd and even cycles in normal logic programs. In Proc. the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, San Jose, USA, July 25-29, 2004, pp.80–85.
Papadimitriou C H, Yannakakis M. Tie-breaking semantics and structural totality. In Proc. 11th ACM Conference on Principles of Database Systems (PODS 1992), San Diego, USA, June 2–4, 1992, pp.16–22.
Robert Saxon Milnikel. Skeptical reasoning in FC-normal logic programs is π 11 -complete. Fundamenta Informaticae, 2001, 45(3): 237–252.
Wang Y, Zhang M, Shen Y. Consistency property of finite FC-normal logic programs. Journal of Computer Science and Technology, 2007, 22(4): 554–561.
Lloyd J W. Foundations of Logic Programming. 2nd Edition, Springer-Verlag, 1987.
Zhang M, Zhang Y, Wang Y. On compatibility and forward chaining normality. In The Eleventh International Workshop on Non-Monotonic Reasoning, Lake District, UK, May 30–June 1, 2006, pp.163–171.
Martha Sideri Georg Gottlob, Francesco Scarcello. Fixedparameter complexity in AI and nonmonotonic reasoning. Artificial Intelligence, 2002, 138(1/2): 55–86.
William F Dowling, Jean H Gallier. Linear-time algorithms for testing the satisfiability of propositional horn formulae. Journal of Logic Programming, 1984, 1(3): 267–284.
Xu D, Ding D. FC-normal and extended stratified logic program. Science in China (Series F), 2002, 45(4): 259–272.
Garey M R, Johnson D S. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
Kunen K. Signed data dependencies in logic programs. Journal of Logic Programming, 1989, 7(3): 231–245.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 60963009 and 90718009. Yi-Song Wang was also partially supported by Scientific Research Fund for Talents Recruiting of Guizhou University under Grant No. (2007)042, the Science and Technology Foundation of Guizhou Province under Grant No. [2008]2119 and the Natural Science Foundation of Educational Commission of Guizhou Province under Grant No. (2008)011.
Rights and permissions
About this article
Cite this article
Wang, YS., Zhang, MY. & You, JH. Logic Programs, Compatibility and Forward Chaining Construction. J. Comput. Sci. Technol. 24, 1125–1137 (2009). https://doi.org/10.1007/s11390-009-9285-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11390-009-9285-5