## 4 Dependency Relation and Dependent Shrink
### Uniqueness on Dependent Shrink  
In this section, we introduce the concept of a dependent transition set that is a maximum set of transitions with a dependency relation and discuss the uniqueness of the resultant net through dependent shrink for retention-free Petri nets. **Definition 11**. : _Let \(PN=(T,P,E,\alpha,\beta)\) be a retention-free net, \(t\) be a transition in \(T\) and \(T_{t}\) be a set of all transitions related to \(t\)._  
_Such a_ \(T_{t}\) _is called a_ \(t\)_-dependent transition set._  
_A Petri net induced by_ \(T_{t}\) _is called a_ \(t\)_-dependent subnet and is denoted by_ \(PN_{t}=(T_{t},P_{t},E_{t},\alpha,\beta)\)_._  
Note that, differing from \(PN_{x}\) defined in Definition 10, the transitions included in \(PN_{t}\) are not related to any transitions of \(T-T_{t}\) owing to the fact that \(T_{t}\) is a maximum set of transitions with a dependency relation (shown in Figure 11). The following lemma is immediate. **Lemma 2**. : _Let \(T_{t}\) and \(T_{t^{\prime}}\) be the transition sets of \(t\)-dependent and \(t^{\prime}\)-dependent, respectively. If \((t,t^{\prime})\in R\), then \(T_{t}=T_{t^{\prime}}\)._  
**Lemma 3**. : _Let \(T_{t}\) be a \(t\)-dependent transition set and \(PN_{t}\) be its \(t\)-dependent subnet of a retention-free Petri net \(PN\). Then, \(PN_{t}\) is a connected subnet._  
Proof. : Assume that \(PN_{t}\) is not connected, i.e., \(PN_{t}\) consists of at least two divided nets, \(PN_{1}\) and \(PN_{2}\). Let us see \(PN_{1}=(T_{1},P_{1},E_{1},\alpha,\beta)\) and its connection to the other part of \(PN\). There exists a subset \(P_{t}^{\prime}\subset P_{1}\) of places that includes all places connecting with the outside transitions (not included in \(T_{1}\)), for instance, \(T_{o}\). Thus, these transitions of \(T_{o}\) are the only ones that connect \(PN_{1}\) to other parts  
Figure 11: Relationships among \(T_{x}\), \(T_{t}\) and \(T\). of \(PN\), and further, they are not related to any one of \(T_{t}\) (\((t_{o},t)\
ot\in R\) for \(t_{o}\in T_{o}\) and \(t\in T_{t}\)); otherwise, \(T_{o}\subset T_{t}\). Because \(PN_{1}\) and \(PN_{2}\) are not connected, any transition of \(PN_{2}\) connecting to a transition of \(PN_{1}\) should pass through at least one of \(T_{o}\), which implies that the transitions of \(PN_{2}\) are not related to \(T_{1}\), and thus, this contradicts that \(T_{t}\) is a \(t\)-dependent transition set. **Theorem 2**. : _Let \(t\) be a transition of a retention-free Petri net \(PN=(T,P,E,\alpha,\beta)\), \(T_{t}\) be a \(t\)-dependent transition set, \(PN_{t}=(T_{t},P_{t},E_{t},\alpha,\beta)\) be a \(t\)-dependent subnet, \(PN^{\prime}=(T^{\prime},P^{\prime},E^{\prime},\alpha,\beta)\) be a net by shrinking \(PN_{t}\) and \(t_{t}\) be a shrunken transition of \(PN_{t}\). For \(t_{i},t_{j}\
ot\subseteq T_{t}\), \((t_{i},t_{t})\
ot\in R\) and \((t_{j},t_{t})\
ot\in R\) are satisfied in \(PN^{\prime}\). Further, if \((t_{i},t_{j})\in R\) in \(PN\), then \((t_{i},t_{j})\in R\) in \(PN^{\prime}\), and vice versa._  
Proof. : There exists a subset \(P^{\prime}_{t}\subset P_{t}\) of places that includes all places connecting with the outside transitions (not included in \(T_{t}\)), for example, \(T_{o}\). Thus, these transitions of \(T_{o}\) are only those that connect \(PN_{t}\) to other parts of \(PN\), and further, they are not related to any of \(T_{t}\) (\((t_{o},t)\
ot\in R\) for \(t_{o}\in T_{o}\) and \(t\in T_{t}\)); otherwise, \(T_{o}\subset T_{t}\). After shrinking \(PN_{t}\), \(P^{\prime}_{t}\) and \(t_{t}\) remain in \(PN^{\prime}=(T^{\prime},P^{\prime},E^{\prime},\alpha,\beta)\), and of course, \((t_{o},t_{t})\
ot\in R\) holds in \(PN^{\prime}\) for \(t_{o}\in T_{o}\). Further, any transition \(t^{\prime}\) included in \(T^{\prime}-\{t_{t}\}\) connecting to \(t_{t}\) should pass through at least one of \(T_{o}\), which means that \((t_{i},t_{t})\
ot\in R\) and \((t_{j},t_{t})\
ot\in R\) hold for \(t_{i},t_{j}\
ot\in T_{t}\).