TAR~*:an improved process similarity measure based on unfolding of Petri nets  

作　　者：WANG Wen-xing WANG Jian-min 

机构地区：[1]School of Software, Tsinghua University, Beijing 100084, China [2]Ministry of Education Key Laboratory for Information System Security, Tsinghua University,Beijing 100084, China [3]Tsinghua National Laboratory for Information Science and Technology, Beijing 100084, China

出　　处：《计算机集成制造系统》2012年第8期1774-1784,共11页Computer Integrated Manufacturing Systems

基　　金：Project supported by the National Science Foundation,China(No.61003099);the National Basic Research Program,China(No.2009CB320700)

摘　　要：Determining the similarity degree between process models was very important for their management,reuse,and analysis.Current approaches either focused on process model's structural aspect,or had inefficiency or imprecision in behavioral similarity.Aiming at these problems,a novel similarity measure which extended an existing method named Transition Adjacent Relation(TAR) with improved precision and efficiency named TAR * was proposed.The ability of measuring similarity was extended by eliminating the duplicate tasks without impacting the behaviors.For precision,TARs was classified into repeatable and unrepeatable ones to identify whether a TAR was involved in a loop.Two new kinds of TARs were added,one related to the invisible tasks after the source place and before sink place,and the other representing implicit dependencies.For efficiency,all TARs based on unfolding instead of its reach ability graph of a labeled Petri net were calculated to avoid state space explosion.Experiments on artificial and real-world process models showed the effectiveness and efficiency of the proposed method.Determining the similarity degree between process models was very important for their management, reuse, and analy- sis. Current approaches either focused on process model＇s structural aspect, or had inefficiency or imprecision in behavioral simi- larity. Aiming at these problems, a novel similarity measure which extended an existing method named Transition Adjacent Rela- tion （TAR） with improved precision and efficiency named TAR＂ was proposed. The ability of measuring similarity was extended by eliminating the duplicate tasks without impacting the behaviors. For precision, TARs was classified into repeatable and unre- peatable ones to identify whether a TAR was involved in a loop. Two new kinds of TARs were added, one related to the invisible tasks after the source place and before sink place, and the other representing implicit dependencies. For efficiency, all TARs based on unfolding instead of its reach ability graph of a labeled Petri net were calculated to avoid state space explosion. Experi- ments on artificial and real-world process models showed the effectiveness and effieienev of the DrODosed method_

关 键 词：transition adjacent relation UNFOLDING Petri nets behavioral similarity 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]