| Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction |
| |
| 引用本文： | Xi-Shun Zhao and Yu-Ping Shen. Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction[J]. 计算机科学技术学报, 2007, 22(4): 562-568. DOI: 10.1007/s11390-007-9078-7 |
| |
| 作者姓名： | Xi-Shun Zhao and Yu-Ping Shen |
| |
| 作者单位： | Institute of Logic and Cognition, Sun Yat-Sen University, Guangzhou 510275, China |
| |
| 基金项目： | This research was partially supported by the National Natural Science Foundation of China under Grant Nos. 60573011, 10410538 and an M0E Project of Key Institute at Universities under Grant No. 05JJD72040122.The authors would like to thank the anonymous referees for their valuable suggestions and information to improve the paper. |
| |
| 摘 要： | In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction. That is, taking perfect model semantics and stable model semantic as an example, any logic program P can be transformed in polynomial time to another logic program P＇ such that perfect models （resp. stable models） of P i-i correspond to stable models （resp. perfect models） of P＇, and the correspondence can be computed also in polynomial time. However, the minimal model semantics has weaker expressiveness than other mentioned semantics, otherwise, the polynomial hierarchy would collapse to NP.
|
| 关 键 词： | 分离性逻辑程序 语义学 等效恢复 布尔公式 |
| 收稿时间： | 2006-05-16 |
| 修稿时间： | 2006-05-162007-02-08 |
Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction |
| |
| Xi-Shun Zhao,Yu-Ping Shen. Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction[J]. Journal of Computer Science and Technology, 2007, 22(4): 562-568. DOI: 10.1007/s11390-007-9078-7 |
| |
| Authors: | Xi-Shun Zhao Yu-Ping Shen |
| |
| Affiliation: | Institute of Logic and Cognition, Sun Yat-Sen University, Guangzhou 510275, China |
| |
| Abstract: | In this paper,it is shown that stable model semantics,perfect model semantics,and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction.That is,taking perfect model semantics and stable model semantic as an example,any logic program P can be transformed in polynomial time to another logic program P' such that perfect models(resp.stable models)of P 1-1 correspond to stable models(resp.perfect models)of P',and the correspondence can be computed also in polynomial time.However,the minimal model semantics has weaker expressiveness than other mentioned semantics,otherwise,the polynomial hierarchy would collapse to NP. |
| |
| Keywords: | disjunctive logic program semantics polynomial-time model-equivalent reduction quantified Boolean formula |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载免费的PDF全文 |
