# An Asymptotic Cyclicity Analysis of Live Autonomous Timed Event Graphs
## 4 Stability Analysis of a TEG  
This section analyzes how the original TEG \(\mathcal{N}=(P,T,F,H,M_{0})\) properties affect the derived precedence graph \(\mathcal{G}(\mathcal{N})=(\mathcal{V},\mathcal{A},\mathcal{W})\) and suggests how to calculate the cyclicity of a live autonomous TEG. First, we investigate which transitions of \(\mathcal{G}(\mathcal{N})\) become corresponding vertices or decompose into multiple corresponding vertices. Lemma 4 determines which transition survives as the vertex of \(\mathcal{G}(\mathcal{N})\). Lemma 4: _If and only if a transition of TEG \(\mathcal{N}\) has at least one downstream place with a token, the transition has corresponding vertices in \(\mathcal{G}(\mathcal{N})\)._  
Figure 8: Example of application of Rules 1 through 4. Proof. : To prove this lemma, we show that, if any downstream place has a token, we cannot remove its upstream transition, and if there is no place with a token among the downstream places, the transition is always removed. First, we prove that a transition whose downstream places have tokens is not removed. Only Rule 2 eliminates a transition after applying the rule. The precondition of the rule is that there is no token in the downstream place of the transition. Even when the downstream transition of its downstream place has been previously eliminated, the token cannot exist in the new downstream place because it occurs only as a result of Rule 2, so the place does not have a token. Therefore, a corresponding transition exists in the precedence graph derived by repeatedly applying transformation rules when one or more downstream places have tokens. Next, we show that the transition without a token in the downstream place is finally not included in the precedence graph. If all downstream places of a transition have no tokens, Rule 3 is applied repeatedly until only one downstream place is left, and then the transition can be eliminated using Rule 2. Therefore, a transition whose downstream places have no tokens is eventually removed. For example, let's check how to map the transitions of TEG \(\mathcal{N}\) in Figure 1 to the vertices of precedence graph \(\mathcal{G}(\mathcal{N})\) in Figure 2. The only transitions with tokened downstream places are \(t_{2}\) and \(t_{4}\) in the TEG \(\mathcal{N}\), and their corresponding vertices are as follows: \(t_{2}\Rightarrow\)(\(t_{2-1}\), \(t_{2-2}\) and \(t_{2-3}\)), and \(t_{4}\Rightarrow\)(\(t_{4-0}\) and \(t_{4-1}\)). In other words, only the corresponding vertices of \(t_{2}\) and \(t_{4}\) of the precedence graph have downstream place tokens. Next, we examine the view of the cycle. Because a live autonomous TEG has a token for each cycle, at least one transition survives as a corresponding vertex for each cycle. In this example, the cycles \(\pi_{1}\) and \(\pi_{2}\) of \(\mathcal{N}\) go through both \(t_{2}\) and \(t_{4}\), and the cycles \(\pi_{3}\) and \(\pi_{4}\) go through both \(t_{2}\) and \(t_{4}\). Looking at the corresponding transition of the vertex included in each cycle of \(\mathcal{G}(\mathcal{N})\), cycles \(\pi_{1}\) and \(\pi_{2}\) have only \(t_{2}\), and \(\pi_{3}\) is related to \(t_{4}\). Cycle \(\pi_{4}\) is related to both \(t_{2}\) and \(t_{4}\). Then, what is the relationship between the cycles of \(\mathcal{N}\) and \(\mathcal{G}(\mathcal{N})\)? Lemma 5 investigates the relationship between the two. Lemma 5.: _If a cycle exists in the original TEG \(\mathcal{N}\), a corresponding cycle exists in the derived precedence graph \(\mathcal{G}(\mathcal{N})\). If there is a cycle in the derived \(\mathcal{G}(\mathcal{N})\), there is a corresponding cycle and concatenation of corresponding cycles in \(\mathcal{N}\)._  
Proof. : We prove this lemma by observing how each rule changes a cycle based on how reachable the transition is. That one transition is reachable from another means that a path exists between them. First, we prove that Rule 1 does not change the reachability among transitions.