›› 2009, Vol. 24 ›› Issue (6): 1125-1137.

• Distributed Computing and Systems • Previous Articles     Next Articles

Logic Programs, Compatibility and Forward Chaining Construction

Yi-Song Wang1 (王以松), Member, CCF, Ming-Yi Zhang*,2,3 (张明义), Member, CCF, and Jia-Huai You4 (犹嘉槐)   

  1. 1Department of Computer Science &|Technology, Guizhou University, Guiyang 550025, China
    2School of Computer and Information Science, Southwest University, Chonqing 400715, China
    3Guizhou Academy of Sciences, Guiyang 550001, China
    4Department of Computing Science, University of Alberta, Canada
  • Received:2008-03-05 Revised:2009-08-14 Online:2009-11-05 Published:2009-11-05
  • About author:
    Yi-Song Wang is a member of China Computer Federation. He received the B.S., M.S. and Ph.D. degrees from Guizhou University in 1998, 2004 and 2007, respectively. He has been a post-doctoral researcher in Hong Kong University of Science and Technology, and he is currently a post-doctoral researcher of the Department of Computing Science in the University of Alberta. His main research interests contain artificial intelligence, knowledge representation and reasoning, and logic programming.
    Ming-Yi Zhang is a member of China Computer Federation. He received the B.S. and M.S. degrees in mathematics from Guizhou University in 1965 and 1980, respectively. He is a professor in Applied Mathematics Institute at the Guizhou Academy of Sciences. His research interests include computer science, artificial intelligence, non-classical logics and their applications, non-monotonic reasoning and logic programs.
    Jia-Huai You received his Ph.D. degree in computer science from University of Utah in 1985. He held a visiting position at Rice University during 1985sim1986, and joined the Department of Computing Science at University of Alberta in 1986, and is now a professor. His general research interest is in knowledge representation and reasoning, declarative problem solving, and various techniques for solving constraints. His research involves: logics of non-monotonic reasoning, constraint programming, answer set programming, abduction, and Boolean satisfiability. He is currently on the editorial board of the Journal of Artificial Intelligence Research.
  • Supported by:

    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.

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 {\em compatibility} and the {\it\Lambda} 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 {\em stable submodels}. We further propose the notion of weak auto-compatibility which characterizes the {\em 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.

[1] Frank Van Harmelen, Vladimir Lifschitz, Bruce Porter (eds.). Handbook of Knowledge Representation. Elsevier, 2008.
[2] Baral C. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, 2003.
[3] 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.
[4] Lifschitz V. Answer set programming and plan generation. Artificial Intelligence, 2002, 138(1/2): 39–54.
[5] 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.
[6] Niemel¨a I. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence, 1999, 25(3/4): 241–273.
[7] 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.
[8] Chen W, Zhang M Y, Wu M N. Logic-program-based negotiation mechanism. Journal of Computer Science and Technology, 2009, 24(4): 753–760.
[9] 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.
[10] 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.
[11] Reiter R. A logic for default reasoning. Artificial Intelligence, 1980, 13(1/2): 81–132.
[12] 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.
[13] Zhang M. A new research into default logic. Information and Computation, 1996, 129(2): 73–85.
[14] Dantsin E, Eiter T, Gottlob G, Voronkov A. Complexity and expressive power of logic programming. ACM Computing Surveys, 2001, 33(3): 374–425.
[15] Marek V W, Truszczynski M. Autoepistemic logic. J. ACM, 1991, 38(3): 588–619.
[16] 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.
[17] 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.
[18] 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.
[19] Robert Saxon Milnikel. Skeptical reasoning in FC-normal logic programs is π1 1-complete. Fundamenta Informaticae, 2001, 45(3): 237–252.
[20] 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.
[21] Lloyd J W. Foundations of Logic Programming. 2nd Edition, Springer-Verlag, 1987.
[22] 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.
[23] Martha Sideri Georg Gottlob, Francesco Scarcello. Fixedparameter complexity in AI and nonmonotonic reasoning. Artificial Intelligence, 2002, 138(1/2): 55–86.
[24] 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.
[25] Xu D, Ding D. FC-normal and extended stratified logic program. Science in China (Series F), 2002, 45(4): 259–272.
[26] Garey M R, Johnson D S. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
[27] Kunen K. Signed data dependencies in logic programs. Journal of Logic Programming, 1989, 7(3): 231–245.
[28] Sato T. Completed logic programs and their consistency. Journal of Logic Programming, 1990, 9(1): 33–44.
[29] Allen Van Gelder, Kenneth A Ross, John S Schlipf. The wellfounded semantics for general logic programs. J. ACM, 1991, 38(3): 620–650.

No related articles found!
Full text



No Suggested Reading articles found!

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved