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.

By: Artem Polyvyanyy, Jussi Vanhatalo and Hagen Voelzer

Published in: RZ3745 in 2009


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .