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

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

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

80Journalof

Frontiers

of

Computer

Science

andTechnology计算机科学与探索2007,1(1

l

引言

认识论,即对知识的研究,从古希腊哲学家开

理一尝小规漠的问题(toyexamples)。

文【l】给出了一个吏用而紧致的知识的语义模etln’e)。这种方法本质上型:知识结构(knowledgestlM是基于语义的,但通过使用知识结构,给出了一种基于语法的简洁形式来表示Kfipke结构,而且可以随接转化成一个符号化布尔算法,借助符号化工具如

BDD(Binm3,DecisionDiagramn|_算,所以在一定程

始,在哲学中有很长的研究历史以及良好的传统Ⅲ。刘诸如“我们知道什么”。“什么能够被知道”、“说某人知道什么到底意味州么”等问题,在哲学文献中有很多讨论。rODWright在20世纪50年代的工作[31给出了对知识推理进行形式化分析的思想。1962年.Hintikkat41第一个以书本的形式给出了认知逻辑一知识逻辑的形式化研究。随后,关于知识的研究在哲学界蓬勃发展起来,主要兴趣之一是如何抓住知识的本质特征。各种关于知识的公理系统建立起来。最近,在不同领域(如经济学、语言学、人工智能以及理论计算机科学)的学者们都对知识推理产生兴趣。关于知识的研究也随之扩大.并在很多领域蓬勃发展起来,如博弈论、经济学、机器人、知识库等领域,来研究如机器人如何获得知识并进行推理以采取下一步行动、数据库何时回答“不知道”、商务智能体(a.

度上避免了状态爆炸问题。该知识结构框架既简单又强大,足以用来分析应用中的协议,如广泛使用的安全协议.实验表明这种基于BDD的算法比传统方法有更大的优势。但是这种基于J=;DD的方法存计算规模大的例子时还是有比较明显的组合爆炸问题。

艾章在知识结构(knowledgesrruetm'e)的语义基础上,通过挖掘知识结构语义中各元素的关系.将把知识的计算规约于可满足性问题(SAT),因为SATSolver在符号化计算方面在计算规模和效率上都要远远优越于BDD,并EL

SAT

solver的发展州当迅速。

gent)女n何收集信息以做决策等问题。其次.计算知识的复杂度也是一个研究方向。另外.知识推理研究

的重点是针对群体智能体(a

groupof

通过这种关系的揭示,还可以在计算复杂的公共知识时避免基于BDD方法f11中的繁琐的不动点计算。

下面将用实验结果来证实这种方法的有效性。

文章结构如下:先简单介绍认知逻辑的基本概念,然后介绍知识结构巾的一些技术结果.给出将这种语义计算规约于可满足性问题(SAT)的一些具体结果,接着将该方法应用于著名的”泥巴小孩”游戏和安全协议验证的实验结果,最后是相关工作和结论。

agents)的情况

(该文也如此),而非单个智能体(哲学家们偏向于研

究)的情况。这是因为对话、谈判、或者是分布式系统中进程问的协议,都是智能体间的交互行为口。

认知逻辑(或知识逻辑)一般认为起源于JaakkoHintikka在20世纪60年代早期的工作H,他描述了如何使用特定的模态逻辑来刻画知识的本质。在20

世纪80年代中期,Haivel'n和他的合作者发现s5认

知逻辑能够给出在分布式系统中进程(一般称之为agent)状态的自然解释。该模型即为所谓的解释系统

(interpreted

2认知逻辑

2.1语法

给定一个命题原子集合。,认知逻辑(知识逻辑)的良构公式(thewellfoundedformulas(wff))为以下定义的BNF:

system)模型日。研究发现.该模型在分布

式系统理论中起关键作用,已经成功应用到对通信协议的推理中日。然而,关于认知逻辑的工作还主要集中于理论方面的研究.例如:模态逻辑的各种变

(删)::=qblq(删)I(埘)A(wff>lK,(,4t'>LD,(wff)

lcc(wff)

简单的说,公式K。咖表示智能体i知道命题‘:b;D。咖表示在G中的所有智能体的分布式知识(d谆

tributed

种,完全性,计算复杂性。以及衍生的概念(如分布式

知识、公共知识)等。

对于认知逻辑相应的算法研究比较少.有基于证明的和基于语义的,例如文献[6—81。基于证明的方法依赖于多命题模态逻辑的证明器.所以处理规模和效率,及表达能力都不高;基于语义的对的问题是状态爆炸问题。闲此传统的

法主要面法只能处

knowledge)为咖;Cc币表示G中所有智能体

的公共知识(commonknowledge)为咖。这里K。、Dc和cG称为知识模态词(knowledgemodalities)。

认知逻辑的标准语义为Kfipke语义日。这种基于

上一页第2页

你可能喜欢

热门文档

相关文档

  • 对可满足性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