Alpha algorithm


The α-algorithm is an algorithm used in process mining, aimed at reconstructing causality from a set of sequences of events.
It was first put forward by van der Aalst, Weijters and Măruşter. Several extensions or modifications of it have since been presented, which will be listed below.
It constructs P/T nets with special properties from event logs. Each transition in the net corresponds to an observed task.

Short description

The algorithm takes a workflow log as input and results in a workflow net being constructed.
It does so by examining causal relationships observed between tasks. For example, one specific task might always precede another specific task in every execution trace, which would be useful information.

Definitions used

Declaratively, the algorithm can be presented as follows.
Three sets of tasks are determined:
Basic ordering relations are determined
Places are discovered. Each place is identified with a pair of sets of tasks, in order to keep the number of places low.
The flow relation is the union of the following:
The result is
It can be shown that in the case of a complete workflow log generated by a sound SWF net, the net generating it can be reconstructed. Complete means that its relation is maximal. It is not required that all possible traces be present.

Limitations

General workflow nets may contain several types of constructs which the α-algorithm cannot rediscover.
Constructing takes exponential time in the number of tasks, since is not constrained and arbitrary subsets of must be considered.

Extensions

for example