|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 Semantic Web(语义Web)/描述逻辑/本体 』 (http://bbs.xml.org.cn/list.asp?boardid=2) ---- 关于可判定性(decidability)的疑问，求高手解答 (http://bbs.xml.org.cn/dispbbs.asp?boardid=2&rootid=&id=90341) |
|
-- 作者：qingmai -- 发布时间：4/13/2011 8:14:00 PM -- 关于可判定性(decidability)的疑问，求高手解答 怎么判断一种逻辑表达式是否是可可判定（decidable) 譬如，FOL是不可判定的，但是他的两个子类Horn rule 和DL都是可判定的，可是结合Rule和DL的SWRL又是不可判定的，但是DL-safe rule，我感觉好像是把SWRL限定在CWA的假设下使用，又成了可判定的了 到底怎么才能证明一套逻辑模型是可判定还是不可判定的？小弟最近在编一个在CWA环境下对SWRL和OWL进行推理的推理引擎，投了文章被人打回来了，说是理论上分析不够主要就是集中在这一块 |
|
-- 作者：baojie -- 发布时间：4/13/2011 11:46:00 PM -- 一般是用reducation（规约？），有问题B已知不可判定，B问题可以多项式时间reduce到A问题，则A问题不可判定。 B问题可以是停机问题，无限平面多米诺(domino)问题，Post对应问题等，具体看这个列表
|
|
-- 作者：qingmai -- 发布时间：4/13/2011 11:49:00 PM -- 那么如何证明可判定呢? 譬如如何证明DL-safe rule 是可判定？ |
|
-- 作者：baojie -- 发布时间：4/13/2011 11:51:00 PM -- 找一个可判定问题A，把你的问题规约到A上 或者，找一个推理算法，证明sound and complete. |
|
-- 作者：timshawn2010 -- 发布时间：5/11/2011 8:41:00 PM -- tractability（可/易处理性）是指什么？
|
|
-- 作者：boywaiter -- 发布时间：5/11/2011 10:26:00 PM --
推理问题复杂度不超过多项式时间。 |
|
-- 作者：mcat -- 发布时间：6/10/2011 8:21:00 PM -- 这是个好办法！ 常用的方法就是找一个可判定的系统，证明你可等同于或归约于它，则你的系统即是可判定的 |
|
-- 作者：wolfel -- 发布时间：6/14/2011 7:06:00 PM -- SWRL+ DL-safety可判定是因为有了safety的条件后rule在grounding之后得到的是有穷的，不是由于CWA。 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
41.016ms |