Alpha algorithm: Difference between revisions

Revision as of 13:14, 13 April 2010

Revision as of 14:07, 13 April 2010

Line 12:

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.

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.

=== Definitions used ===

* A '''workflow trace''' or '''execution trace''' is a [[String (computer science)|string]] over an [[alphabet (computer science)|alphabet]] <math>T</math> of ''tasks''.

* A '''workflow log''' is a set of workflow traces.

* A '''complete workflow log''' of a workflow net <math>N</math> is the set of firing sequences of <math>(N,m_i)</math> resulting in the end marking <math>m_o</math>.

<!--- need definitions of SWF net etc. --->

Line 51 ⟶ 48:

* a petri net structure <math>\alpha(W) = (P_W,T_W,F_W)</math>

* with one input place <math>i_W</math> and one output place <math>o_W</math>

<!--- show: which is indeed always a workflow net because there is always a <math>F_W</math>-path from <math>i_W</math> through every transition to <math>o_W</math> --->

== Properties ==

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. The definition of a complete workflow log is as follows:

<!--- * a '''complete workflow log''' of a --->

<!--- consequence: short loops never coour. --->