# An Asymptotic Cyclicity Analysis of Live Autonomous Timed Event Graphs
## 3 Transformation from a TEG to Its Precedence Graph
First, if \((^{\bullet}p_{io})^{\bullet}=\{p_{io}\}\) as in Figure 5, the upstream transition \(t_{i}\) in the removed place \(p_{io}\) has only one downstream place, \(p_{io}\) itself, Rule 2, as inspiration from the serial fusion rule [20], can be applied. **Rule 2**. : _The case in which both a place with a token and its upstream transition are removed._  
**Precondition:**: _When a TEG \(\mathcal{N}=(P,T,F,H,M_{0})\) has Place \(p_{io}\), which has no initial token, we assume that its upstream and downstream transitions are \(t_{i}\) and \(t_{o}\), respectively, and \(t_{i}\) has only one downstream place \(p_{io}\) (\(t_{i}^{\bullet}=\{p_{io}\}\))._
**Rule:**: _A transformed equivalent TEG \(\mathcal{N}_{f}=(P_{f},T_{f},F_{f},H_{f},M_{0f})\) such that_  
1. \(P_{f}=P\cup S-\{p_{io}\}-^{\bullet}t_{i}\)_, where_ \(\forall p_{ji}p_{io},p_{ji}p_{io}\in S\)__
2. \(T_{f}=T-\{t_{i}\}\)__
3. \(M_{0}(p_{ji}p_{io})=M_{0}(p_{ji})\)__
4. \({}^{\bullet}p_{ji}p_{io}=^{\bullet}p_{ji}\)__
5. \(p_{ji}p_{io}=^{\bullet}p_{io}\)__
6. \(H(p_{ji}p_{io})=H(p_{jl})+H(p_{io})\)__  
Figure 5: Illustration of Rule 2. Figure 5 shows an example in which place \(p_{io}\) without any token is concatenated to \({}^{\bullet\bullet}p_{io}\), and its upstream transition \(t_{i}\) is removed. As a result, the number of places and transitions of the new equivalent TEG decreases by one. The new place is named \(p_{ai}p_{io}\) and \(p_{bi}p_{io}\) in succession, with two concatenated places' names, and their initial markings are the same as \(p_{ai}\) and \(p_{bi}\), respectively. Their holding times are the sum of two holding times of the merged places (i.e., \(h_{ai}+h_{io}\) and \(h_{bi}+h_{io}\)). Lemma 1 proves that the TEG derived by Rule 2 is equivalent to the original TEG. **Lemma 1**. : _TEG \(\mathcal{N}\) derived by Rule 2 is equivalent to \(\mathcal{N}_{f}\)._  
Proof. : The set of transitions of TEG \(\mathcal{N}_{f}\) newly derived by Rule 2 is \(T_{f}=T-\{t_{i}\}\), which is a subset of the original transition set. We denote the \(r\)th firing epoch of the transition \(t_{i}\) as \(t_{i}^{r}\) and then assume that place \(p_{io}\) has no initial token. That is, \(t_{o}^{r}=t_{i}^{r}+H(p_{io})\) at the \(r\)th firing epoch of \(t_{o}\). The \(r\)th firing epoch of \(t_{o}\) of the newly created TEG \(\mathcal{N}_{f}\) is changed to  
\[t_{o}^{r}=\max_{p_{ji}\in\star t_{i}}\{H(p_{ji})+H(p_{io})+t_{j}^{r-M_{0}(p_{ ji})}\}. \tag{5}\]  
If firing epochs of transitions other than \(t_{o}\) are the same, the two TEGs are equivalent by Definition 1, given that the number of tokens between the remaining transitions and firing epochs of \(t_{o}\) do not change. The next rule removes zero-tokened \(p_{io}\), whose upstream transition \(t_{i}\) has multiple downstream places. After applying this rule, a place without a token in the original TEG is concatenated to the preceding places \({}^{\bullet\bullet}p_{io}\), but the upstream transition \(t_{i}\) does not disappear. **Rule 3**. : _The case in which a place with a token is removed, but its upstream transition survives._  
**Precondition:**: _When a TEG \(\mathcal{N}=(P,T,F,H,M_{0})\) has Place \(p_{io}\), which has no initial token, we assume that its upstream and downstream transitions are \(t_{i}\) and \(t_{o}\), respectively, and \(t_{i}\) has multiple downstream places, unlike Rule 2 (\(t_{i}^{\bullet}-\{p_{io}\}\
eq\emptyset\))._
**Rule:**: _A transformed equivalent TEG \(\mathcal{N}_{f}=(P_{f},T,F_{f},H_{f},M_{0f})\) such that_  
1. \(P_{f}=P\cup S-\{p_{io}\}\)_, where_ \(\forall p_{ji}p_{io},p_{ji}p_{io}\in S\)__
2. \(t_{i}^{\bullet}=t_{i}^{\bullet}-\{p_{io}\}\)__
3. \(M_{0}(p_{ji}p_{io})=M_{0}(p_{ji})\)__
4. \({}^{\bullet}p_{ji}p_{io}={}^{\bullet}p_{ji}\)__
5. \(p_{ji}p_{io}=p_{io}^{\bullet}\)__
6.