The paradigm of disjunctive logic programming (DLP) enhances greatly the expressive power of normal logic programming (NLP) and many (declarative) semantics have beeu defined for DLP to cope with various problems of ...The paradigm of disjunctive logic programming (DLP) enhances greatly the expressive power of normal logic programming (NLP) and many (declarative) semantics have beeu defined for DLP to cope with various problems of knowledge representation in artificial intelligence. However, the expressive ability of the semantics and the soundness of program transformations for DLP have been rarely explored. This paper defines an immediate consequence operator TGP for each disjunctive program and shows that TGP has the least and computable fixpoint Lft(P). Lft is, in fact, a program transformation for DLP which transforms all disjunctive programs into negative programs. It is shown that Lft preserves many key semantics, including the disjunctive stable models, well-founded model, disjunctive argument semantics DAS, three-valued models, etc. This means that every disjunctive program P has a unique canonical form Lft(P) with respect to these semanics. As a result, the work in this paper provides a unifying frameword for studying the expressive ability of various semantics for DLP.On the other hand, the computing of the above semantics for negative programs is just a trivial task, therefore, Lft(P) is also an optimization method for DLP. Another application of Lft is to derive some interesting semantic results for DLP.展开更多
The relationship between TMS and general logic programs is an important issue in non-monotonic logic programming. In this paper, we prove that, after we translate the TMS theory into a general logic program, the TMS&#...The relationship between TMS and general logic programs is an important issue in non-monotonic logic programming. In this paper, we prove that, after we translate the TMS theory into a general logic program, the TMS's well-founded assignment (orextension) is equivalent to the corresponding general logic program's stable model. It means that TMS can be completely integrated into a non-monotonic logic programming environment.展开更多
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 pro...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.展开更多
This paper investigates the consistency property of FC-normal logic program and presents an equivalent deciding condition whether a logic program P is an FC-normal program. The deciding condition describes the charact...This paper investigates the consistency property of FC-normal logic program and presents an equivalent deciding condition whether a logic program P is an FC-normal program. The deciding condition describes the characterizations of FC-normal program. By the Petri-net presentation of a logic program, the characterizations of stratification of FC-normal program are investigated. The stratification of FC-normal program motivates us to introduce a new kind of stratification, extended stratification, over logic program. It is shown that an extended (locally) stratified logic program is an FC-normal program. Thus, an extended (locally) stratified logic program has at least one stable model. Finally, we have presented algorithms about computation of consistency property and a few equivalent deciding methods of the finite FC-normal program.展开更多
文摘The paradigm of disjunctive logic programming (DLP) enhances greatly the expressive power of normal logic programming (NLP) and many (declarative) semantics have beeu defined for DLP to cope with various problems of knowledge representation in artificial intelligence. However, the expressive ability of the semantics and the soundness of program transformations for DLP have been rarely explored. This paper defines an immediate consequence operator TGP for each disjunctive program and shows that TGP has the least and computable fixpoint Lft(P). Lft is, in fact, a program transformation for DLP which transforms all disjunctive programs into negative programs. It is shown that Lft preserves many key semantics, including the disjunctive stable models, well-founded model, disjunctive argument semantics DAS, three-valued models, etc. This means that every disjunctive program P has a unique canonical form Lft(P) with respect to these semanics. As a result, the work in this paper provides a unifying frameword for studying the expressive ability of various semantics for DLP.On the other hand, the computing of the above semantics for negative programs is just a trivial task, therefore, Lft(P) is also an optimization method for DLP. Another application of Lft is to derive some interesting semantic results for DLP.
文摘The relationship between TMS and general logic programs is an important issue in non-monotonic logic programming. In this paper, we prove that, after we translate the TMS theory into a general logic program, the TMS's well-founded assignment (orextension) is equivalent to the corresponding general logic program's stable model. It means that TMS can be completely integrated into a non-monotonic logic programming environment.
基金This work is partially supported by the National Natural Science Foundation of China under Grant No.60573009the Stadholder Foundation of Guizhou Province under Grant No.2005(212).
文摘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.
文摘This paper investigates the consistency property of FC-normal logic program and presents an equivalent deciding condition whether a logic program P is an FC-normal program. The deciding condition describes the characterizations of FC-normal program. By the Petri-net presentation of a logic program, the characterizations of stratification of FC-normal program are investigated. The stratification of FC-normal program motivates us to introduce a new kind of stratification, extended stratification, over logic program. It is shown that an extended (locally) stratified logic program is an FC-normal program. Thus, an extended (locally) stratified logic program has at least one stable model. Finally, we have presented algorithms about computation of consistency property and a few equivalent deciding methods of the finite FC-normal program.
