Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a rev...Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method in special case, and gives a corresponding polynomial algorithm as well as its parallel version on CREW PRAM.展开更多
This paper gives an outline of knowledge base revision and some recently presented complexity results about propositional knowledge base revision. Different methods for revising propositional knowledge baize have been...This paper gives an outline of knowledge base revision and some recently presented complexity results about propositional knowledge base revision. Different methods for revising propositional knowledge baize have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method for special case, and gives its corresponding polynomial algorithm.展开更多
One of the important topics in knowledge base revision is to introduce an efficient implementation algorithm. Algebraic approaches have good characteristics and implementation method; they may be a choice to solve the...One of the important topics in knowledge base revision is to introduce an efficient implementation algorithm. Algebraic approaches have good characteristics and implementation method; they may be a choice to solve the problem. An algebraic approach is presented to revise propositional rule-based knowledge bases in this paper. A way is firstly introduced to transform a propositional rule-based knowledge base into a Petri net. A knowledge base is represented by a Petri net, and facts are represented by the initial marking. Thus, the consistency check of a knowledge base is equivalent to the reachability problem of Petri nets. The reachability of Petri nets can be decided by whether the state equation has a solution; hence the consistency check can also be implemented by algebraic approach. Furthermore, algorithms are introduced to revise a propositional rule-based knowledge base, as well as extended logic programming. Compared with related works, the algorithms presented in the paper are efficient, and the time complexities of these algorithms are polynomial.展开更多
This paper presents a programmable approach to revising knowledge bases consisting of clauses. Some theorems and lemmas are shown in order to give procedures for generating maximally consistent subsets. Then a complet...This paper presents a programmable approach to revising knowledge bases consisting of clauses. Some theorems and lemmas are shown in order to give procedures for generating maximally consistent subsets. Then a complete procedure and an incomplete procedure for generating the maximal consistent subsets are presented, and the correctness of the procedures is also shown. Furthermore, a way to implement knowledge base revision is presented, and a prototype system is introduced. Compared with related works, the main characteristic of our approach is that the approach can be implemented by a computer program.展开更多
文摘Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method in special case, and gives a corresponding polynomial algorithm as well as its parallel version on CREW PRAM.
文摘This paper gives an outline of knowledge base revision and some recently presented complexity results about propositional knowledge base revision. Different methods for revising propositional knowledge baize have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method for special case, and gives its corresponding polynomial algorithm.
基金Supported by the National Grand Fundamental Research 973 Program of China (Grant No. 2002CB312103)
文摘One of the important topics in knowledge base revision is to introduce an efficient implementation algorithm. Algebraic approaches have good characteristics and implementation method; they may be a choice to solve the problem. An algebraic approach is presented to revise propositional rule-based knowledge bases in this paper. A way is firstly introduced to transform a propositional rule-based knowledge base into a Petri net. A knowledge base is represented by a Petri net, and facts are represented by the initial marking. Thus, the consistency check of a knowledge base is equivalent to the reachability problem of Petri nets. The reachability of Petri nets can be decided by whether the state equation has a solution; hence the consistency check can also be implemented by algebraic approach. Furthermore, algorithms are introduced to revise a propositional rule-based knowledge base, as well as extended logic programming. Compared with related works, the algorithms presented in the paper are efficient, and the time complexities of these algorithms are polynomial.
基金This work was supposed by the National Fundamental Research 973 Program of China(Grand No．2002CB312103)； the National Natural Science Foundation of China(Grant Nos．60033020，70371052)．
文摘This paper presents a programmable approach to revising knowledge bases consisting of clauses. Some theorems and lemmas are shown in order to give procedures for generating maximally consistent subsets. Then a complete procedure and an incomplete procedure for generating the maximal consistent subsets are presented, and the correctness of the procedures is also shown. Furthermore, a way to implement knowledge base revision is presented, and a prototype system is introduced. Compared with related works, the main characteristic of our approach is that the approach can be implemented by a computer program.
