1. A computer program residing on a computer-readable storage medium, comprising instructions for causing a computer system to implement steps for analyzing a control-flow in a business process, the steps comprising: invoking a representation of the business process as an acyclic workflow graph containing a plurality of types of nodes and edges linking nodes of the graph; labeling edges of the graph such that a label assigned to a first edge comprises a plurality of edge identifiers identifying respective edges, each of the edges identified being an outgoing edge of a split node in the graph, whereby executing any one of the identified edges ensures that the first edge will be executed; and checking the labels for a deadlock using a processor, while labeling the edges of the graph, wherein a deadlock is found if a condition for relaxed soundness is true.