Alpha algorithm: Difference between revisions

Revision as of 22:58, 10 May 2010

Revision as of 09:02, 20 May 2010

Line 3:

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|workflow nets]]s) from event logs (as might be collected by an [[ERP]] system). Each transition in the net corresponds to an observed task.

== Short description ==

Line 52:

It can be shown <ref>van der Aalst et al. 2003</ref> 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 <math>\succ_W</math> 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 <ref>A. de Medeiros, A K and van der Aalst, W M P and Weijters, A J M M (2003). "Workflow Mining: Current Status and Future Directions". in: "volume 2888 of Lecture Notes in Computer Science", Springer-Verlag</ref> which the α-algorithm cannot rediscover.

{{Expand section|date=May stub2010}}

Constructing <math>Y_W</math> takes exponential time in the number of tasks, since <math>\succ_W</math> is not constrained and arbitrary subsets of <math>T_W</math> must be considered.

Line 63 ⟶ 62:

== Extensions ==

{{Expand section|date=May stub2010}}

for example <ref name="extending_the">A. de Medeiros, A K and van Dongen, B F and van der Aalst, W M P and Weijters, A J M M (2004). "Process mining: extending the α-algorithm to mine short loops"</ref>

<ref name="wen2007mining">Wen, L and van der Aalst, W M P and Wang, J and Sun, J (2007). "Mining process models with non-free-choice constructs",

Line 72 ⟶ 71:

<!--- Categories --->

[[Category:Articles created via the Article Wizard]]

[[Category:Algorithms]]

<!--- [[de:Alpha-Algorithmus]] --->

<!--- [[fr:Algorithme alpha]] --->

{{DEFAULTSORT:Alpha Algorithm}}

[[Category:Articles created via the Article Wizard]]

[[Category:Algorithms]]