## 3 Deadlock Prevention Policy for Reconfigurable S\({}^{3}\)PR Net Based on Siphons
\(S\subseteq P_{C1}\) is called a minimal siphon (trap) if a siphon (trap) contains no other siphons. \(A\) minimal siphon \(S\) is called a strict minimal siphon if \(S{}^{\bullet}\subseteq{}^{\bullet}S\). Let \(\Pi\) = {\(S_{1}\), \(S_{2}\), \(S_{3}\), \(\ldots\), \(S_{k}\)} be a set of strict minimal siphons of \(N_{1}\). We have \(S\)= \(S_{A}\cup S_{R}\), \(S_{R}\) = \(S\cap P_{R}\), and \(S_{A}\) = \(S\backslash S_{R}\), where \(S_{A}\) and \(S_{R}\) are sets of operations and resources places, respectively._  
**Definition 35**. : _Let \(N_{R}\) be a reconfigurable \(S^{3}\)PR net with \(N_{R}\) = ((\(N\), \(M_{o}\)), \(\mathcal{R}\)). Let \(N_{1}\) be a state of \(N_{R}\) with \(N_{1}\) = (\(P_{C1}\), \(T_{1}\), \(F_{1}\), \(W_{1}\), \(M_{1o}\), \(K_{1}\)). A siphon \(S\) in \(N_{1}\) is called marked at marking \(M\) if \(\sum_{p\in S}M(p)\geq 1\), and otherwise is called unmarked at marking \(M\)._  
**Definition 36**. : _Let \(N_{R}\) be a reconfigurable \(S^{3}\)PR net with \(N_{R}\) = ((\(N\), \(M_{o}\)), \(\mathcal{R}\)). Let \(N_{1}\) be a state of \(N_{R}\) with \(N_{1}\) = (\(P_{C1}\), \(T_{1}\), \(F_{1}\), \(W_{1}\), \(M_{1o}\), \(K_{1}\)). A siphon \(S\) in \(N_{1}\) is called an emptable siphon if there exists \(M\in R(N_{1}\), \(M_{1o}\)) such that \(\sum_{p\in S}M(p)=0\), and otherwise is called non-emptiable siphon._  
**Theorem 4**. : _Let \(N_{R}\) be a reconfigurable \(S^{3}\)PR net with \(N_{R}\) = ((\(N\), \(M_{o}\)), \(\mathcal{R}\)). Let \(N_{1}\) be a state of \(N_{R}\) with \(N_{1}\) = (\(P_{C1}\), \(T_{1}\), \(F_{1}\), \(W_{1}\), \(M_{1o}\), \(K_{1}\)) and \(\Pi\) the set of \(N_{1}\) siphons. The net \(N_{1}\) is deadlock-free if for all \(S\in\Pi\), for all \(M\in R(N_{1}\), \(M_{1o}\)), \(\sum_{p\in S}M(p)\geq 1\)._  
**Proof**. : Let \(S\) be a siphon in \(N_{1}\) and \(p\in S\). \(p\) is marked at marking \(M\) and satisfies \(\sum_{p\in S}M(p)\geq 1\). The net \(N_{1}\) has at least one transition \(t\) enabled at any marking reachable from \(M\) and \(S\) is never be an unmarked, and it is therefore deadlock-free. **Theorem 5**. : _Let \(N_{R}\) be a reconfigurable \(S^{3}\)PR net with \(N_{R}\) = ((\(N\), \(M_{o}\)), \(\mathcal{R}\)). Let \(N_{1}\) be a state of \(N_{R}\) with \(N_{1}\) = (\(P_{C1}\), \(T_{1}\), \(F_{1}\), \(W_{1}\), \(M_{1o}\), \(K_{1}\)) and \(\Pi\) the set of \(N_{1}\) siphons. The net (\(N_{1}\), \(M_{1o}\)) is in a deadlock state, i.e., \(M\) is a dead marking of \(N_{1}\). Then, \(\{p\in P_{C1}|M(p)=0\}\) is a siphon \(S\)._  
**Proof**. : Since \(M\) is a dead marking, each \(t\) has an empty input place \(p\) at \(M\), \(\forall p\in{}^{\bullet}t\), \(M(p)<W(p\), \(t)\), and thus \(S{}^{\bullet}\) includes each transition of \(N_{1}\). In fact, we have \({}^{\bullet}S\subseteq S^{\bullet}\). Therefore, \(S\) is a siphon. Since the net has at least one transition \(t\in T_{1}\), \(S\) is not an empty set. **Corollary 3**. : _Let \(N_{R}\) be a reconfigurable \(S^{3}\)PR net with \(N_{R}\) = ((\(N\), \(M_{o}\)), \(\mathcal{R}\)). Let \(N_{1}\) be a state of \(N_{R}\) with \(N_{1}\) = (\(P_{C1}\), \(T_{1}\), \(F_{1}\), \(W_{1}\), \(M_{1o}\), \(K_{1}\)), a deadlocked \(N_{1}\) net includes at least one unmarked siphon \(S\)._  
**Corollary 4**. : _Let \(N_{R}\) be a reconfigurable \(S^{3}\)PR net with \(N_{R}=\) ((\(N,M_{o}\)), \(\mathcal{R}\)). Let \(N_{I}\) be a state of \(N_{R}\) with \(N_{I}=\) (\(P_{C\!I}\), \(T_{I}\), \(F_{I}\), \(W_{I}\), \(M_{1o}\), \(K_{I}\)), \(N_{I}\) is a deadlocked net at marking \(M\). Then, \(N_{I}\) has at least one unmarked siphon \(S\) such that for all \(p\in S\), there exists \(t\in p^{\bullet}\) such that \(W_{I}(p,t)>M(p)\)._  
To develop a deadlock prevention policy for reconfigurable S\({}^{3}\)PR net, we reviewed the approach of designing a control place (monitor) for a place invariant developed by [PERSON] et al. [40]. Then we develop a deadlock prevention policy for reconfigurable S\({}^{3}\)PR net to achieve an optimal place invariant. [PERSON] et al.