| Fast Algorithms for Revision of Some Special Prepositional Knowledge Bases |
| |
| 作者姓名： | 栾尚敏 戴国忠 |
| |
| 作者单位： | Institute of Software，The Chinese Academy of Sciences Beijing P.R. China 100080，Institute of Software，The Chinese Academy of Sciences Beijing P.R. China 100080 |
| |
| 基金项目： | This work is supported by the National Natural Sciences Foundation of China under Grant Nos.60033020 and 60103020,and the China Postdoctoral Foundation of Sciences. |
| |
| 摘 要： | In this paper, the computational complexity of prepositional clause set counterfactuals is discussed. It is shown that the computational complexity of prepositional clause set counterfactuals is at the second level of the polynomial hierarchy, and that the computational complexity of prepositional Horn clause set counterfactuals is at the first level of the polynomial hierarchy. Furthermore, some polynomial algorithms are presented for some special prepositional clause set, such as the unique satisfiable clause set and the clause set of which only one subset is minimally inconsistent with the input clause whose inconsistency check can be solved in polynomial time.
|
Fast Algorithms for Revision of Some Special Prepositional Knowledge Bases |
| |
| LUAN ShangMin and DAI GuoZhong
Institute of Software,The Chinese Academy of Sciences,Beijing ,P.R. China.Fast Algorithms for Revision of Some Special Prepositional Knowledge Bases[J].Journal of Computer Science and Technology,2003(3). |
| |
| Authors: | LUAN ShangMin and DAI GuoZhong
Institute of Software The Chinese Academy of Sciences Beijing PR China |
| |
| Affiliation: | LUAN ShangMin and DAI GuoZhong
Institute of Software,The Chinese Academy of Sciences,Beijing 100080,P.R. China |
| |
| Abstract: | In this paper, the computational complexity of prepositional clause set counterfactuals is discussed. It is shown that the computational complexity of prepositional clause set counterfactuals is at the second level of the polynomial hierarchy, and that the computational complexity of prepositional Horn clause set counterfactuals is at the first level of the polynomial hierarchy. Furthermore, some polynomial algorithms are presented for some special prepositional clause set, such as the unique satisfiable clause set and the clause set of which only one subset is minimally inconsistent with the input clause whose inconsistency check can be solved in polynomial time. |
| |
| Keywords: | prepositional base revision computational complexity polynomial algorithm |
| 本文献已被 CNKI 等数据库收录！ |
