Get Minimal Siphon (Deadlock) Algorithm
20/3/2014
CE-653 - PTnet Theory and some
Algorithms
22
}N = (P, T, F) strongly-connected FC-Net with p in P
}D is minimal deadlock D ≤ P, containing P
}To be an S-Component, minimal deadlock D must satisfy:
}It is strongly connected
}For all t in D: |•t∩D| = |t•∩D| = 1
Algorithm
Get_Minimal_Deadlock(P, T, F, p, D, Td)
Pc = {p}; Tc = 0; // current sets of Places and
Transitions
while (there exists p’ in Pc,
there exists t in •p’ and t not in Tc)
{
H = Get_Handle((Pc U
Tc), (P U T)-(Pc U Tc), F, p’, t);
Pc = Pc U (H ∩
P); // discard multiple instances of places
Tc = Tc U (H ∩
T); // and transitions
}
D = Pc; Td = Tc;
return D, Tc; // return Deadlock
places and transitions