Simplified Computation and Generalization of the Refined Process Structure Tree (Revised version of July 20, 2010)

A business process is often modeled using some kind of a directed flow graph, which we call a workflow graph. The Refined Process Structure Tree (RPST) [1] is a technique for workflow graph parsing, i.e., for detecting the structure of a workflow graph, which has various applications. In this paper, we provide two improvements to the RPST. First, we propose an alternative way to compute the RPST that is simpler than the one developed originally [1]. In particular, the computation reduces to constructing the tree of the triconnected components of a workflow graph in the special case when every node has at most one incoming or at most one outgoing edge. Such graphs occur frequently in applications. Secondly, we extend the applicability of the RPST. Originally, the RPST was applicable to graphs with a single source and single sink such that the completed version of the graph is biconnected. We lift both restrictions. Therefore, the RPST is then applicable to arbitrary directed graphs such that every node is on a path from some source to some sink. This includes graphs with multiple sources and/or sinks and disconnected graphs.
[1] Vanhatalo, J., Voelzer, H., Koehler, J.: The refined process structure tree. Data & Knowledge Engineering 68(9) (2009) 793–818

A shortened version of this paper appears in "Web Services and Formal Methods," Proc. 7th Int'l Workshop on Web Services and Formal Methods "WS-FM," Hoboken, NJ, September 2010, Lecture Notes in Computer Science, vol. 6551, (Springer, 2011), pp. 25-41.