# An Asymptotic Cyclicity Analysis of Live Autonomous Timed Event Graphs
## 3 Transformation from a TEG to Its Precedence Graph
\(H(p_{ji}p_{io})=H(p_{ji})+H(p_{io})\)_._  
Rule 3 is similar to Rule 2 in that a place without a token is concatenated to the upstream places of its upstream transition, but its upstream transition has other downstream places, so it is making the two rules different in that the transition survives after applying the rule. Figure 6 shows an example in which place \(p_{io}\) is replaced with \(p_{ai}p_{io}\) and \(p_{bi}p_{io}\) according to Rule 3. This example does not remove the upstream transition \(t_{i}\) of \(p_{io}\), as opposed to Rule 2. The number of transitions of both TEGs before and after applying the rule is the same as five, but the total number of places increases by the number of upstream places of \(t_{i}\). The holding times, the initial markings, and the naming convention of transformed places are the same as those in Rule 2. Lemma 2 proves that the TEG after applying Rule 3 is equivalent to the original TEG. **Lemma 2**. : _TEG \(\mathcal{N}\) derived by Rule 3 is equivalent to \(\mathcal{N}_{f}\)._  
Proof. : The set of transitions of TEG \(\mathcal{N}_{f}\) transformed by Rule 3 is the same as the original transition set except for the connection relationship with the place. The rule does not change any of the downstream places of the upstream transition of place \(p_{io}\) by Rule 3 except \(t_{i}\) and \(p_{io}\), so \(\{t_{i}^{\bullet\bullet}\}-\{t_{o}\}\) has the same firing epoch after applying the rule. \(t_{o}\) fires at the same time as before the rule was applied for the same reason as in Lemma 1. In addition, the initial marking of the new place \(M_{0}(p_{ji}p_{io})=M_{0}(p_{ji})\), where \(p_{ji}\in^{\bullet}t_{i}\), so the number of tokens between \(t_{j}\) and \(t_{o}\) has not changed. That is, the transformed TEG from applying Rule 3 is equivalent to the original TEG. Finally, we examine the case in which merging multiple places with the same number of tokens connecting two consecutive transitions into one, as shown in Figure 7. We can apply Rule 4 for this case. **Rule 4**. : _Merging of parallel places._  
**Precondition:**: _There is an arbitrary subset_ \(S\) _of places in which the initial token number, the upstream transition_ \(t_{i}\) _and the downstream transition_ \(t_{o}\) _of all places belonging to_ \(S\) _are the same._
**Rule:**: _All places belonging to the set of places_ \(S\) _may be replaced by a single place, specifically a transformed equivalent TEG_ \(\mathcal{N}_{f}=(P_{f},T,F_{f},H_{f},M_{0f})\) _such that_  
1. \(P_{f}=P\cup\{p_{io}^{0}|\cdots|p_{io}^{k}\}-S\)__
2. \(M_{0}(p_{io})=M_{0}(p_{io}^{0}|\cdots|p_{io}^{k})\)__
3. \({}^{\bullet}(p_{io}^{0}|\cdots|p_{io}^{k})=t_{i}\)__
4. \((p_{io}^{0}|\cdots|p_{io}^{k})^{\bullet}=t_{o}\)__
5. \(H(p_{io}^{0}|\cdots|p_{io}^{k})=\underset{\forall p_{io}\in S}{\max}H(p_{io})\)_._  
By way of explanation, if we apply Rule 4, the new place's holding time is the maximum of the original places, and its upstream transition and downstream transition do not change. We denote \(|\) notation to indicate which places are merged in the place newly created by Rule 4 when parallel places directly connect two transitions. Figure 7 illustrates how zero-tokened places \(p_{io}\) and \(p_{io}^{\prime}\), which directly connect \(t_{i}\) and \(t_{o}\) merge to form \(p_{io}|p_{io}^{\prime}\). Its holding time becomes the maximum value of the holding time of \(p_{io}\) and \(p_{io}^{\prime}\). Lemma 3 proves that the new TEG after this transformation is equivalent to the one in existence before the application of Rule 4. Figure 6: Illustration of Rule 3. **Lemma 3**. : _TEG \(\mathcal{N}\) transformed by Rule 4 is equivalent to \(\mathcal{N}_{f}\)._  
Proof. : When all places connect from \(t_{i}\) to \(t_{o}\) and have the same number of tokens, we call them parallel places, and their set is denoted as \(S\) (\(S=^{\bullet}t_{o}\cap t_{i}^{\bullet}\)).