# An Asymptotic Cyclicity Analysis of Live Autonomous Timed Event Graphs
## 2 Basic Definitions and Notations  
### Timed Event Graphs  
This section quickly reviews the essential definitions and notations of a TEG. There are more general discussions [10; 11], and an excellent survey of Petri nets [4]. A TEG is a kind of Petri net and is also known as a marked graph [21]. A TEG is defined as \(\mathcal{N}=(P,T,F,H,M_{0})\). It has two sets of nodes called \(P\) (a set of _places_) and \(T\) (a set of _transitions_). \(F\) is a set of _arcs_ of a directed bipartite graph; and a Petri net where each place has exactly one input and one output transition is called an _event graph_. A TEG is an event graph, so when each place connects the transitions \(t_{i}\) and \(t_{j}\), it is often denoted as \(p_{ij}\). Function \(H(p_{ij})=h_{ij}\) defined in a TEG only is a _holding time_ function, where \(h_{ij}\) is a nonnegative real number. The function's meaning is that the token can be activatedonly after it enters the place \(p_{ij}\) and becomes valid after \(h_{ij}\) has passed. In other words, the holding time of a place defines how long a token must spend in the place before contributing to the enabling of the downstream transitions. \(M_{0}:P\to N^{+}\) is called _initial marking_, where \(N^{+}\) is the set of nonnegative integers. This article uses the following symbols and notations for the set of predecessors and successors of place \(p\in P\) and transition \(t\in T\)[4; 20]. Each place in a TEG has only one upstream transition as a predecessor and only one downstream transition as a successor:  
* \(t=\{p|(p,t)\in F\}\): the set of upstream places in transition \(t\)
* \(t^{\bullet}=\{p|(t,p)\in F\}\): the set of downstream places in transition \(t\)
* \(p=\{t|(t,p)\in F\}\): the set of upstream transitions in place \(p\)
* \(p^{\bullet}=\{t|(p,t)\in F\}\): the set of downstream transitions in place \(p\)  
A _path_ is a sequence of nodes (places and transitions) used to get from one node to another without repeating any nodes or arcs [21]. If the paths of the first and last nodes are the same, we call the nonempty path a _directed cycle_, _simple directed cycle_, or _cycle_ for short. If all transitions in a TEG have upstream places and downstream places, we say that it is _autonomous_. If a cyclic schedule for mass production repeating the same task without any other external control is modeled with a TEG, the TEG can be autonomous [22]. Additionally, a _live_ TEG can fire every transition in \(M_{0}\) state without deadlock. The condition for which an autonomous TEG is live is that every cycle has at least one token [10]. Figure 1 visualizes a TEG with seven places and four transitions. Because it is an event graph, there is exactly one pair of upstream and downstream transitions for each place, so the place connecting \(t_{i}\) to \(t_{j}\) is denoted as \(p_{ij}\), and its holding time is represented as \(h_{ij}\). However, transitions \(t_{2}\) and \(t_{3}\) have two places that directly connect them, for which we use denotations \(p_{23}\) and \(p^{\prime}_{23}\), respectively. That is, the insersection of the downstream places of \(t_{2}\) and the upstream places of \(t_{3}\) are \(p_{23}\) and \(p^{\prime}_{23}(t^{\bullet}_{2}\cap^{\bullet}t_{3}=\{p_{23},p^{\prime}_{23}\})\). We extend this \({}^{\bullet}\) notation for use in succession. \({}^{\bullet\bullet}t\) denotes the set of upstream transitions of the upstream places of transition \(t\) ( \({}^{\bullet\bullet}t=\cup_{p\in\star}t^{\bullet}p\)). For example, \({}^{\bullet\bullet}t_{1}\) is a set of \(t_{2}\) and \(t_{4}\) because the upstream places of \(t_{1}\) are \(p_{21}\) and \(p_{41}\) and their upstream transitions are \(t_{2}\) and \(t_{4}\), respectively. Figure 1 has four cycles: \(\pi_{1}:t_{1}\to p_{12}\to t_{2}\to p_{23}\to t_{3}\to p_{34}\to t_{4}\to p_{41}\to t_{1}\), \(\pi_{2}:t_{1}\to p_{12}\to t_{2}\to p^{\prime}_{23}\to t_{3}\to p_{34}\to t_{4} \to p_{41}\to t_{1}\), \(\pi_{3}:t_{1}\to p_{12}\to t_{2}\to p_{21}\to t_{1}\), and \(\pi_{4}:t_{3}\to p_{34}\to t_{4}\to p_{43}\to t_{3}\).