## 4 Dependency Relation and Dependent Shrink
### Dependent Strink  
**Definition 10**. : _Let \(PN=(T,P,E,\alpha,\beta)\) be a retention-free Petri net._  
1. _Let_ \(T_{x}\) _be a subset of_ \(T\)_, where_ \(x\) _(_\(1\leq x\leq|T|\)_) is a positive integer, and all of the transitions in_ \(T_{x}\) _satisfy a dependency relation. A Petri net induced by_ \(T_{x}\) _is defined as_ \(PN_{x}=(T_{x},P_{x},E_{x},\alpha,\beta)\)_, where_ \(P_{x}=\{p|p\in^{\bullet}t\cup t^{\bullet},t\in T_{x}\}\)_, and_ \(E_{x}=\{e|e\in T_{x}\times P_{x}\cup P_{x}\times T_{x}\}\)_._
2. _The transformation of_ \(PN_{x}\) _by constructing all transitions of_ \(T_{x}\) _and any place_ \(p\in P_{x}\) _satisfying_ \({}^{\bullet}p\cup p^{\bullet}\subset T_{x}\) _into a single transition, denoted by_ \(t_{x}\)_, is called a dependent shrink. In addition, the resultant net_ \(PN^{\prime}=(T^{\prime},P^{\prime},E^{\prime},\alpha,\beta)\) _transformed from_ \(PN\) _is called a dependent shrunk net, where,_ \(T^{\prime}=T-T_{x}+t_{x}\)_,_ \(P^{\prime}=P-\{p|^{\bullet}p\cup p^{\bullet}\subset T_{x}\}\)_,_ \(E^{\prime}=\{e|e\in T^{\prime}\times P^{\prime}\cup P^{\prime}\times T^{ \prime}\}\)_,_ \(\alpha\) _and_ \(\beta\) _of_ \(t_{x}\)_'s input and output arcs are decided, such that the input and output token flows of the places, included in_ \({}^{\bullet}t_{x}\cup t_{x}^{\bullet}\)_, are kept equivalent before and after shrinking._  
The following lemma shows us that the dependency relation of the transitions does not change before and after a dependent shrink, i.e., if two transitions are out of the dependency relation, then they will not satisfy the dependency relation after a dependent shrink; and vice versa. **Lemma 1**. : _Let \(PN=(T,P,E,\alpha,\beta)\) be a retention-free net including a subnet \(PN_{x}=(T_{x},P_{x},E_{x},\alpha,\beta)\) of Figure (a)a or Figure (a)a and \(PN^{\prime}=(T^{\prime},P^{\prime},E^{\prime},\alpha,\beta)\) be its dependent shrunk net by applying a dependent shrink for \(PN_{x}\), where \(T^{\prime}=T-T_{x}+t_{x}\). Suppose \(t_{j},t_{k}\in T-T_{x}\) and \(t_{y}\in T_{x}\); then, the following claims hold._  
1. _If_ \((t_{j},t_{k})\in R\) _in_ \(PN\)_, then_ \((t_{j},t_{k})\in R\) _in_ \(PN^{\prime}\)_; otherwise,_ \((t_{j},t_{k})\
ot\in R\) _in_ \(PN^{\prime}\)_._
2. _If_ \((t_{j},t_{y})\in R\) _(_\((t_{k},t_{y})\in R\)_) in_ \(PN\)_, then_ \((t_{j},t_{x})\in R\) _(_\((t_{k},t_{x})\in R\)_) in_ \(PN^{\prime}\)_; otherwise,_ \((t_{j},t_{x})\
ot\in R\)__\(((t_{k},t_{x})\
ot\in R)\) _in_ \(PN^{\prime}\)Proof. : Recall that a single-input and single-output structure (Figure 7) and a conflict structure (Figure 8) are the elementary structures of \(RFPN\) considered in this paper. \(PN_{x}\)s surrounded by the bold line in Figures 9a and 10a are basically the same as in Figures 7 and 8, respectively, but these are extended by attaching additional places and arcs (pale parts) in order to make them more general. In addition, two transitions, \(t_{j}\) and \(t_{k}\), are appended for the proof of Lemma 1 below. For the case of Figure 9, \(p\) and its input and output transitions (\(t_{1}\) and \(t_{2}\)) are shrunk into a single transition, \(t_{x}\), and the weights of the new input and output arcs are given as \(\alpha^{\prime}=\alpha_{1}\) and \(\beta^{\prime}=\beta_{2}\frac{b_{1}}{2\alpha}\), respectively. On the other hand, for the case of Figure 10, all output transitions of place \(p\) are shrunk into a single transition, \(t_{x}\), and the weights of the new input and output arcs are set to:  
\[\alpha^{\prime} = \Big{(}\sum_{u=1}^{n}s_{\omega,u}\alpha_{\omega,u}-\sum_{v=1}^{k} s_{1,v}\beta_{1,v}\Big{)}/s_{\omega,1}\] \[\beta^{\prime}_{1} = s_{\omega,1}\beta_{1}\] \[\beta^{\prime}_{2} = s_{\omega,2}\beta_{2}\] \[\vdots\] \[\beta^{\prime}_{n} = s_{\omega,n}\beta_{n}.\]  
Here, \(\alpha^{\prime}>0\) should be satisfied; otherwise, \(PN\) is not a retention-free Petri net.