没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
第 37卷第 3期
2009年 3月
同 济 大 学 学 报(自 然 科 学 版)
JOURNALOFTONGJIUNIVERSITY(NATURALSCIENCE)
V01.37 No。3
Mar.2009
文章 编号 :0253—374X(2009)03—0390—05
工作流模型验证及分解 的多项式算法分析
庞善 臣 ,蒋昌俊
(1.同济大学 计算机科学与212程 系,上海 200092;2.山东科技大学 信息科学与工程学院 ,山东 青岛 266510)
摘要 :基于工作流的 Petri网结构化建 模方法,证 明了工作 流
网的 T一不变量和 P一不变 量 的存 在性 、可 覆盖性 ,给 出了一
个工作流模型完整性 的充 要条件 ,进 一步得 到 了基 于 丁一不
变量的多项式分解算法 ,与以往非 多项 式分解 算法 相 比,克
服了遍历 的不足 ,降低 了算 法复 杂度 ,给 出的实例 验证 了算
法的有效性 .
关键词:工作流 ;Petri网;模 型分解及验证 ;多项式算法
中图分类号 :TP 302 文献标识码 :A
Workflow Verifieation and Polynomial
Algorithm of Model Decomposition
PANG Shanchen 一.JIANG Changjun
(1.Department of Computer Science & Engineering, Tongji
University,Shanghai 200092,China;2.Co llege of Information Science
& Engineering, Shandong University of Science & Technology,
Qingdao 266510,China)
Abstract:This paper presents a new necessary and sufficient
condition for the soundness of workflow model based on the
Petri nets modeling techniques.Some properties of worldlow
net were analyzed and verified,such as the existence of T—
invariant and P invariant of the workflow net(WF_net),the
sets of transitions and places be covered by T invariants and
P—invariants respectively. A polynomial algorithm of
workflow model decomposition based on T—invariant iS
presented.Compared with other exponential algorithms,the
algorithm is simple,easy to understand and operate,and can
also effectively simplify decompo sition and analysis of the
workflow systems.The effect of the pape r’S research results
iS verfied with an example.
Key words:worldlow;Petri net;model decomposition and
verification;polynomial algorithm
工作流建模方法是成功实施工作流管理的关键
术[1],工作流的模型分析和优化是工作流技术的一
个 研 究 重 点l2].工 作 流 管 理 联 盟 (workflow
management coalition,WfMC)L3 提 出了工作流管理
系统实施的系列标准和接 口规 范,以 WfMC提供的
规范标准为参考和基础 ,对工作流建模理论和方法
的研究工作在不断深入 .
Petri网是 目前工作流建模的主要方法之一.文
献E4]应用 Petri网对工作 流系统进行建模和验证 ,
提出了完整性 (soundness)的概念 ,目前 ,基于 Petri
网的工作流建模 中,采用的主要 有时间 Petri网[5]、
有色 Petri网[引、随机 Petri网[ ]和逻辑 Petri网[8]
等.目前,通过工作流模型的分解来分析工作流系统
性质的研究相对较少,文献[9]给出了工作流网的一
个特殊子类——无环 自由选择工作 流网的一个分解
算法 ,文献[2,5]将文献[9]的分解算法推广,进一步
给出了含有循环结构的自由选择工作流网的分解算
法 ,其复杂度只随选择库所指数增长 ,仍然是一个非
多项式算法 ,并且只能处理工作流网的特殊子类,有
一
定的局限性 ,本文证明了工作流网的 T一不变量和
P一不变量的存在性、可覆盖性 ,给出了一个工作流模
型完整性充要条件 ,提出的基于 T一不变量的多项式
分解算法,克服了上述算法的不足 ,降低了算法复杂
度,给出的实例验证 了算法的有效性.
1 工作流的 Petri网建模方法
荷兰埃 因霍恩 科技大学教 授 van der Aalst博士
利用 Petri网为建模工具 ,建立 了工作流的形式化模
型 ,给 出了工作 流 网 (workflow net,WF-net)的概
收稿 日期:2007—07—17
基金项 目:国家 “973”重点基础研究发展规 划资助项 目(2004CB318001—13);国家 自然 科学基金资助项 目(90412013,90718012,
60503002,60534060);上海市基础研究重点资助项 目(05JC14063)
作者简介 :庞善臣(1974一),男,副教授 ,工学博士,主要研究方向为计算机支持的协 同工作、模型形式化验证、Petri网应用.
E-mail:shanchenpang@ sohu.com
蒋昌俊 (1962一),男 ,教授 ,工学博 士,博士生导师,主要研究方向为并发理论 、并行处 理、Petri网、软件形式化验证.
E-mail:cjjiang@ online.sh.ca
资源评论
weixin_38617413
- 粉丝: 7
- 资源: 927
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功