中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
基于状态空间的无界Petri网分析技术
作者: 江波
答辩日期: 2008-05-28
授予单位: 中国科学院软件研究所
授予地点: 软件研究所
学位: 博士
关键词: 标识 ; 有界性 ; 活性 ; 无死锁性 ; 分支进程 ; 展开 ; 前缀
其他题名: On the Analysis Techniques of Unbounded Petri Nets Based on the State Space
摘要: Petri 网提供了一种以图形和数学为基础的形式化建模方法。现在它已经成为建模和分析工业系统的成熟工具,其应用领域也越来越广泛,涉及到工作流管理,软件工程,并发程序设计,异步电路,协议验证等等。 目前对Petri 网的理论研究更多的是限于有界的情形,并且已经取得了相当大的成功,而无界Petri 网方面的研究进度则相对缓慢。在验证无界Petri 网系统的性质时往往面临着严重的状态爆炸问题。无界Petri 网系统的状态爆炸问题主要体现在两个方面:其一是变迁序列的周期性执行,其二是并发行为的交错执行。 针对第一种情形的状态爆炸,一般采用构造可达图的有限形式,即可覆盖树,但是可覆盖树有很大的局限性,例如不能验证网系统的可达性和活性等等。本文采用一种改进的可达树技术,一方面改进的可达树是有限的(即可以缓解这类状态爆炸问题),另一方面,我们可以直接使用改进的可达树来验证网系统的可达性和活性。 针对第二种情形的状态爆炸,方法之一是采用基于偏序语义的ω-分支进程技术。ω-分支进程结合了分支进程和可覆盖树两种技术,在验证系统的性质方面,它和可覆盖树一样具有一定的局限性,例如不能用来验证可达性问题。为使ω-分支进程能够验证可达性问题,本文结合改进的可达树技术,对ω-分支进程的改进工作做了初步的探讨。
英文摘要: Petri nets give a formal modeling method based on the graphics and mathematics. Nowadays they have been mature tools of modeling and analysis of manufacturing systems and received more and more widespread applications such as work-flow management, software engineering, concurrent programming design, asynchronous circuits, protocol verification, etc. So far, the theoretical research of Petri nets, on the most occasions, has been limited to the bounded Petri nets and much achievement has been obtained, while little research on the unbounded Petri nets has been available. The reason is that, for unbounded Petri nets, it is more difficult to handle the state explosion involved in the construction of the state space. This state explosion of unbounded Petri nets comes from two aspects: one is the periodic occurring of firing sequences, and the other is concurrent occurring of transitions. For the first aspect, the finite form of the reachability graph, the coverability tree, is constructed since the reachability graph of an unbounded Petri net is always infinite. However, the coverability tree has no ability of checking properties such as reachability and liveness. In this paper, we propose an improved reachability tree technique. It has two advantages: one is the finiteness of the improved reachability tree, the other is its ability of checking reachability and liveness. For the second aspect, one of the most prevalent solutions is the ω-branching process based on the partial order semantics. ω-branching processes result from the combination of the concepts of coverability tree and branching process. When checking properties, such as the reachability problem, the ω-branching processes have the same limitation as the coverability trees. In order to enhance the ability of checking the reachability, we describe a primitive improvement of ω-branching processes using the improved reachability tree techniques.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6974
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_200528015029036江波_paper.pdf(1204KB)----限制开放-- 联系获取全文

Recommended Citation:
江波. 基于状态空间的无界Petri网分析技术[D]. 软件研究所. 中国科学院软件研究所. 2008-05-28.
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