关键词: Petri网, 相似性度量, 可覆盖图, 编辑距离, A*匹配算法

Abstract: Aiming at the problem that the calculating result of behavioral similarity measures was inaccurate and inefficiency in existing process models,an approach named Transition-labeled Graph Edit Distance(TAGER) to compute the similarity based on edit distance between coverability graphs was proposed.Through defining the transition-labeled graph,the behaviors of process models was expressed.The computing method of graph edit operations and graph edit distance according to behavioral features was refined.The matching optimal scheme between nodes of two T-labeled graphs was calculated with A* algorithm.Through the satisfied rate and average time cost of triangle inequality,TAGER from efficiency and efficacy perspectives was evaluated,and an experimental comparison between TAGER and other mainstream similarity algorithms was completed.

Key words: Petri nets, similarity measure ment, coverability graph, edit distance, A*algorithm