Objective: To develop proof strategies to formally study the expressiveness of workflow-based languages, and to investigate their applicability to clinical workflow languages.
Method: We propose two strategies for studying the expressiveness of workflow-based languages based on a standard set of workflow patterns expressed as Petri Nets and notions of congruence and bisimilarity from process calculus. Proof that a Petri Net-based pattern P can be expressed in a language L can be carried out semi-automatically. Proof that a language L cannot provide the behavior specified by a Petri Net P requires proof by exhaustion based on analysis of cases and cannot be performed automatically. The proof strategies are generic but we exemplify their use with a particular clinical workflow language, PROforma. To illustrate the method we evaluate the expressiveness of PROforma against three standard workflow patterns and compare our results with a previous similar but informal comparison.
Results: We show that the two proof strategies are effective in evaluating a workflow language against standard workflow patterns. We find that using the proposed formal techniques we obtain different results to a comparable previously published but less formal study. We discuss the utility of these analyses as the basis for principled extensions to workflow languages. Additionally we explain how the same proof strategies can be reused to prove the satisfaction of patterns expressed in declarative languages based on linear temporal logic.
Conclusion: The proof strategies we propose are useful tools for analysing the expressiveness of clinical workflow languages. This study provides good evidence of the benefits of applying formal methods of proof over semi-formal ones.