Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2014, Vol. 54 Issue (4): 490-494    
  本期目录 | 过刊浏览 | 高级检索 |
基于完全有限前缀的过程实例表示图的分解
宋亮1,2,闻立杰1(),王建民1,刘国平2,刘廷龙2,杨剑勇2
2. 成都军区联勤部后勤信息中心, 成都 610015
CFP-based method to extract execution instance representation graphs from business processes
Liang SONG1,2,Lijie WEN1(),Jianmin WANG1,Guoping LIU2,Tinglong LIU2,Jianyong YANG2
1. School of Software, Tsinghua University, Beijing 100084, China
2. Logistic Information Center, Chengdu Military Region, Chengdu 610015, China
全文: PDF(955 KB)   HTML
输出: BibTeX | EndNote (RIS)      
摘要 

由于语义交织现象的广泛存在,导致过程模型的行为状态空间面临状态爆炸问题。完全有限前缀能够有效压缩过程模型的状态空间,但是会丢失部分任务间时序关系特征。该文提出时序保存的完全有限前缀(temporal-order protecting complete finite prefix, TPCFP)技术,既能在不丢失任何可达状态信息的前提下高效压缩状态空间,又能确保不丢失任何任务间的时序关系。通过从TPCFP叶子结点中不同的并发集合出发,逆向遍历直到初始状态,可以分解出代表过程模型所有过程实例的结构,称为过程实例表示图(execution instance representation graph, EIRG)。在实际过程模型集合上所做的实验表明该技术是高效和准确的。

服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词 过程模型行为特征过程实例完全有限前缀    
Abstract

Studies of the semantic behavioral properties of business processes are limited by state explosion caused by interleaving of concurrent events. The complete finite prefix (CFP) method avoids the state explosion problem as much as possible and gives full reachability information for process models. However, CFP may lose temporal-order information between tasks. This paper describes a CFP based method that extracts all execution instances from business process models. Thus, this method overcomes the shortcomings of the CFP method. The method uses back traversing from the co-sets of leaf nodes to the initial nodes to extract the execution instances in process models that are then represented by an execution instance representation graph. Tests with a process model repository show that this method is very efficient and accurate.

Key wordsprocess model    behavioral property    execution instance    complete finite prefix
收稿日期: 2013-11-26      出版日期: 2014-04-15
基金资助:国家自然科学基金资助项目 (61003099);国家“八六三”高技术项目 (2012AA040904);教育部—中国移动科研基金资助项目(MCM20123011)
引用本文:   
宋亮,闻立杰,王建民,刘国平,刘廷龙,杨剑勇. 基于完全有限前缀的过程实例表示图的分解[J]. 清华大学学报(自然科学版), 2014, 54(4): 490-494.
Liang SONG,Lijie WEN,Jianmin WANG,Guoping LIU,Tinglong LIU,Jianyong YANG. CFP-based method to extract execution instance representation graphs from business processes. Journal of Tsinghua University(Science and Technology), 2014, 54(4): 490-494.
链接本文:  
http://jst.tsinghuajournals.com/CN/  或          http://jst.tsinghuajournals.com/CN/Y2014/V54/I4/490
  TPCFP的生成算法
指标 数量
模型数量 591
变迁数量 4 439
标签数量 1 494
平均变迁数量 7.5
平均库所数量 12.7
平均有向边数量 19.7
  SAP业务过程模型集合统计特征
指标 数量
过程实例表示图数量 3 134
变迁数量 16 924
平均变迁数量 5.4
平均库所数量 9.6
平均有向边数量 11.8
  过程实例表示图集合统计特征
[1] Awad A. BPMN-Q: A language to query business processes [C]// Proceedings of the 2nd International Workshop on Enterprise Modelling and Information Systems Architectures (EMISA'07). Bonn, Germany: Greenhill, 2007: 115-128.
[2] Beeri C, Eyal A, Kamenkovich S, et al.Querying business processes with BP-QL [J]. Information Systems, 2008, 33(6): 477-507.
[3] Awad A, Decker G, Weske M. Efficient compliance checking using bpmn-q and temporal logic [C]// Proceedings of the 6th International Conference on Business Process Management. Berlin, Germany: Springer-Verlag, 2008: 326-341.
[4] Weidlich M, Mendling J, Weske M. Efficient consistency measurement based on behavioral profiles of process models[J]. IEEE Transactions on Software Engineering, 2011, 37(3), 410-429.
[5] Becker M, Laue R. A comparative survey of business process similarity measures[J]. Computers in Industry, 2012, 63(2): 148-167.
[6] Mcmillan K L. Using unfoldings to avoid the state explosion problem in the verification of asynchronous circuits [C]// Proceedings of the Fourth International Workshop on Computer Aided Verification. London, UK: Springer-Verlag, 1992: 164-177.
[7] Mcmillan K L. Atechnique of a state space search based on unfolding[J]. Formal Methods in System Design, 1995, 6(1): 45-65.
[8] Murata T. Petri nets: Properties, analysis and applications[J]. Proceedings of the IEEE, 1989, 77(4): 541-580.
[9] Aalst W M P van der. The application of Petri nets to workflow management[J].The Journal of Circuits, Systems and Computers, 1998, 8(1): 21-66.
[10] Nielsen M, Plotkin G D, Winskel G. Petri nets, event structures and domains [C]// Proceedings of the International Symposium on Semantics of Concurrent Computation. London, UK: Springer-Verlag, 1979: 266-284.
[11] Engelfriet J. Branching processes of petri nets[J]. Acta Informatica, 1991, 28(6): 575-591.
[12] Clarke E M, Grumberg O, Peled D. Model Checking [M]. Massachusetts, USA: MIT Press, 1999.
[13] Esparza J, Römer S, Vogler W. An improvement of mcmillan's unfolding algorithm[J]. Formal Methods in System Design, 2002, 20(3): 285-310.
[1] 姜波, 陈涛, 袁宏永, 范维澄. 基于情景时空演化的暴雨灾害应急决策方法[J]. 清华大学学报(自然科学版), 2022, 62(1): 52-59.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn