Repetición basada en tokens

La técnica de repetición basada en tokens es un algoritmo de verificación de conformidad ^[1] que verifica qué tan bien un proceso se ajusta a su modelo al reproducir cada traza en el modelo (en notación de red de Petri ). ^[2] Utilizando los cuatro contadores de tokens producidos, tokens consumidos, tokens faltantes y tokens restantes, registra las situaciones en las que se fuerza la activación de una transición y los tokens restantes después de que finaliza la repetición. Con base en el recuento en cada contador, podemos calcular el valor de aptitud entre la traza y el modelo.

La técnica de repetición de token utiliza cuatro contadores para realizar un seguimiento de un rastro durante la reproducción:

• p : Tokens producidos
• c : Fichas consumidas
• m : Fichas faltantes (consumidas mientras no estaban allí)
• r : Fichas restantes (producidas pero no consumidas)

Invariantes:

• En cualquier momento:${\displaystyle p+m\geq c\geq m}$
• Al final:${\displaystyle r=p+m-c}$

Al principio, se produce una ficha para el lugar de origen (p = 1) y, al final, se consume una ficha del lugar de destino (c' = c + 1). Cuando termina la repetición, el valor de aptitud se puede calcular de la siguiente manera:

$${\displaystyle {\frac {1}{2}}(1-{\frac {m}{c}})+{\frac {1}{2}}(1-{\frac {r}{p}})}$$

Supongamos que existe un modelo de proceso en notación de red de Petri como sigue:

• Paso 1: se inicia un token. Se produce un token ( ).${\displaystyle p=1}$

• Paso 2: La actividad consume 1 token para ser activada y produce 2 tokens ( y ).${\displaystyle \mathbf {a} }$${\displaystyle p=1+2=3}$${\displaystyle c=1}$

• Paso 3: La actividad consume 1 token y produce 1 token ( y ).${\displaystyle \mathbf {b} }$${\displaystyle p=3+1=4}$${\displaystyle c=1+1=2}$

• Paso 4: La actividad consume 1 token y produce 1 token ( y ).${\displaystyle \mathbf {c} }$${\displaystyle p=4+1=5}$${\displaystyle c=2+1=3}$

  

• Paso 5: La actividad consume 2 tokens y produce 1 token ( , ).${\displaystyle \mathbf {d} }$${\displaystyle p=5+1=6}$${\displaystyle c=3+2=5}$

• Paso 6: El token en el lugar final se consume ( ). El rastreo está completo.${\displaystyle c=5+1=6}$

  

La aptitud de la traza ( ) en el modelo es: ${\displaystyle \mathbf {a,b,c,d} }$${\displaystyle \mathbf {M} }$

$${\displaystyle {\frac {1}{2}}(1-{\frac {m}{c}})+{\frac {1}{2}}(1-{\frac {r}{p}})={\frac {1}{2}}(1-{\frac {0}{6}})+{\frac {1}{2}}(1-{\frac {0}{6}})=1}$$

• Paso 1: se inicia un token. Se produce un token ( ).${\displaystyle p=1}$

• Paso 2: La actividad consume 1 token para ser activada y produce 2 tokens ( y ).${\displaystyle \mathbf {a} }$${\displaystyle p=1+2=3}$${\displaystyle c=1}$

• Paso 3: La actividad consume 1 token y produce 1 token ( y ).${\displaystyle \mathbf {b} }$${\displaystyle p=3+1=4}$${\displaystyle c=1+1=2}$

• Paso 4: La actividad debe iniciarse pero no hay suficientes tokens. Se produjo un token artificial y el contador de tokens faltantes se incrementa en uno ( ). El token artificial y el token en el lugar se consumen ( ) y se produce un token en el lugar final ( ).${\displaystyle \mathbf {d} }$${\displaystyle m=1}$${\displaystyle [\mathbf {b,d} ]}$${\displaystyle c=2+2=4}$${\displaystyle p=4+1=5}$

  

• Paso 5: El token en el lugar final se consume ( ). El rastreo está completo. Queda un token restante en el lugar ( ).${\displaystyle c=4+1=5}$${\displaystyle [\mathbf {a,c} ]}$${\displaystyle r=1}$

La aptitud de la traza ( ) en el modelo es: ${\displaystyle \mathbf {a,b,d} }$${\displaystyle \mathbf {M} }$

$${\displaystyle {\frac {1}{2}}(1-{\frac {m}{c}})+{\frac {1}{2}}(1-{\frac {r}{p}})={\frac {1}{2}}(1-{\frac {1}{5}})+{\frac {1}{2}}(1-{\frac {1}{5}})=0.8}$$