Consistency Property of Finite FC-Normal Logic Programs

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 \it\Pi, there exists the leastconsistency property \it LCon(\it\Pi) over \it\Pi, which justdepends on \it\Pi itself, such that, \it\Pi is FC-normal if andonly if \it\Pi is FC-normal with respect to (w.r.t.) \itLCon(\it\Pi). Actually, in order to determine the FC-normality of alogic program, it is sufficient to check the monotonic closed sets in\it LCon(\it\Pi) for all non-monotonic rules, that is \itLFC(\it\Pi). Secondly, we present an algorithm for computing \itLFC(\it\Pi). 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.