文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 一种规约于可满足性问题SAT的知识推理算法
侵权投诉

一种规约于可满足性问题SAT的知识推理算法

传统的知识推理算法主要依赖于通用的定理证明器,因此会有明显的组合爆炸问题和半自动化问题,只能处理小规模的问题.在文[1]中,给出了一个实用而紧致的知识的语义模型--知识结构(knowledge structure),并给出相应的利用BDD(Binary Decision Diagram)的符号化计算方法,实验表明这种基于BDD的算法比传统方法有很大的优势,但这种基于BDD的方法在计算规模大的例子时仍存在明显的组合爆

lSSN1673—94l8of

CODENJKYTA8

ScienceandTechnology

E—nmll

Journal

Computer

1673—9418/2007/01(01)一0079—08

Frontiersof

Tcl+86一lO一51616056

hnp1lvn㈣eeaj

fcst@nci

术

acell

org

一种规约于可满足性问题

苏开乐.陈清亮+.岳伟亚

SUKai—le,CHEN

(SAT)的

知识推理算法

Qing—liang,YUEWei—ya

中f『I大学计算机科学系.J'州510275

Department

of

Comput,r

Science.Sun

Yat—senUniversity。,Gumlgzhou510275,China

+Cm'respondingauthor:E—main:tsingliangchen@94nail.com

SUKai—le.CHlENFrontiersof

Qing—liang.YUEWei—ya.SAT—basedalgorithm

for

knowledgereasoning.Journal

of

ComputerScienceandTechnology,2007,1(1):79-86.

Abstract:Traditionalplosion

problemandhas

been

knowledge

can

reasoningsrely

on

the

generaltheoremprovers

concrete

andmayof

sull;rthe

called

stateex—

only

deat

withtoyexamoreples.Am

presents

a

model

knowledgeknowledge

and

OFt

structure

introduced

in(1】,whichBDD-basedapproachfor

a

computingknowledge

showsthe

greatimprovement.But

structure,anis

the

BDD—basedapproachstillhas

way

substantialstate

explosionproblem.Basedknowledge

the

reasoning

state

knowledge

agents

alternativeandeffective

SAT

can

by

SATsolvingpowerful

in

forthein

a

groupofillustrated,since

bemuchmore

this.

ithdealingw

explosion

problemthan

BDDs.Finallytheexperimental

resultsprove

Keywords:knowledge

structure;knowledgereasoning;satis6ability(sAT)

摘要:传统的知识推理算法主要依粕于通用的定理证明器.因此会有明显的组合爆炸问题和半自动化问题.

只能处理小规模的问题。在文『1]中,给出了一个实用而紧致的知识的语义模型——知识结构(knowledge

ture),并给出相应的利用BDD(Binary

Decision

struc—

Diagram)的符号化计算方法,实验表明这种基于BDD的算法比

传统方法有很大的优势,但这种基于BDD的方法在计算规模大的例子时仍存在明显的组合爆炸。文章在知识结构(knowledgestructure)的语义基础上,通过挖掘知识结构语义中各元素的关系,把知识的计算规约于可满足性问题(SAT),因为SATSoh,er在符号化计算方面以及在计算规模和效率上都要明显优于BDD,、实验结果证实了这种方法的有效性.

关键词:知识结构;知识推理;可满足性问题(SAT)文献标识码:A

中图分类号:TP3叭

8

theNationalthe

GrandFundamentalResesreh973ProgramofChinaunderGrant

ScienceFoundationofof

ChinaunderGrantof

China

under

No.2005CB321902(囤家重点基础研究发展规划(973));

Natural

in

NafimmlNatural

No.60496327,10410638,60473004(国家自然科学基金);the

Grant

ScienceFoundation

Guangdong

Province

No.04205407(r东省自然科学基金);the

Open

Fund

Shan曲ai

Intelligent

INbrmafionProcessingKaboratoryundereyLGrar,t(k淘t市智能信息处理重点实验室开放课题资助项目)

Received2007—02,Accepted2007—04

第1页

你可能喜欢

热门文档

相关文档

  • 对可满足性SAT问题求全解的算法研究及实现

    对可满足性SAT问题求全解的算法研究及实现_IT/...在这 一推理算法中,每个子句有两个相关的指针,分别... 中医养生知识大全 女人养生之道 78份文档 笑翻...

  • 利用一种SAT问题全解算法求Trivium可滑动对

    2012 利用一种 SAT 问题全解算法求 Trivium 可滑动对戴江海, 戚文峰( 信息工程大学 信息工程学院, 河南 郑州 450002) 摘要: Trivium 是进入到 eSTREAM 计划最终...

  • 可满足性问题DPLL算法研究

    实验结果验证了 这项新的正向推理技术的有效性,并...可满足性问题算法(TheSatisfiabilityProblem, 简称SAT...章简要介绍和说明了有关可满足性问题的基础知识和 ...

  • 基于集合理论的SAT算法的设计与实现

    (如C,C++),或者学过数字电路的基本 知识的人,对...而且在自动化推理,人工智 能,资源调度,VLSI集成电路...电子科技大学硕士学位论文 1.1.2 SAT问题及其算法...

  • 一种新的SAT问题预处理算法

    一种新的SAT问题预处理算法熊 伟.唐璞山(复旦大学专用集成电路与系统国家重点实验室.上海201203) 抽要:提出了一项新的正向推理技术:对祢扩展的一元子句推导(...

  • 一种新的SAT问题预处理算法

    一种新的SAT问题预处理算法一种新的SAT问题预处理算法隐藏>> 20 年第 2卷...算法的 有 效性, 证明了 这项对 称扩展一元推导技术的 强大正 向 推理能力...

  • SAT问题及其转换公式

    命题逻辑 可满足性问题的算法 分析[J]. 计算机科学...? BMC问题能够有效地规约成命题SAT问题。 只考虑一...它们的最短的推理出空 子句的归结证明长度是指数的...

  • 一种改进的基于SAT的多错误诊断算法

    改进了二种组合电路设计错误诊断DED(Design Error Diagnosis)算法。它使用多可满足性问题(SAT)求解技术,通过对布尔可满足解计数来实现对多个逻辑错误的诊断定位。...

  • 一种基于形式规约说明的类测试框架

    产生了传统语言设计所不存在的错误可能性,或者使 得传统软件测试中的重点不再...基于范畴划 分方法构造测试层次算法, 将操作的输入空间划分为具有某些相同性质的...

  • 基于SAT工具的限界模型检测归约方法

    规约为命题逻辑的可 满足性问题,从而可以使用 SAT ...魏小勇 基于OBDD的SMC中PRE操作的改进算法 2008(14...分析方法,在验证电子商务协议时,它的 逻辑推理能力...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email