A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> State space methods are one of the most important approaches to computer-aided analysis and verification of the behaviour of concurrent systems. In their basic form, they consist of enumerating and analysing the set of the states the system can ever reach. Unfortunately, the number of states of even a relatively small system is often far greater than can be handled in a realistic computer. The goal of this article is to analyse this state explosion problem from several perspectives. Many advanced state space methods alleviate the problem by using a subset or an ion of the set of states. Unfortunately, their use tends to restrict the set of analysis or verification questions that can be answered, making it impossible to discuss the methods without some taxonomy of the questions. Therefore, the article contains a lengthy discussion on alternative ways of stating analysis and verification questions, and algorithms for answering them. After that, many advanced state space methods are briefly described. The state explosion problem is investigated also from the computational complexity point of view. <s> BIB001 </s> A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> Contemporary workflow management systems are driven by explicit process models, i.e., a completely specified workflow design is required in order to enact a given workflow process. Creating a workflow design is a complicated time-consuming process and, typically, there are discrepancies between the actual workflow processes and the processes as perceived by the management. Therefore, we have developed techniques for discovering workflow models. The starting point for such techniques is a so-called "workflow log" containing information about the workflow process as it is actually being executed. We present a new algorithm to extract a process model from such a log and represent it in terms of a Petri net. However, we also demonstrate that it is not possible to discover arbitrary workflow processes. We explore a class of workflow processes that can be discovered. We show that the /spl alpha/-algorithm can successfully mine any workflow represented by a so-called SWF-net. <s> BIB002 </s> A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> Business processes continue to play an important role in todayâ€™s service-oriented enterprise computing systems. Mining, discovering, and integrating process-oriented services has attracted growing attention in the recent years. In this article, we present a quantitative approach to modeling and capturing the similarity and dissimilarity between different process designs. We derive the similarity measures by analyzing the process dependency graphs of the participating workflow processes. We first convert each process dependency graph into a normalized process matrix. Then we calculate the metric space distance between the normalized matrices. This distance measure can be used as a quantitative and qualitative tool in process mining, process merging, and process clustering, and ultimately it can reduce or minimize the costs involved in design, analysis, and evolution of workflow systems. <s> BIB003 </s> A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> BPEL has emerged as the industrial standard language for modelling behavioral aspects of web services. To support business partners in dynamically and flexibly binding their services together, different BPEL processes need to be efficiently matched. This paper identifies and defines various types of structural matching for BPEL processes. The matching definitions are based on heuristics: they take behavioral interaction aspects of the compared services into account, but abstract from irrelevant syntactical differences. Since the definitions are structural, they can be efficiently computed, and thus are useful to support dynamic and flexible binding of services. The approach is illustrated with an example from an existing business scenario. <s> BIB004 </s> A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> Similarity search is a general class of problems in which a given object, called a query object, is compared against a collection of objects in order to retrieve those that most closely resemble the query object. This paper reviews recent work on an instance of this class of problems, where the objects in question are business process models. The goal is to identify process models in a repository that most closely resemble a given process model or a fragment thereof. <s> BIB005 </s> A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> We investigate the problem of ranking all process models in a repository according to their similarity with respect to a given process model. We focus specifically on the application of graph matching algorithms to this similarity search problem. Since the corresponding graph matching problem is NP-complete, we seek to find a compromise between computational complexity and quality of the computed ranking. Using a repository of 100 process models, we evaluate four graph matching algorithms, ranging from a greedy one to a relatively exhaustive one. The results show that the mean average precision obtained by a fast greedy algorithm is close to that obtained with the most exhaustive algorithm. <s> BIB006 </s> A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> Many activities in business process management, such as process retrieval, process mining, and process integration, need to determine the similarity or the distance between two processes. Although several approaches have recently been proposed to measure the similarity between business processes, neither the definitions of the similarity notion between processes nor the measure methods have gained wide recognition. In this paper, we define the similarity and the distance based on firing sequences in the context of workflow nets (WF-nets) as the unified reference concepts. However, to many WF-nets, either the number of full firing sequences or the length of a single firing sequence is infinite. Since transition adjacency relations (TARs) can be seen as the genes of the firing sequences which describe transition orders appearing in all possible firing sequences, we propose a practical similarity definition based on the TAR sets of two processes. It is formally shown that the corresponding distance measure between processes is a metric. An algorithm using model reduction techniques for the efficient computation of the measure is also presented. Experimental results involving comparison of different measures on artificial processes and evaluations on clustering real-life processes validate our approach. <s> BIB007 </s> A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> A business process often shows different variations in a large organisation, due to different legal requirements in different countries, deviations in the IT infrastructure, or organisational differences. These variants are documented in separate independent process models. Management of these variants imposes various challenges. Invariant behaviour needs to be identified and redundancies among the variants have to be avoided. In this paper, we address these questions by defining a setalgebra for behavioural profiles. These profiles represent a behavioural abstraction of process models that can be computed efficiently. We trace back many questions of process variability management to set-theoretic operations and relations defined for behavioural profiles. As a validation, we apply our approach to an industry model collection. <s> BIB008 </s> A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> Engineering of process-driven business applications can be supported by process modeling efforts in order to bridge the gap between business requirements and system specifications. However, diverging purposes of business process modeling initiatives have led to significant problems in aligning related models at different abstract levels and different perspectives. Checking the consistency of such corresponding models is a major challenge for process modeling theory and practice. In this paper, we take the inappropriateness of existing strict notions of behavioral equivalence as a starting point. Our contribution is a concept called behavioral profile that captures the essential behavioral constraints of a process model. We show that these profiles can be computed efficiently, i.e., in cubic time for sound free-choice Petri nets w.r.t. their number of places and transitions. We use behavioral profiles for the definition of a formal notion of consistency which is less sensitive to model projections than common criteria of behavioral equivalence and allows for quantifying deviation in a metric way. The derivation of behavioral profiles and the calculation of a degree of consistency have been implemented to demonstrate the applicability of our approach. We also report the findings from checking consistency between partially overlapping models of the SAP reference model. <s> BIB009 </s> A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> Analysis of behavioural consistency is an important aspect of software engineering. In process and service management, consistency verification of behavioural models has manifold applications. For instance, a business process model used as system specification and a corresponding workflow model used as implementation have to be consistent. Another example would be the analysis to what degree a process log of executed business operations is consistent with the corresponding normative process model. Typically, existing notions of behaviour equivalence, such as bisimulation and trace equivalence, are applied as consistency notions. Still, these notions are exponential in computation and yield a Boolean result. In many cases, however, a quantification of behavioural deviation is needed along with concepts to isolate the source of deviation. In this article, we propose causal behavioural profiles as the basis for a consistency notion. These profiles capture essential behavioural information, such as order, exclusiveness, and causality between pairs of activities of a process model. Consistency based on these profiles is weaker than trace equivalence, but can be computed efficiently for a broad class of models. In this article, we introduce techniques for the computation of causal behavioural profiles using structural decomposition techniques for sound free-choice workflow systems if unstructured net fragments are acyclic or can be traced back to S- or T-nets. We also elaborate on the findings of applying our technique to three industry model collections. <s> BIB010 </s> A Short Survey on Process Model Similarity <s> Underlying Notions for Process Model Similarity Calculation <s> With the increasing influence of Business Process Management, large process model repositories emerged in enterprises and public administrations. Their effective utilization requires meaningful and efficient capabilities to search for models that go beyond text based search or folder navigation, e.g., by similarity. Existing measures for process model similarity are often not applicable for efficient similarity search, as they lack metric features. In this paper, we introduce a proper metric to quantify process similarity based on behavioral profiles. It is grounded in the Jaccard coefficient and leverages behavioral relations between pairs of process model activities. The metric is successfully evaluated towards its approximation of human similarity assessment. <s> BIB011
Most approaches for process similarity are based on either the process model's graph structure or the behaviour captured in the model BIB005 . Similarity is typically quantified by symmetric and non-negative distance functions that capture the amount of differences a pair of process models exposes. Accordingly, two process models are identical if their distance equals 0. The process model graph plus the execution semantics of its elements prescribe the allowed behaviour of the process, which is typically analysed by means of reachability graphs or the set of allowed execution traces. The problem of calculating the similarity of two process models based on both these options is that both approaches suffer from exponential complexity due to concurrency and loops in the process model BIB001 . Hence, abstractions have been proposed that only consider the order in which two activities can be executed in any process instance BIB002 . Two variants are (1) the transition adjacency relation BIB003 BIB007 that consider pairs of activities that can be executed directly after each other (non-transitive) and (2) weak order relations BIB004 BIB008 which consider any pair of activities that can be executed after each other eventually (transitive). An extension of the latter are behavioural profiles, which distinguish these relations by mutual exclusion, strict, and interleaving order BIB009 BIB010 . Although these relations abstract from certain behavioural aspects, e.g., causality and cardinality, they have been shown to support the human assessment of process model similarity BIB011 . Higher precision can be achieved based on event structures which yield a matrix of relations that fully characterizes a model in terms of a strong notion of behavioral equivalence  . An alternative to a notion of distance based on behavioural relations is graph edit distance BIB006 . The graph edit distance is the minimum number of basic graph operations that is needed to transform one graph into another. The basic operations are: add node, remove node, add edge and remove edge. In labelled graphs, node substitution can also be used as an operation, in which one node is substituted by another node with a different label. The graph edit distance can be transformed into a similarity metric in different ways, e.g., by dividing the distance by the number of nodes and edges of the largest graph and using one minus the result of that.