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.
Contents
It constructs P/T nets with special properties (workflow nets) from event logs (as might be collected by an ERP system). Each transition in the net corresponds to an observed task.
Short description
The algorithm takes a workflow log
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
Description
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
The result is
Properties
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
Limitations
General workflow nets may contain several types of constructs which the α-algorithm cannot rediscover.
Constructing
Extensions
for example