Consistency Property of Finite FC-Normal Logic Programs

Marek＇s forward-chaining construction is one of the important techniques for investigating the non-monotonic reasoning. By introduction of consistency property over a logic program, they proposed a class of logic programs, FC-normal programs, each of which has at least one stable model. However, it is not clear how to choose one appropriate consistency property for deciding whether or not a logic program is FC-normal. In this paper, we firstly discover that, for any finite logic programⅡ, there exists the least consistency property LCon（Ⅱ） overⅡ, which just depends onⅡitself, such that, Ⅱ is FC-normal if and only ifⅡ is FC-normal with respect to （w.r.t.） LCon（Ⅱ）. Actually, in order to determine the FC-normality of a logic program, it is sufficient to check the monotonic closed sets in LCon（Ⅱ） for all non-monotonic rules, that is LFC（Ⅱ）. Secondly, we present an algorithm for computing LFC（Ⅱ）. Finally, we reveal that the brave reasoning task and cautious reasoning task for FC-normal logic programs are of the same difficulty as that of normal logic programs.

Consistency Property of Finite FC-Normal Logic Programs

Marek’s forward-chaining construction is one of the important techniques for investigating the non-monotonic reasoning. By introduction of consistency property over a logic program, they proposed a class of logic programs, FC-normal programs, each of which has at least one stable model. However, it is not clear how to choose one appropriate consistency property for deciding whether or not a logic program is FC-normal. In this paper, we firstly discover that, for any finite logic program Π, there exists the least consistency property LCon (Π) over Π, which just depends on Π itself, such that, Π is FC-normal if and only if Π is FC-normal with respect to (w.r.t.) LCon (Π). Actually, in order to determine the FC-normality of a logic program, it is sufficient to check the monotonic closed sets in LCon (Π) for all non-monotonic rules, that is LFC (Π). Secondly, we present an algorithm for computing LFC (Π). Finally, we reveal that the brave reasoning task and cautious reasoning task for FC-normal logic programs are of the same difficulty as that of normal logic programs. Electronic Supplementary Material  The online version of this article (doi:) contatins supplementary material, which is available to authorized users. This work is partially supported by the National Natural Science Foundation of China under Grant No. 60573009 and the Stadholder Foundation of Guizhou Province under Grant No. 2005(212).