## 5 Dependent Shrink Algorithm and Case Study
### Dependent Shrink Algorithm  
The following algorithm is used to repeatedly shrink the structures of Figures 9 and 10 to find transitions with an interdependent firing frequency. **Input:**\(PN_{0}=(T_{0},P_{0},E_{0})\)  
**Output:** Shrunk Petri net \(N=(T,P,E)\)  
**Main\((PN_{0})\)**  
\(1^{\circ}T\gets T_{0}\), \(P\gets P_{0}\), \(E\gets E_{0}\), \(N\leftarrow(T,P,E)\)  
\(2^{\circ}X\gets P\), \(Q\leftarrow\phi,c\gets 0\)  
\(3^{\circ}\)**while** (\(X\
eq\phi\))  
Pull an element \(x\) from \(X(X\gets X-\{x\})\)  
**Enqueue\((Q,x)\)**  
**Shrink1\((N,x)\)**  
\(4^{\circ}\)**Shrink2\((N,Q,c)\)**  
**Shrink1\((N,x)\)**  
\(1^{\circ}\)**if** (\(|^{\star}x\cap x^{\star}|\geq 1\)) then  
\(f\gets 1\)  
**Arweight\((N,x,f)\)**  
\(2^{\circ}\)**if** (\(|x^{\star}\cap x^{\star}|\geq 2\)) then  
\(f\gets 2\)  
**Arweight\((N,x,f)\)**  
**Shrink2\((N,Q,c)\)**  
\(1^{\circ}\)**while** (\(|Q|\geq 1\))  
\(x\leftarrow\)**Dequeue\((Q)\)**  
**if** (\(|^{\star}x\cap x^{\star}|\geq 1\)) then  
\(f\gets 1\)  
**Enqueue\((Q,x)\)**  
**Algorithm 1** Dependent Shrink
``` else if(\(|\lx@converttounder{\text{\bf else if}}(|\lx@converttounder{\text{\bf else}}| =|\lx@converttounder{\text{\bf x}}^{\bullet}|=1)\)then \(f\gets 3\) \(c\gets 0\) else if(\(|\lx@converttounder{\text{\bf else}}|\geq 2\))then \(f\gets 4\) \(\text{\bf Enqueue}(Q,x)\) \(c\gets c+1\) if(\(f\
eq 4\))then \(\text{\bf Arcweight}(N,x,f)\) if(\(c=|Q|\))then Break \(\text{\bf Arcweight}(N,x,f)\) \(1\lx@converttounder{\text{\bf`if}}(f=1)\)then \(\forall t^{\prime}\in\lx@converttounder{\text{\bf`{x}}}\,\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! The Algorithm 1 will terminate when all places are shrunk, i.e., a single transition remains, or becomes ones with multiple input transitions and a single output transition. The time complexity is \(O(|P||E|)\). As a result, given with a retention-free Petri net, this algorithm gives a smaller shrunk net, in which a transition may represent a class of ones with a dependency relation. ### Case Study

Here, we give an example showing an application of our proposed algorithm. Since the algorithm has not been implemented, here we manually apply it. The algorithm is applied to the IL-3 Petri net model (see Figure 15a), obtained from the website [27]. As a result, the original IL-3 Petri net model shown in Figure 15a is shrunk into Figure 15c. This means that the firing frequencies of all transitions in Figure 15a are dependent on one another. In the intermediate shrunk net (see Figure 15b), by assuming that the firing frequency \(f_{i}\) of the input transition \(t_{i}\) is one, and the weights of the input and output arcs are \(\frac{1}{2}\) and one, respectively, then the firing frequency \(f_{o}\) of output transition \(t_{o}\) is \(\frac{1}{2}\). In this way, we can calculate all firing frequencies in the IL-3 Petri net model if the firing frequency of one transition is known in this model. Figure 15: Shrinking processes of the IL-3 Petri net model. (**a**) Petri net model of IL-3; (**b**) intermediate shrunk net; (**c**) final shrunk net. That is, all of the reaction speed data of the IL-3 Petri net model are dependent on one another, and thus, if one reaction speed datum is available, all of the others can be derived from it. We have two ways to determine reaction speed data in biological pathway, i.e., firing frequencies. One is to find firing frequency relationships between transitions from the intermediate shrunk nets generated during the execution of the Algorithm 1, in turn from the final net to the original net. In the intermediate shrunk net (see Figure 15b), by assuming the firing frequency \(f_{i}\) of the input transition \(t_{i}\) to be available (say one), then the firing frequency \(f_{o}\) of output transition \(t_{o}\) is \(\frac{1}{2}\). Recursively, we can derive all of the firing frequencies in the IL-3 Petri net model.