中文XML论坛 - 专业的XML技术讨论区--显示贴子

以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 Semantic Web(语义Web)/描述逻辑/本体』  (http://bbs.xml.org.cn/list.asp?boardid=2)
----  关于tractable DL的几个问题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=2&rootid=&id=68730)

--  作者：sherryzhy
--  发布时间：10/25/2008 11:01:00 PM

--  关于tractable DL的几个问题
刚刚开始研究描述逻辑的推理算法和复杂性,看到tractable DLs的时候有一些疑问,请各位大侠指教:
1 EL++, Horn-DLs, and DL-Lite这些语言tractable的原因是什么?是不是找到比tableau更好的算法的话,就可以改进ALC,ALCNFQ....等DL fragment的推理复杂性使其也成为tractable的语言

2 目前存在不存在tractable的带具体域(concrete domains)的DL语言,比如在EL++, HORN-DLS,DL-Lite里面加入concrete domains的表达力,它们是否还能tractable呢?

--  作者：baojie
--  发布时间：10/27/2008 5:55:00 AM

--
1. EL++, Horn-DLs, and DL-Lite tractable的原因是他们不包含一些会导致复杂计算的构造符，如在EL++中没有“非”。ALC或任何比它复杂的语言，是绝对不存在sound and complete and tractable算法的，这一点是理论上严格证明的。当然可以有incomplete and tractable算法。

2. EL++等当然可以带具体域，细节请看OWL 2 Profile文档

--  作者：wjwenoch
--  发布时间：11/19/2008 10:40:00 AM

--
一般的，如果有多项式算法就是tractable...

W 3 C h i n a ( since 2003 ) 旗下站点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》

46.875ms