Token-based replay
Token-based replay technique is a conformance checking algorithm that checks how well a process conforms with its model by replaying each trace on the model. Using the four counters produced tokens, consumed tokens, missing tokens, and remaining tokens, it records the situations where a transition is forced to fire and the remaining tokens after the replay ends. Based on the count at each counter, we can compute the fitness value between the trace and the model.
The algorithm
Source:The token-replay technique uses four counters to keep track of a trace during the replaying:
- : Produced tokens
- : Consumed tokens
- : Missing tokens
- : Remaining tokens
- At any time:
- At the end:
Example
Suppose there is a process model in Petri net notation as follows:Example 1: Replay the trace () on the model M
- Step 1: A token is initiated. There is one produced token.
- Step 2: The activity consumes 1 token to be fired and produces 2 tokens.
- Step 3: The activity consumes 1 token and produces 1 token.
- Step 4: The activity consumes 1 token and produces 1 token.
- Step 5: The activity consumes 2 tokens and produces 1 token.
- Step 6: The token at the end place is consumed. The trace is complete.
Example 2: Replay the trace (a, b, d) on the model M
- Step 1: A token is initiated. There is one produced token.
- Step 2: The activity consumes 1 token to be fired and produces 2 tokens.
- Step 3: The activity consumes 1 token and produces 1 token.
- Step 4: The activity needs to be fired but there are not enough tokens. One artificial token was produced and the missing token counter is increased by one. The artificial token and the token at place are consumed and one token is produced at place end.
- Step 5: The token in the end place is consumed. The trace is complete. There is one remaining token at place .