# An Asymptotic Cyclicity Analysis of Live Autonomous Timed Event Graphs
## 2 Basic Definitions and Notations
### (max,+) Algebra  
While modeling with a TEG is intuitive, (max,+) algebra is also widely used to model the concept of synchronization and concurrency when analyzing the stability of a discrete event system. The (max,+) algebra known as the max tropical semiring is defined by \((\bar{R},\oplus,\otimes)\) over the real number including a negative infinity and has two operators: a maximum (\(\oplus:a\oplus b=\max(a,b)\)) and a plus (\(\otimes:a\otimes b=a+b\)) [14; 17]. Each of these two  
Figure 1: A general TEG. operators is associative, commutative, and distributive. Their neutral elements of \(\oplus\) and \(\otimes\) correspond to a value of \(-\infty\) and 0, expressed as \(\epsilon\) and \(e\), respectively. TEG modeling is intuitive, whereas stability analysis is indirect, but (max,+) algebra can directly analyze the stability, whereas modeling is not intuitive. Therefore, we usually model with a TEG and then convert it to (max,+) algebra for analysis. Converting a TEG model to (max,+) algebra requires two assumptions [10]: a FIFO and an earliest starting policy. A FIFO selects the token that entered the place first when we need to determine which token has contributed to enabling the downstream transition of the place with more than one token. An earliest starting policy fires transitions immediately if all tokens stay at the minimum holding time in the upstream place. The aim of this article is to analyze whether a live autonomous TEG has asymptotical stability so that these assumptions can be established. The first step in converting a discrete event system modeled with a TEG into a (max,+) algebra model is to express the firing schedule of transitions in a TEG in vector format. In general, the epoch when the \(r\)th firing of the transition \(t_{i}\) occurs is denoted by \(t_{i}^{r}\), so the vector \(\vec{t}\equiv\{t_{i}^{r}|i\in T,r=1,2,...\}\) is the firing schedule of the transition in the \(r\)th cycle. In that case, the schedule satisfies the following:  
\[t_{j}^{r}=max_{(i,j)\in E}\{t_{i}^{r-\mu_{ij}}+h_{ij}\}\hskip 28.452756 pt\forall j \in T, \tag{1}\]  
while \(\mu_{ij}\) and \(h_{ij}\) indicate the number of tokens and the minimum holding time at place \(p_{ij}\), respectively because we assume FIFO and the earliest epoch firing schedule. Equation (1) is an example rewritten in the form of Matrix \(A(k)\) for Figure 1:  
\[\vec{x}^{r}=A(0)\vec{x}^{r}\oplus A(1)\vec{x}^{r-1}\oplus A(2)\vec{x}^{r-2} \oplus A(3)\vec{x}^{r-3}, \tag{2}\]  
where \(\vec{x}^{r}\equiv(t_{1}^{r},t_{2}^{r},t_{3}^{r},t_{4}^{r})^{\prime}\),  
\[A(0)=\left( \begin{array}{cccc}\epsilon&\epsilon&\epsilon&h_{41}\\ h_{12}&\epsilon&\epsilon&\epsilon\\ e&\epsilon&\epsilon&\epsilon\\ e&e&h_{34}&\epsilon\end{array} \right),A(1)=\left( \begin{array}{cccc} \epsilon&\epsilon&\epsilon&\epsilon\\ \epsilon&\epsilon&\epsilon&\epsilon\\ \epsilon&\max\{h_{23},h_{23}^{\prime}\}&\epsilon&\epsilon\\ \epsilon&\epsilon&\epsilon\end{array} \right),\]  
\[A(2)=\left( \begin{array}{cccc}\epsilon&\epsilon&\epsilon&\epsilon\\ e&\epsilon&\epsilon&\epsilon\\ e&\epsilon&\epsilon&h_{43}\\ \epsilon&\epsilon&\epsilon&\epsilon\end{array} \right),and\ A(3)=\left( \begin{array}{cccc}\epsilon&h_{21}&\epsilon&\epsilon\\ \epsilon&\epsilon&\epsilon&\epsilon\\ \epsilon&\epsilon&\epsilon&\epsilon\\ \epsilon&\epsilon&\epsilon&\epsilon\end{array} \right).\]  
Given that Equation (2), unfortunately, uses a circular definition that defines \(\vec{x}^{r}\) using \(\vec{x}^{r}\), to calculate the value of \(\vec{x}^{r}\), this equation must be redefined as a proper recursive definition by removing \(A(0)\) and \(\vec{x}^{r}\) on the right-hand side simultaneously. Therefore, the matrix needs to transform into a _standard autonomous equation_, which means that all matrices on the right-hand side are integrated into one matrix. The first step of this transformation is to change each matrix \(A(k)\) into \(\tilde{A}(k)=A(0)^{*}\otimes A(k)\) to remove \(A(k)\) and \(\vec{x}^{r}\) on the right side, where \(A^{*}\) is the Kleene star of \(A\).