The α-algorithm is an algorithm used in process mining

Process mining

Process mining is a process management technique that allows for the analysis of business processes based on event logs. The basic idea is to extract knowledge from event logs recorded by an information system...

, aimed at reconstructing causality from a set of sequences of events.
It was first put forward by van der Aalst

Wil van der Aalst

Wil M.P. van der Aalst is a Dutch computer scientist, and professor at the Department of Mathematics & Computer Science of the Technische Universiteit Eindhoven, where he chairs the Architecture of Information Systems group, His research and teaching interests include information systems, workflow...

, Weijter 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 (workflow nets) from event logs (as might be collected by an ERP

Enterprise resource planning

Enterprise resource planning systems integrate internal and external management information across an entire organization, embracing finance/accounting, manufacturing, sales and service, customer relationship management, etc. ERP systems automate this activity with an integrated software application...

 system). 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

• A workflow trace or execution trace is a string
  String (computer science)
  In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
  
   over an alphabet  of tasks.
• A workflow log is a set of workflow traces.

Description

Declaratively, the algorithm can be presented as follows.
Three sets of tasks are determined:

• is the set of all tasks which occur in at least one trace
• is the set of all tasks which occur trace-initially
• is the set of all tasks which occur trace-terminally

Basic ordering relations are determined ( first, the latter three can be constructed therefrom)

• iff b directly precedes a in some trace
• iff
• iff
• iff

Places are discovered. Each place is identified with a pair of sets of tasks, in order to keep the number of places low.

• is the set of all pairs of maximal sets of tasks such that
• Neither and contain any members of and
• is a subset of
• contains one place for every member of , plus the input place and the output place

The flow relation is the union of the following:

• 
• 
• 
• 

The result is

• a petri net
  Petri net
  A Petri net is one of several mathematical modeling languages for the description of distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions and places...
  
   structure
• with one input place and one output place
• because every transition of is on a -path from to , it is indeed a workflow net.

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 relation is maximal. It is not required that all possible traces be present (which would be countably infinite for a net with a loop).

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.