位置:成果数据库 > 期刊 > 期刊详情页
Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction
  • ISSN号:1000-9000
  • 期刊名称:《计算机科学技术学报:英文版》
  • 时间:0
  • 分类:TP312[自动化与计算机技术—计算机软件与理论;自动化与计算机技术—计算机科学与技术]
  • 作者机构:[1]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.
中文摘要:

在这篇论文,它被看那稳定模型语义,完美的模型语义,;分离逻辑程序的部分稳定模型语义关于多项式时间模型等价物减小有一样的富有表达力的力量。也就是说拿完美的模型语义;象一个例子语义的稳定模型,任何逻辑程序 P 能在另一逻辑程序 P ′的多项式时间被转变以便完成式当模特儿(分别地稳定模型) P 1-1 对应于 P ′的稳定模型(分别地完美的模型) ,;通讯能在多项式时间也被计算。然而,不那样,最小模型语义比另外的提及的语义有更弱的表现力多项式层次将崩溃到 NP。

英文摘要:

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.

同期刊论文项目
期刊论文 18 会议论文 3 著作 1
同项目期刊论文
期刊信息
  • 《计算机科学技术学报:英文版》
  • 中国科技核心期刊
  • 主管单位:
  • 主办单位:中国科学院计算机技术研究所
  • 主编:
  • 地址:北京2704信箱
  • 邮编:100080
  • 邮箱:jcst@ict.ac.cn
  • 电话:010-62610746 64017032
  • 国际标准刊号:ISSN:1000-9000
  • 国内统一刊号:ISSN:11-2296/TP
  • 邮发代号:2-578
  • 获奖情况:
  • 国内外数据库收录:
  • 被引量:505