Alpha algorithm: Difference between revisions

Revision as of 18:12, 6 August 2011

Revision as of 20:44, 19 May 2012

Line 1:

<!--- not to be confused with alpha-beta or with alpha-shapes --->

The '''α-algorithm''' is an algorithm used in [[process mining]], aimed at reconstructing causality from a set of [[sequence of events|sequences of events]].

It was first put forward by [[Wil van der Aalst|van der Aalst]], Weijter and Măruşter .<ref>van der Aalst, W M P and Weijter, A J M M and Maruster, L (2003). "Workflow Mining: Discovering process models from event logs", ''IEEE Transactions on Knowledge and Data Engineering'', vol 16</ref>. Several extensions or modifications of it have since been presented, which will be listed below.

It constructs [[petri nets|P/T nets]] with special properties ([[workflow net]]s) from event logs (as might be collected by an [[Enterprise resource planning|ERP]] system). Each transition in the net corresponds to an observed task.

Line 32:

<!--- as would be the result of merging --->

* <math>Y_W</math> is the set of all pairs <math>(A,B)</math> of maximal sets of tasks such that

:** Neither <math>A \times A</math> and <math>B \times B</math> contain any members of <math>\succ_W</math> and

:** <math>A \times B</math> is a subset of <math>\rightarrow_W</math>

* <math>P_W</math> contains one place <math>p_{(A,B)}</math> for every member of <math>Y_W</math>, plus the input place <math>i_W</math> and the output place <math>o_W</math>