Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 22 Issue 4
July  2007
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Yi-Song Wang, Ming-Yi Zhang, Yu-Ping Shen. Consistency Property of Finite FC-Normal Logic Programs[J]. Journal of Computer Science and Technology, 2007, 22(4): 554-561.
Citation: Yi-Song Wang, Ming-Yi Zhang, Yu-Ping Shen. Consistency Property of Finite FC-Normal Logic Programs[J]. Journal of Computer Science and Technology, 2007, 22(4): 554-561.
shu

Consistency Property of Finite FC-Normal Logic Programs

  • 1College of Computer Science and Technology, Guizhou University, Guiyang 550025, China2Guizhou Academy of Sciences, Guiyang 550001, China3Institute of Logic and Cognition, Sun Yat-Sen University, Guangzhou 510275, China

More Information
  • Received Date: September 05, 2006
  • Revised Date: March 18, 2007
  • Published Date: July 14, 2007
    Abstract
  • Marek's forward-chaining construction is one of the importanttechniques for investigating the non-monotonic reasoning. Byintroduction of consistency property over a logic program, theyproposed a class of logic programs, FC-normal programs, each ofwhich has at least one stable model. However, it is not clear how tochoose one appropriate consistency property for deciding whether ornot a logic program is FC-normal. In this paper, we firstly discoverthat, for any finite logic program Π, there exists the leastconsistency property LCon(Π) over Π, which justdepends on Π itself, such that, Π is FC-normal if andonly if Π is FC-normal with respect to (w.r.t.) \itLCon(Π). Actually, in order to determine the FC-normality of alogic program, it is sufficient to check the monotonic closed sets inLCon(Π) for all non-monotonic rules, that is \itLFC(Π). Secondly, we present an algorithm for computing \itLFC(Π). Finally, we reveal that the brave reasoning task andcautious reasoning task for FC-normal logic programs are of the samedifficulty as that of normal logic programs.
    • FullText(HTML)
    • References (16)
  • [1]
    Michael Gelfond, Vladimir Lifschitz. The stable model semantics for logic programming. In -\em Proc. Fifth International Conference and Symposium on Logic Programming}, Seattle, Washington, 1988, pp.1070∼1080.
    [2]
    Marek V W, Truszczynski M. Stable models and an alternative logic programming paradigm. In -\em Proc. The Logic Programming Paradigm: A 25-Year Perspective}, Apt K R, Marek V W, Truszczynski M, Warren D S (eds.), Berlin: Springer-Verlag, Germany, 1999, pp.375∼398.
    [3]
    Vladimir Lifschitz. Answer set programming and plan generation. -\em Artif. Intell.}, 2002, 138(1-2): 39∼54.
    [4]
    Chitta Baral. -Knowledge Representation, Reasoning and Declarative Problem Solving}. Cambridge University Press, 2003.
    [5]
    Marek V W, Nerode A, Remmel J B. Logic programs, well-ordering, and forward chaining. -\em Annals of Pure and Applied Logic}, 1999, 96: 231∼276.
    [6]
    Lloyd J W. -Foundations of Logic Programming}. 2nd Edition, Springer-Verlag, 1987.
    [7]
    Daoyun Xu, Decheng Ding. Fc-normal and extended stratified logic program. -\em Science in China (Series F)}, 2002, 45(4): 259∼272.
    [8]
    Evgeny Dantsin, Thomas Eiter, Georg Gottlob \it et al. \rm Complexity and expressive power of logic programming. -\em ACM Computing Surveys}, 2001, 33(3): 374∼425.
    [9]
    Gottlob G, Scarcello F, Sideri M. Fixed-parameter complexity in AI and nonmonotonic reasoning. -\em Artificial Intelligence}, 2002, 138(1-2): 55∼86.
    [10]
    V Wiktor Marek, Miroslaw Truszczynski. Autoepistemic logic. -\em J. ACM}, 1991, 38(3): 588∼619.
    [11]
    Fangzhen Lin, Xishun Zhao. On odd and even cycles in normal logic programs. In -\em Proc. the 19th National Conference on Artificial Intelligence (AAAI-2004)}, Menlo Park, CA., AAAI Press, 2004, pp.80∼85.
    [12]
    Henry A Kautz, Bart Selman. Hard problems for simple default logics. -\em Artif. Intell.}, 1991, 49(1-3): 243∼279.
    [13]
    Mingyi Zhang, Ying Zhang, Yisong Wang. On compatibility and forward chaining normality. In -\em Proc. NMR06 Workshop}, Lake District, UK, 2006, pp.163∼171.
    [14]
    Zhang Mingyi. A characterization of extension of general default theories. In -\em Proc. 9th Cannadian Conference on Artificial Intelligence}, Vancouver, BC, Canada, 1992, pp.134∼139.
    [15]
    Zheng Chuanjin. Extensions and strong compatible subsets of defaults. -\it Chinese Journal of Computers}, 1994, 17(2): 142∼146.
    [16]
    Zhang Mingyi. A new research into default logic. -\em Information and Computation}, Elsevier, 1996, 129(2): 73∼85.
    • Relative Articles

  • Related Articles

    [1]ZHANG Yiying, ZHU Xiaoyan, ZHANG Bo. A New Speaker Verification Method with Global Speaker Model and Likelihood Score Normalization[J]. Journal of Computer Science and Technology, 2000, 15(2): 184-193.
    [2]CHEN Yangjun. On the Arc Consistency Problem[J]. Journal of Computer Science and Technology, 1999, 14(4): 298-308.
    [3]Wang Shitong. Normalized Exponential Neural Networks[J]. Journal of Computer Science and Technology, 1998, 13(4): 375-383.
    [4]Wang Kewen, Chen Huowang, Wu Quanyuan. The Least Fixpoint Transformation for Disjunctive Logic Programs[J]. Journal of Computer Science and Technology, 1998, 13(3): 193-201.
    [5]Hu Weiwu, Shi Weisong, Tang Zhimin. A Framework of Memory Consistency Models[J]. Journal of Computer Science and Technology, 1998, 13(2): 110-124.
    [6]Li Tianzhu, Xiao Jitian, Sun Zhaohao, Bian Xiaofan. Normalization of Class Hierarchy in Databases[J]. Journal of Computer Science and Technology, 1996, 11(4): 356-364.
    [7]Yang Li. Towards Restructuring and Normalization of Types in Databases[J]. Journal of Computer Science and Technology, 1995, 10(1): 65-73.
    [8]Wang Xianchang, Chen Huowang, Zhao Qinping. On the Relationship Between TMS and Logic Programs[J]. Journal of Computer Science and Technology, 1994, 9(3): 245-251.
    [9]Zhang Xubo. Some Results on the Confluence Property of Combined Term Rewriting Systems[J]. Journal of Computer Science and Technology, 1991, 6(3): 291-295.
    [10]Xue Xing, Sun Zhongxiu, Zhou Jianqiang, Xu Xihao. A Message-Based Distributed Kernel for a Full Heterogeneous Environment[J]. Journal of Computer Science and Technology, 1990, 5(1): 47-56.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (14) PDF downloads (4459) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return