# An Asymptotic Cyclicity Analysis of Live Autonomous Timed Event Graphs
## 3 Transformation from a TEG to Its Precedence Graph  
This section explains how to transform a general TEG into a precedence graph without going through converting the (max,+) algebra to a matrix form. The precedence graph defined in Section 2 is a special type of TEG with three properties as follows [10]: There is at most one token in each place, there is always a token in all places, and there is only one place that directly connects any two transitions. Therefore, to convert from a general TEG to a precedence graph, we must separate the place with multiple initial tokens into as many places as the number of tokens, remove a place without a token by concatenation with another place, and merge parallel places that directly connect two transitions into one place. First, we explain how to remove the place with multiple tokens so each place has at most one token. There already exists a method of transforming a place with multiple tokens to another equivalent TEG [10]. Specifically, when a TEG has a place with multiple tokens, as in Figure 4, we can construct another TEG with the corresponding places with at most one token in the initial marking. **Rule 1**. : _Concatenation of sequence places_  
**Precondition:**: _A TEG_ \(\mathcal{N}=(P,T,F,H,M_{0})\) _if there exists a place_ \(p_{i0}\) _that initially has more than one token (_\(M_{0}(p_{i0})>1,\exists p_{i0}\in P\)_)._
**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_{i0}\}\)_, where_ \(S=\{p_{i0-j}|0\leq j<M_{0}(p_{i0})\}\)__
2. \(T_{f}=T\cup T^{\prime}-\{t_{i}\}\)_, where_ \(T^{\prime}=\{t_{i-j}|0\leq j<M_{0}(p_{i0})\}\)__
3. \(M_{0}(p)=1,\forall p\in S\)__  
Figure 4: Illustration of Rule 1. 4. \({}^{\bullet}t_{i-0}=^{\bullet}t_{i}\)
5. \({}^{\bullet}t_{i-j}=p_{io-(j-1)},\forall j,0<j<M_{0}(p_{i})\)
6. \({}^{\bullet}p_{io-j}=t_{i-j},\forall j,0\leq j<M_{0}(p_{i})\)
7. \({}^{\bullet}t_{0}=p_{io-\{M_{0}(p_{ia})-1\}}\)
8. \(H(p_{io-j})=H(p_{io})\) if \(j=M_{0}(p_{io})-1\), otherwise \(H(p_{io-j})=0\)  
We illustrate Rule 1 with Figure 4. Steps one and two describe how sets of places and transitions are changed. Place \(p_{io}\), with multiple tokens on the left of Figure 4, is replaced with as many new places as the number of initial tokens (i.e., two places with one token, \(p_{io-0}\) and \(p_{io-1}\)). Transition \(t_{i}\) is also divided into \(t_{i-0}\) and \(t_{i-1}\). Step three guarantees that each new place has exactly one token. Steps four through seven explain how to connect \({}^{\bullet}t_{i}\) and \(t_{o}\). The last step defines the holding time of new places. The holding time of the place \(p_{io}\) in the original TEG is allocated to \(p_{io-\{M_{0}(p_{i})-1\}}\), and directly connected to the transition \(t_{o}\). The holding time of the remaining new places is zero. If we apply this rule to all places with multiple initial tokens, the number of places and transitions increases, but it is known that the new TEG becomes equivalent to the original TEG. To sum it up, the firing epochs of the surviving transitions and the number of tokens between them do not change. We now describe removing the place \(p\) with zero tokens from a TEG by concatenating it to another place. Because a live event graph always has the upstream transitions, the transitions belonging to \({}^{\bullet}p\) may disappear at the same time. However, we assume that the TEG operates using the earliest starting strategy, and so the firing epoch of the removed transition is calculated automatically from the epochs of the remaining transitions. Therefore, the transformed TEG has the same dynamic behavior as the original, so they are equivalent. There are two rules for removing a zero-tokened place, depending on how many downstream places the \({}^{\bullet}p\) has: Rules 2 and 3.