微信服务号

微信订阅号

2025-4-3- 22
Home > Archive>Volume 32, Issue 5, 2021 >1385-1403. DOI:10.13328/j.cnki.jos.006162
PDF HTML XML Export Cite reminder
Generating Algorithm for the Behavior Equivalent Process Tree Based on Complete Finite Prefix Unfolding
Author:
Affiliation:

Clc Number:

TP311

Fund Project:

National Natural Science Foundation of China (62002310); Major Project of Science and Technology of Yunnan Province (202002AD080002); Yunnan Provincial Natural Science Foundation of China (2019FB135); Yunnan Provincial Open Fund Project of the Software Engineering Key Laboratory (2020SE404); Yunnan University Data-driven Software Engineering Provincial Science and Technology Innovation Team Foundation of China (2017HC012); Yunnan University "Dong Lu Young-backbone Teacher" Training Program of China (C176220200)

  • Article
    • | |
  • Metrics
    • |
  • Reference [44]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    The process tree has both the behavior and the structure of process model, and it is significant on simplifying the complexity of the process model. Existing methods can only transform the block structured process model into process tree. However, it is difficult to transform process model with complex structure into process tree. To solve this problem, a generating algorithm for the behavior equivalent process tree based on complete finite prefix unfolding is proposed. The algorithm is used to transform the process tree in behavior equivalent's process model into behavior equivalent process tree. This algorithm analyzes the process model based on an incomplete prefix unfolding technique and extracts the relationships between process model activities. After analyzing the activity relation, the algorithm reconstructs the process model. The behavior equivalent process tree is constructed through activity relation judgment and the iterative operation of model reconstruction. The validity and feasibility of the proposed algorithm in the generation of behavioral equivalent process tree are verified by experiments on the test model.

    Reference
    [1] Jin T, Wen LJ. Indexing technology for business process models. Computer Integrated Manufacturing Systems, 2011,17(8):1580-1586(in Chinese with English abstract).[doi:10.4028/www.scientific.net/AMR.154-155.87]
    [2] Van Dongen BF. BPI challenge 2014:Change details. Rabobank Nederland, 2014.[doi:10.4121/uuid:d5ccb355-ca67-480f-8739-289b9b593aaf]
    [3] Van Der Aalst WMP. Process Mining:Data Science in Action. 2th ed., Heidelberg:Springer-Verlag, 2016.[doi:10.1007/978-3-662-49851-4]
    [4] Tax N, Sidorova N, Haakma R, van der Aalst WMP. Mining local process models. Journal of Innovation in Digital Ecosystems, 2016,3(2):183-196.[doi:10.1016/j.jides.2016.11.001]
    [5] Diamantini C, Genga L, Potena D. Behavioral process mining for unstructured processes. Journal of Intelligent Information Systems, 2016,47(1):5-32.[doi:10.1007/s10844-016-0394-7]
    [6] Zhang XW, Song W, Wang JC, Xing JC, Zhou QZ. Measuring business process consistency across different abstraction levels. IEEE Trans. on Network and Service Management, 2019,16(1):294-307.[doi:10.1109/TNSM.2018.2883362]
    [7] Chinces D, Salomie I. Optimizing spaghetti process models. In:Proc. of the 20th Int'l Conf. on Control Systems and Computer Science. Romania:IEEE, 2015.506-511.[doi:10.1109/CSCS.2015.15]
    [8] Tax N, Sidorova N, Haakma R, van der Aalst WMP. Event abstraction for process mining using supervised learning techniques. In:Bi Y, Kapoor S, Bhatia R, eds. Proc. of the SAI Intelligent Systems Conf. (IntelliSys) 2016. Cham:Springer Int'l Publishing, 2016.251-269.[doi:10.1007/978-3-319-56994-9_18]
    [9] Çela O, Front A, Rieu D. Model consolidation:A process modelling method combining process mining and business process modelling. In:Gulden J, ed. Proc. of the BPMDS 2018, EMMSAD 2018:Enterprise, Business-process and Information Systems Modeling. Cham:Springer Int'l Publishing, 2018.117-130.[doi:10.1007/978-3-319-91704-7_8]
    [10] Leemans M, van der Aalst WMP, van den Brand MGJ. Recursion aware modeling and discovery for hierarchical software event log analysis. In:Proc. of the 25th IEEE Int'l Conf. on Software Analysis, Evolution and Reengineering (SANER). Campobasso:IEEE, 2018.185-196.[doi:10.1109/SANER.2018.8330208]
    [11] Lu XX, Tabatabaei SA, Hoogendoorn M, Reijers HA. Trace clustering on very large event data in healthcare using frequent sequence patterns. In:Hildebrandt T, van Dongen B, Röglinger M, Mendling J, eds. Proc. of the BPM 2019:Business Process Management. Cham:Springer Int'l Publishing, 2019.198-215.[doi:10.1007/978-3-030-26619-6_14]
    [12] Zhu R, Li T, Mo Q, He ZL, Yu Q, Wang YQ. Data-driven bilayer software process mining. Ruan Jian Xue Bao/Journal of Software, 2018,29(11):3455-3483(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5304.htm[doi:10.13328/j.cnki.jos. 005304]
    [13] Van Der Aalst WMP. Process discovery from event data:Relating models and logs through abstractions. Wiley Interdisciplinary Reviews Data Mining & Knowledge Discovery, 2018,8(3):Article No.e1244.[doi:10.1002/widm.1244]
    [14] Van Der Aalst WMP. Everything you always wanted to know about Petri nets, but were afraid to ask. In:Hildebrandt T, van Dongen B, Röglinger M, Mendling J, eds. Proc. of the BPM 2019:Business Process Management. Cham:Springer Int'l Publishing, 2019.3-9.[doi:10.1007/978-3-030-26619-6_1]
    [15] Milner R, Wrote; Lin HM, Liu XX, Liu J, Qu N, Trans. Communicating and Mobile Systems:π-calculus. Beijing:Tsinghua University Press, 2009(in Chinese).
    [16] Van Der Aalst WMP, Buijs J, van Dongen B. Towards improving the representational bias of process mining. In:Aberer K, Damiani E, Dillon T, eds. Proc. of the Data-driven Process Discovery and Analysis. Berlin, Heidelberg:Springer-Verlag, 2012.39-54.[doi:10.1007/978-3-642-34044-4_3]
    [17] Buijs J, van Dongen B, van der Aalst WMP. A genetic algorithm for discovering process trees. In:Proc. of the 2012 IEEE Congress on Evolutionary Computation. Brisbane:IEEE, 2012.1-8.
    [18] Zhu R, Zhang ZX, Mo Q, Li T, Ma ZF, Li B. Hybrid process mining method supporting complex structures. Computer Integrated Manufacturing Systems, 2018,24(7):1653-1670(in Chinese with English abstract).[doi:10.13196/j.cims.2018.07.007]
    [19] Ahmadon MAB, Yamaguchi S. Convertibility and conversion algorithm of well-structured workflow net to process tree. In:Proc. of the 1st Int'l Symp. on Computing and Networking. Matsuyama:IEEE, 2013.122-127.[doi:10.1109/CANDAR.2013.24]
    [20] Zhong CF, He WL, Li ZW, Wu NQ, Qu T. Deadlock analysis and control using Petri net decomposition techniques. Information Sciences:An Int'l Journal, 2019,482:440-456.[doi:10.1016/j.ins.2019.01.029]
    [21] Liu C, Zeng QT, Duan H, Wang L, Tan J, Ren CG, Yu WY. Petri net based data-flow error detection and correction strategy for business processes. IEEE Access, 2020,8:43265-43276.[doi:10.1109/ACCESS.2020.2976124]
    [22] Li YT, Yin L, Chen YF, Yu ZH, Wu NQ. Optimal Petri net supervisor synthesis for forbidden state problems using marking mask. Information Sciences, 2019,505:183-197.[doi:10.1016/j.ins.2019.07.008]
    [23] Leemans SJJ, Fahland D, van der Aalst WMP. Discovering block-structured process models from event logs-A constructive approach. In:Colom JM, Desel J, eds. Proc. of the PETRI NETS 2013:Application and Theory of Petri Nets and Concurrency. Berlin, Heidelberg:Springer-Verlag, 2013.311-329.[doi:10.1007/978-3-642-38697-8_17]
    [24] Leemans SJJ, Fahland D, van der Aalst WMP. Discovering block-structured process models from event logs containing infrequent behaviour. In:Lohmann N, Song M, Wohed P, eds. Proc. of the BPM 2013:Business Process Management Workshops. Cham:Springer Int'l Publishing, 2013.66-78.[doi:10.1007/978-3-319-06257-0_6]
    [25] Esparza J, Römer S, Vogler W. An improvement of McMillan's unfolding algorithm. Int'l Workshop on Tools and Algorithms for the Construction and Analysis of Systems. Berlin:Springer-Verlag, 1996.87-106.[doi:10.1023/A:1014746130920]
    [26] Burattin A, Sperduti A. PLG:A framework for the generation of business process models and their execution logs. In:zur Muehlen M, Su J, eds. Proc. of the BPM 2010:Business Process Management Workshops. Berlin, Heidelberg:Springer-Verlag, 2011.214-219.[doi:10.1007/978-3-642-20511-8_20]
    [27] Polyvyanyy A, García-Bañuelos L, Fahland D, Weske M. Maximal structuring of acyclic process models. Computer Journal, 2014, 57(1):12-37.[doi:10.1093/comjnl/bxs126]
    [28] Tan WA, Xie N, Zhao L, Sun Y, Huang L. Retrieval of business process models based on performance constraints. Computer Integrated Manufacturing Systems, 2019,25(4):847-855(in Chinese with English abstract).[doi:CNKI:SUN:JSJJ.0.2019-04-006]
    [29] Sun JY, Gu TL, Wen LJ, Qian JY. Similarity algorithm for semantic workflows used in process-oriented case-based reasoning. Computer Integrated Manufacturing Systems, 2016,22(2):381-394(in Chinese with English abstract).[doi:10.13196/j.cims.2016.02.011]
    [30] Sun JY, Gu TL, Wen LJ, Qian JY, Meng Y. Retrieval of similar semantic workflows based on behavioral and structural characteristics. Journal of Computer Research and Development, 2017,54(9):1880-1891(in Chinese with English abstract).[doi:10.7544/issn1000-1239.2017.20160755]
    [31] Dong ZH, Wen LJ, Huang HW, Wang JM. Behavioral similarity algorithm for process models based on firing sequence collection. Ruan Jian Xue Bao/Journal of Software, 2015,26(3):449-459(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4765.htm[doi:10.13328/j.cnki.jos.004765]
    [32] Tao J, Wang JM, Wen LJ. Querying business process models based on semantics. In:Yu JX, Kim MH, Unland R, eds. Proc. of the DASFAA 2011:Database Systems for Advanced Applications. Berlin, Heidelberg:Springer-Verlag, 2011.164-178.[doi:10.1007/978-3-642-20152-3_13]
    [33] Polyvyanyy A, RosaArthur ML, ter Hofstede HM. Indexing and efficient instance-based retrieval of process models using untanglings. In:Jarke M, ed. Proc. of the CAiSE 2014:Advanced Information Systems Engineering. Cham:Springer Int'l Publishing, 2014.439-456.[doi:10.1007/978-3-319-07881-6_30]
    [34] Bottrighi A, Canensi L, Leonardi G, Montani S, Terenziani P. Interactive mining and retrieval from process traces. Expert Systems with Applications, 2018,110:62-79.[doi:10.1016/j.eswa.2018.05.041]
    [35] Song W, Jacobsen H, Cheung SC, Liu HY. Workflow refactoring for maximizing concurrency and block-structuredness. IEEE Trans. on Services Computing, 2018. Early Access, 8450038.[doi:10.1109/TSC.2018.2867593]
    附中文参考文献:
    [1] 金涛,闻立杰.业务过程模型库索引技术.计算机集成制造系统,2011,17(8):1580-1586.[doi:10.4028/www.scientific.net/AMR. 154-155.87]
    [12] 朱锐,李彤,莫启,何臻力,于倩,王一荃.数据驱动的双层次软件过程挖掘方法.软件学报,2018,29(11):3455-3483. http://www.jos.org.cn/1000-9825/5304.htm[doi:10.13328/j.cnki.jos.005304]
    [15] Milner R,著;林惠民,柳欣欣,刘佳,屈楠,译.通信与移动系统:π演算.北京:清华大学出版社,2009.
    [18] 朱锐,张志幸,莫启,李彤,马自飞,黎彬.支持复杂结构的混成过程挖掘方法.计算机集成制造系统,2018,24(7):1653-1670.[doi:10.13196/j.cims.2018.07.007]
    [28] 谭文安,谢娜,赵璐,孙勇,黄黎.基于性能约束的业务过程模型检索.计算机集成制造系统,2019,25(4):847-855.[doi:CNKI:SUN:JSJJ.0.2019-04-006]
    [29] 孙晋永,古天龙,闻立杰,钱俊彦.用于面向过程的基于实例推理的语义工作流相似性算法.计算机集成制造系统,2016,22(2):381-394.[doi:10.13196/j.cims.2016.02.011]
    [30] 孙晋永,古天龙,闻立杰,钱俊彦,孟瑜.基于行为和结构特征的相似语义工作流检索.计算机研究与发展,2017,54(9):1880-1891.[doi:10.7544/issn1000-1239.2017.20160755]
    [31] 董子禾,闻立杰,黄浩未,王建民.基于触发序列集合的过程模型行为相似性算法.软件学报,2015,26(3):449-459. http://www.jos.org.cn/1000-9825/4765.htm[doi:10.13328/j.cnki.jos.004765]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

朱锐,黄月,金芝,李彤,汤雅惠.基于完全有限前缀展开的行为等价过程树生成算法.软件学报,2021,32(5):1385-1403

Copy
Share
Article Metrics
  • Abstract:1846
  • PDF: 3912
  • HTML: 1620
  • Cited by: 0
History
  • Received:April 22,2020
  • Revised:August 24,2020
  • Online: December 02,2020
  • Published: May 06,2021
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2032471Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063