中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 学位论文
题名:
分布式系统中必然方式下的谓词检测
作者: 黄洪涛
答辩日期: 2009-06-04
导师: 张文辉
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所5号楼337
学位: 硕士
摘要: 本文研究了Definitely模态下分布式计算的谓词检测问题,即判断在计算产生的格状态空间中,是否每条从最小元到最大元的路径都通过一个满足谓词的状态。本文的主要内容有以下四个方面: 1、本文建立了一个逻辑公式用来描述一个DNF谓词在Definitely模态下的检测是否为真。这个逻辑公式给出了一个新的方式用以考察对于DNF谓词Definitely模态的含义。由这个逻辑公式可以导出一种原有的区间缩减技术:区间压缩。接下来使用这个逻辑公式,还可以得到两种新的区间缩减技术:区间组合和区间删除。为了进行区间组合和区间删除,本文将计算表示成Hasse图,同时给出了一个化简Hasse图的方法。 2、本文给出了两类DNF谓词,它们可以按照与合取谓词类似的方式检测,因此有多项式时间的检测算法。这两类DNF谓词是:分离DNF谓词和分离-包含DNF谓词。 3、必然状态和必然集合在上面两类DNF谓词的检测中起着重要作用,因此本文研究了必然状态和必然集合的一些性质。接下来本文提出了区域独立的概念,区域独立是上面两类DNF谓词有多项式时间检测算法的本质,同时给出了区域独立的一些基本性质。 4、本文证明了正则谓词在Definitely模态下的检测是coNP完全的,回答了文献中提出的未解决的问题。接下来研究了一种特殊情况下正则谓词在Definitely模态下的检测。这种特殊情况是:计算的所有状态都是一致的,称这时的状态空间为全空间。本文给出了全空间情况下对于正则谓词,Definitely模态和Invariant模态之间的关系。并且给出了一种算法,它在全空间情况下通过测试n条简单路进行Definitely模态下正则谓词的检测,其时间复杂度是O(n|E|),其中n为计算中进程的个数,|E|是计算中所有事件的个数。
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/113
Appears in Collections:计算机科学国家重点实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
Thesis.pdf(1741KB)----限制开放 联系获取全文

Recommended Citation:
黄洪涛. 分布式系统中必然方式下的谓词检测[D]. 中国科学院软件研究所5号楼337. 中国科学院软件研究所. 2009-06-04.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[黄洪涛]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[黄洪涛]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace