| |
|
| 基于完全有限前缀的过程实例表示图的分解 |
宋亮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 |
| |
摘要由于语义交织现象的广泛存在,导致过程模型的行为状态空间面临状态爆炸问题。完全有限前缀能够有效压缩过程模型的状态空间,但是会丢失部分任务间时序关系特征。该文提出时序保存的完全有限前缀(temporal-order protecting complete finite prefix, TPCFP)技术,既能在不丢失任何可达状态信息的前提下高效压缩状态空间,又能确保不丢失任何任务间的时序关系。通过从TPCFP叶子结点中不同的并发集合出发,逆向遍历直到初始状态,可以分解出代表过程模型所有过程实例的结构,称为过程实例表示图(execution instance representation graph, EIRG)。在实际过程模型集合上所做的实验表明该技术是高效和准确的。
|
| 关键词 ：过程模型,行为特征,过程实例,完全有限前缀 |
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 words：process modelbehavioral propertyexecution instancecomplete finite prefix |
| 收稿日期: 2013-11-26 出版日期: 2015-04-17 |
| 基金资助:国家自然科学基金资助项目 (61003099);国家“八六三”高技术项目 (2012AA040904);教育部—中国移动科研基金资助项目(MCM20123011) |
| [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. |
