## 4 Dependency Relation and Dependent Shrink
### Dependency Relation  
Definition 9: Let \(TPN\) be a timed Petri net and \(t_{i}\) and \(t_{j}\) be two transitions. Here, \(t_{i}\) and \(t_{j}\) are said to be related to each other if and only if the following equation holds:  
\[f_{i}=r_{ij}f_{j}, \tag{9}\]  
where \(f_{i}\) and \(f_{j}\) are the firing frequencies of \(t_{i}\) and \(t_{j}\), and \(r_{ij}\) is a positive rational. This is called a dependency relation and is denoted by \((t_{i},t_{j})\)\(\in\)R.  
The above equation means if two transitions are related to each other, then firing frequencies are dependent. Based on this definition, we have the following propositions.  
Theorem 1: _A dependency relation is an equivalence relation._  
Proof: We only need to prove that a dependency relation is reflexive, symmetric and transitive. Let \(t\), \(t_{1}\), \(t_{2}\) and \(t_{3}\) be transitions of a Petri net. A dependency relation is clearly reflexive and symmetric because (1) \(f_{t}=f_{t}\) holds and (2) if \(f_{1}=r_{12}f_{2}\), then \(f_{2}=\frac{1}{r_{12}}f_{1}\), and vice versa. Suppose \(f_{1}=r_{12}f_{2}\) and \(f_{2}=r_{23}f_{3}\) hold, then \(f_{1}=r_{12}r_{23}f_{3}\), which means the dependency relation is transitive.  
Based on the Definition 9, we have the following proposition for a retention-free Petri net.  
Proposition 3: _Let \(PN_{\text{iso}}\) and \(PN_{\text{conf}}\) be two retention-free nets consisting of a place with single input and single output transitions (called a single-input and single-output structure), and a conflict place with multiple transitions (called a conflict structure), respectively. (i) In \(PN_{\text{iso}}\), the input transition and output transition satisfy a dependency relation; (ii) in \(PN_{\text{conf}}\), all output transitions satisfy their dependency relation with one another._  
Proof.: (i) Suppose \(PN_{\text{iso}}\) is a net, as shown in Figure 7. Because Figure 7 is retention free, the amount of input and output token flows through place \(p\) must be equal, i.e., \(f_{i}\beta_{i}=f_{o}\alpha_{o}\). Thus, the firing frequency \(f_{i}\) can be expressed as \(f_{i}=\frac{\alpha_{o}}{\beta_{i}}f_{o}\). (ii) Without a loss of generality, herein we suppose place \(p\) possesses a single input transition (because we only need to consider the dependency relation of the output transitions), as shown in Figure 8.  
Figure 8: Conflict structure (\(PN_{\text{conf}}\)).  
Figure 7: Single-input and single-output structure (\(PN_{\text{iso}}\)).  
Since the given firing probabilities of all output transitions, \(s_{0,1},s_{0,2},\cdots,s_{0,n}\), satisfy:  
\[\begin{array}{rcl}\frac{s_{o,1}}{s_{o,2}}&=&\frac{f_{o,1}}{f_{o,2}}\\ \frac{s_{o,1}}{s_{o,3}}&=&\frac{f_{o,1}}{f_{o,3}}\\ &\vdots&\\ \frac{s_{o,1}}{s_{o,n}}&=&\frac{f_{o,1}}{f_{o,n}}.\end{array} \tag{10}\]  
the firing frequencies, \(f_{o,2}\), \(f_{o,3},\cdots,f_{o,n}\), can be expressed through the following equations:  
\[\begin{array}{rcl}f_{o,2}&=&\frac{s_{o,2}}{s_{o,1}}f_{o,1}\\ f_{o,3}&=&\frac{s_{o,3}}{s_{o,1}}f_{o,1}\\ &\vdots&\\ f_{o,n}&=&\frac{s_{o,n}}{s_{o,1}}f_{o,1},\end{array} \tag{11}\]  
which means that all output transitions satisfy the dependency relations with one another.  
The two nets shown above are elementary structures of \(RFPN\), which will be applied in the following discussion, as well as in our algorithm.  
As shown in Theorem 1 above, a dependency relation is an equivalence relation. Hence, the transition set of a timed Petri net can be divided into independent subsets, i.e., equivalence classes. In the following subsection, to indicate a block of a retention-free Petri net, in which all transitions satisfy a dependency relation, we provide a definition of \"dependent shrink\".