## 3 Deadlock Prevention Policy for Reconfigurable S\({}^{3}\)PR Net Based on Siphons  
This section presents definitions on siphons in reconfigurable S\({}^{3}\)PR nets. Next, the siphon control method based on place invariants is introduced. Finally, a deadlock prevention algorithm is proposed to solve the deadlock problems in reconfigurable S\({}^{3}\)PR nets. **Definition 29**. : _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 place vector of \(N_{1}\) is expressed as a column vector I: \(P_{C1}\)\(\rightarrow\)\(\mathbf{Z}\) indexed by \(P_{C1}\), and a transition vector of \(N_{1}\) is defined as a column vector J: \(T_{1}\rightarrow\)\(\mathbf{Z}\) indexed by \(T_{1}\), where \(\mathbf{Z}\) = \(\{\)..., \(-2\), \(-1\), \(0\), \(1\), \(2\),... \(\}\)._  
**Definition 30**. : _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 place vector I of \(N_{1}\) is expressed as a place invariant (PI) if I\({}^{T}\). [\(N_{1}\)] = \(\mathbf{0}^{T}\) and I \(\
eq\)\(\mathbf{0}\), and a transition vector of \(N_{1}\) is defined as a transition invariant (TI) if [\(N_{1}\)]. J = \(\mathbf{0}\) and J \(\
eq\)\(\mathbf{0}\)._  
Figure 6: A reconfigured S\({}^{3}\)PR net by addition of a new robot. (**a**) Left hand side net \(L\). (**b**) Right hand side net \(R\). (**c**) A reconfigurable S\({}^{3}\)PR net (\(N_{4}\), \(M_{4o}\)). **Definition 31**. : _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 place invariant 1 of \(N_{1}\) is expressed as a place semi-flow if each element of 1 is non-negative. \(||||=\{p\ |I(p)\
eq 0\}\) is said to be the support of place invariant of 1. \(||||^{+}=\{p\ |I(p)>0\}\) is said to be the positive support of place invariant 1. \(||||^{-}=\{p\ |I(p)<0\}\) is said to be the negative support of place invariant 1. \(I\) is a minimal place invariant if \(||||\) is not a superset of the support of any other one and its components are mutually prime._  
**Definition 32**. : _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 transition invariant 1 of \(N_{1}\) is expressed as a transition semi-flow if each element of 1 is non-negative. \(||||=\{t\ |J(t)\
eq 0\}\) is said to be the support of transition invariant of 1. \(||||^{+}=\{t\ |J(t)>0\}\) is said to be the positive support of transition invariant 1. \(||||^{-}=\{t\ |J(t)<0\}\) is said to be the negative support of transition invariant 1. \(||||\) is not a superset of the support of any other one, and its components are mutually prime._  
**Definition 33**. : _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}\)). \(l_{i}\) is said to be the coefficients of place invariant 1 if for all \(p_{i}\in P_{C1}\), \(l_{i}=l(p_{i})\)._  
**Definition 34**. : _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 non-empty set \(S\subseteq P_{C1}\) is called a siphon in \(N_{1}\) if \({}^{\bullet}S\subseteq{}^{\bullet}\). \(S\subseteq P_{C1}\) is called a trap in \(N_{1}\) if \(S{}^{\bullet}\subseteq{}^{\bullet}\).