Consistency Property of Finite FCNormal Logic Programs

Abstract
Marek's forwardchaining construction is one of the importanttechniques for investigating the nonmonotonic reasoning. Byintroduction of consistency property over a logic program, theyproposed a class of logic programs, FCnormal 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 FCnormal. 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 FCnormal if andonly if \it\Pi is FCnormal with respect to (w.r.t.) \itLCon(\it\Pi). Actually, in order to determine the FCnormality of alogic program, it is sufficient to check the monotonic closed sets in\it LCon(\it\Pi) for all nonmonotonic 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 FCnormal logic programs are of the samedifficulty as that of normal logic programs.

