The representation,analysis and verification of business processes: a metagraph-based approach

Business processes can be modeled using a variety of schemes such as Petri Nets, Metagraphs and UML Activity Diagrams. When information analysis is as important an objective as the proper sequencing of tasks, the metagraph formalism is the most appropriate. In practice, however, metagraphs have not achieved wide popularity. Here we propose a modification of the original formulation that eliminates some of the inconveniences that have hindered the use of this technique. We represent a business process as a Task-Precedence Metagraph (TPMG), which is a type of AND/OR graph. A TPMG is similar to a metagraph but is visually clearer and more appealing, and the algorithmic procedures are graphical rather than algebraic. We first describe the proposed representation scheme for TPMGs and present a simple graph-search algorithm for the analysis of information flow. This can be readily extended to perform task analysis, resource analysis, and operational (i.e., semantic) verification. We then present a generalized graphical algorithm for structural (i.e., syntactic) verification that runs correctly not only on TPMGs containing directed cycles, but even on those that have overlapping patterns. Editor-in-Chief’s Note: An earlier version of this paper was accepted for WITS2004. The authors were subsequently invited to submit an expanded paper for publication consideration in Information Technology and Management. The conference co-chairs, Professors Amit Dutta and Paulo Goes were the guest editors for this paper.