How do you compare different workflow specification languages such as the business process execution language (BPEL) or business process modeling notation (BPMN), given their utterly different notations and dissimilar execution semantics? This theoretical paper offers one possible and very early step toward showing how such a comparison might work.

The authors model workflow and workflow execution as a potentially infinite tree of possible runs of the workflow system. The nodes of the tree represent states of the system and the edges represent events. In this representation, two different workflows are isomorphic if a variant of bisimulation (well known in process algebras) holds. This notion of equivalence, however, is far too strong to compare real languages such as BPEL or BPMN. The authors introduce “views” to relax this condition. Views map the full workflow tree to a new and (usually) smaller model of states and events intuitively representing observable information. Equivalence of the original workflow systems is then defined as bisimulation equivalence of the views only.

The paper uses three artificial workflow specification languages, extensions of the (earlier) basic active Extensible Markup Language (XML) model of one of the authors (Abiteboul), to model automata, languages with guards, and languages representing linear temporal logic. Their comparison yields exact results concerning which language is “stronger” (that is, more expressive), but these results are not highly interesting. They also show that some languages may not be compared at all in certain types of views.

Using many examples and figures, the authors have produced an extensive, highly theoretical treatise, including proofs of lemmas and theorems of their method that are easily accessible to an active researcher fluent in the concepts of theoretical workflow, language modeling, or process algebras.