# An Asymptotic Cyclicity Analysis of Live Autonomous Timed Event Graphs
## 2 Basic Definitions and Notations
### (max,+) Algebra
The precedence graph derived from the standard autonomous equation is known as an equivalent graph to the original TEG. Although the set of transitions of the precedence graph is a subset of the transitions of the original TEG, we can predict the epochs of all transitions because the corresponding transitions of the surviving ones fire at the same time, and the firing epochs of the other transitions are also decided uniquely because of the earliest starting policy. Figure 2 is a precedence graph derived from Equation (4). The node is named to represent the original TEG's corresponding transition, and the note of an arc represents the weight. If the precedence graph is strongly connected, we call the matrix is _irreducible_[17]. Additionally, if we have a real number \(\lambda\) and a vector \(x\) which satisfy the equation, \(A\otimes x=\lambda x\), \(\lambda\) is an _topical eigenvalue_, and \(x\) is an _tropical eigenvector_ associated with \(\lambda\). Whereas a general matrix may have several eigenvalues, an irreducible matrix has only one eigenvalue, which we call the _max_(-_algebraic_) _Perron root_ of \(A\)[23]. The value of \(\lambda\) is the maximum cycle mean of \(A\). That is, the asymptotic firing epoch pattern for a given firing sequence and holding time depends on the initial firing epoch. For example, assuming that \(h_{21}\) is four, \(h_{43}\) is nine, and the others are one, there is more than one asymptotic firing epoch pattern of Figure 1 like Figure 3. Both schedules in Figure 3 have the same holding time and firing sequence, but the above schedule repeats every cycle; in the below schedule, the firing time pattern repeats after firing twice. In this case, the above and the below schedules are called a one-cyclic schedule and a two-cyclic schedule, respectively, and the system has an asymptotic two-cyclicity. Definition 2 gives a formal definition of cyclicity and stability. **Definition 2**. : _A schedule is an asymptotic d-cyclic schedule if there exists an integer \(d\), such as \(\vec{x}_{i}^{k+d}-\vec{x}_{i}^{k}\) is a constant, \(d\lambda\), for only \(d\) that is bigger than \(d^{\prime}\) and enough big integer \(k\). In other words, the cyclicity of this schedule is \(d\). An asymptotic 1-cyclic schedule is said to be stable or to have stability [12]._  
Assume that every transition fires under the earliest starting policy. If a system asymptotically converges to less than a \(d\)-cyclic schedule based on the critical cycle structure regardless of the initial firing epoch, its cyclicity is \(d\)[3]. For a given precedence graph, its cyclicity is the LCM (least common multiple) of the cyclicity of every maximal strongly connected subgraph of \(\mathcal{G}^{c}\). The cyclicity of each maximal strongly connected subgraph is the GCD (greatest common divisor) of the number of arcs making up each critical cycle in the subgraph [10; 17]. Additionally, if the precedence graph's cyclicity is \(d\), the original TEG's firing schedule is also an _asymptotic d-cyclic schedule_[12]. Let us illustrate how to calculate the cyclicity with the example in Figure 2. There are four cycles in this precedence graph: \(\pi_{1}:t_{2-0}\to t_{2-0}\), \(\pi_{2}:t_{2-0}\to t_{2-1}\to t_{2-2}\to t_{2-0}\), \(\pi_{3}:t_{4-0}\to t_{4-1}\to t_{4-0}\), and \(\pi_{4}:t_{2-0}\to t_{4-0}\to t_{4-1}\to t_{2-0}\). The precedence graph can be regarded as a TEG, each of whose places has exactly one token. Each cycle's cycle time is the sum of the weights of arcs in the cycle divided by the number of arcs. In this  
Figure 3: A firing schedule for Figure 1.  
Figure 2: The precedence graph for Figure 1.  
example, the cycle times of \(\pi_{1},\pi_{2},\pi_{3}\), and \(\pi_{4}\) are \(\max\{h_{23}+h_{23}^{\prime}\}+h_{34}+h_{41}+h_{12}\), \(\frac{b_{21}+h_{12}}{3}\), \(\frac{\max\{h_{23}+h_{23}^{\prime}\}+2\times h_{34}+h_{41}+h_{12}}{3}\), and \(\frac{h_{34}+h_{34}}{2}\). We are aware that the cycle time of \(\pi_{4}\) is the sum of \(\tilde{\pi}_{1}\) and \(\tilde{\pi}_{3}\).