# Model decomposition of timed event graphs under periodic partial synchronization: application to output reference control

Johannes Trunk, Bertrand Cottenceau, Laurent Hardouin, Joerg Raisch

► To cite this version:

Johannes Trunk, Bertrand Cottenceau, Laurent Hardouin, Joerg Raisch. Model decomposition of timed event graphs under periodic partial synchronization: application to output reference control. Discrete Event Dynamic Systems, 2020, 10.1007/s10626-020-00316-y. http://hal-02961743

HAL Id: hal-02961743

https://univ-angers.hal.science/hal-02961743

Submitted on 8 Oct 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

# Dear Author

Here are the proofs of your article.

* You can submit your corrections **online** or by **fax**.

* For **online** submission please insert your corrections in the online correction form. Always indicate the line number to which the correction refers.

* Please return your proof together with the permission to publish confirmation.

* For **fax** submission, please ensure that your corrections are clearly legible. Use a fine black pen and write the correction in the margin, not too close to the edge of the page.

* Remember to note the journal title, article number, and your name when sending your response via e-mail, fax or regular mail.

* **Check** the metadata sheet to make sure that the header information, especially author names and the corresponding affiliations are correctly shown.

* **Check** the questions that may have arisen during copy editing and insert your answers/corrections.

* **Check** that the text is complete and that all figures, tables and their legends are included. Also check the accuracy of special characters, equations, and electronic supplementary material if applicable. If necessary refer to the *Edited manuscript*.

* The publication of inaccurate data such as dosages and units can have serious consequences. Please take particular care that all such details are correct.

* Please **do not** make changes that involve only matters of style. We have generally introduced forms that follow the journal's style. Substantial changes in content, e.g., new results, corrected values, title and authorship are not allowed without the approval of the responsible editor. In such a case, please contact the Editorial Office and return his/her consent together with the proof.

* If we do not receive your corrections **within 48 hours**, we will send you a reminder.

## Please note

Your article will be published **Online First** approximately one week after receipt of your corrected proofs. This is the **official first publication** citable with the DOI. **Further changes are, therefore, not possible.**

After online publication, subscribers (personal/institutional) to this journal will have access to the complete article via the DOI using the URL:

http://dx.doi.org/10.1007/s10626-020-00316-y

If you would like to know when your article has been published online, take advantage of our free alert service. For registration and further information, go to:
http://www.springerlink.com.

Due to the electronic nature of the procedure, the manuscript and the original figures will only be returned to you on special request. When you return your corrections, please inform us, if you would like to have these documents returned.

The **printed version** will follow in a forthcoming issue.
Metadata of the article that will be visualized in OnlineFirst

1 Article Title Model decomposition of timed event graphs under periodic partial synchronization: application to output reference control

2 Article Sub-Title

3 Article Copyright - Year The Author(s) 2020 (This will be the copyright line in the final PDF)

4 Journal Name Discrete Event Dynamic Systems

5 Family Name Trunk

6 Particle

7 Given Name Johannes

8 Suffix

9 Corresponding Author Organization Technische Universität Berlin, Fachgebiet Regelungssysteme

10 Division

11 Address Einsteinufer 17, Berlin D-10587, Germany

12 e-mail Trunk@control.tu-berlin.de

13 Family Name Cottenceau

14 Particle

15 Given Name Bertrand

16 Suffix

17 Organization Université d'Angers

18 Division

19 Address 62 Avenue Notre Dame du Lac, Angers 49000, France

20 e-mail bertrand.cottenceau@univ-angers.fr

21 Family Name Hardouin

22 Particle

23 Given Name Laurent

24 Suffix

25 Organization Université d'Angers

26 Division

27 Address 62 Avenue Notre Dame du Lac, Angers 49000, France

28 e-mail laurent.hardouin@univ-angers.fr

29 Author Family Name Raisch

30 Particle
<table><tr><td>31</td><td>Given Name</td><td>Joerg</td></tr><tr><td>32</td><td>Suffix</td><td></td></tr><tr><td>33</td><td>Organization</td><td>Technische Universität Berlin, Fachgebiet Regelungssysteme</td></tr><tr><td>34</td><td>Division</td><td></td></tr><tr><td>35</td><td>Address</td><td>Einsteinufer 17, Berlin D-10587, Germany</td></tr><tr><td>36</td><td>e-mail</td><td>raisch@control.tu-berlin.de</td></tr><tr><td>37</td><td>Received</td><td>12 December 2018</td></tr><tr><td>38</td><td>Schedule</td><td>Revised</td></tr><tr><td>39</td><td></td><td>Accepted</td></tr><tr><td></td><td></td><td>1 April 2020</td></tr></table>

<table><tr><td>40</td><td>Abstract</td><td>Timed Event Graphs (TEGs) are a graphical model for decision free and time-invariant Discrete Event Systems (DESs). To express systems with time-variant behaviors, a new form of synchronization, called partial synchronization (PS), has been introduced for TEGs. Unlike exact synchronization, where two transitions t<sub>1</sub>,t<sub>2</sub> can only fire if both transitions are simultaneously enabled, PS of transition t<sub>1</sub> by transition t<sub>2</sub> means that t<sub>1</sub> can fire only when transition t<sub>2</sub> fires, but t<sub>1</sub> does not influence the firing of t<sub>2</sub>. This, for example can describe the synchronization between a local train and a long distance train. Of course it is reasonable to synchronize the departure of a local train by the arrival of long distance train in order to guarantee a smooth connection for passengers. In contrast, the long distance train should not be delayed due to the late arrival of a local train. Under the assumption that PS is periodic, we can show that the dynamic behavior of a TEG under PS can be decomposed into a time-variant and a time-invariant part. It is shown that the time-variant part is invertible and that the time-invariant part can be modeled by a matrix with entries in the dioid Minax<sub>γ,δ</sub>, i.e. the time-invariant part can be interpreted as a standard TEG. Therefore, the tools introduced for standard TEGs can be used to analyze and to control the overall system. In particular, in this paper output reference control for TEGs under PS is addressed. This control strategy determines the optimal input for a predefined reference output. In this case optimality is in the sense of the "just-in-time" criterion, i.e., the input events are chosen as late as possible under the constraint that the output events do not occur later than required by the reference output.</td></tr><tr><td>41</td><td>Keywords separated by ' - '</td><td>Dioids - Optimal control - TEG - Discrete-event systems - Residuation - Time-variant behaviour</td></tr><tr><td>42</td><td>Foot note information</td><td>This article belongs to the Topical Collection: on Theory-2020 Guest Editors: Francesco Basile, Jan Komenda, and Christoforos Hadjicostis Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.</td></tr></table>
# Model decomposition of timed event graphs under periodic partial synchronization: application to output reference control

Johannes Trunk¹ · Bertrand Cottenceau² · Laurent Hardouin² · Joerg Raisch¹

Received: 12 December 2018 / Accepted: 1 April 2020

© The Author(s) 2020

## Abstract

Timed Event Graphs (TEGs) are a graphical model for decision free and time-invariant Discrete Event Systems (DESs). To express systems with time-variant behaviors, a new form of synchronization, called partial synchronization (PS), has been introduced for TEGs. Unlike exact synchronization, where two transitions $t_1, t_2$ can only fire if both transitions are simultaneously enabled, PS of transition $t_1$ by transition $t_2$ means that $t_1$ can fire only when transition $t_2$ fires, but $t_1$ does not influence the firing of $t_2$. This, for example can describe the synchronization between a local train and a long distance train. Of course it is reasonable to synchronize the departure of a local train by the arrival of long distance train in order to guarantee a smooth connection for passengers. In contrast, the long distance train should not be delayed due to the late arrival of a local train. Under the assumption that PS is periodic, we can show that the dynamic behavior of a TEG under PS can be decomposed into a time-variant and a time-invariant part. It is shown that the time-variant part is invertible and that the time-invariant part can be modeled by a matrix with entries in the dioid $M_{in}^{ax}$ [[$\gamma$, $\delta$]], i.e. the time-invariant part can be interpreted as a standard TEG. Therefore, the tools introduced for standard TEGs can be used to analyze and to control the overall system. In particular, in this paper output reference control for TEGs under PS is addressed. This control strategy determines the optimal input for a predefined reference output. In this case optimality is in the sense of the "just-in-time" criterion, i.e., the input events are chosen as late as possible under the constraint that the output events do not occur later than required by the reference output.

**Keywords** Diods · Optimal control · TEG · Discrete-event systems · Residuation · Time-variant behaviour

Q1

Q2

<footnote>This article belongs to the Topical Collection: on Theory-2020</footnote>

<footnote>Guest Editors: Francesco Basile, Jan Komenda, and Christoforos Hadjicostis</footnote>

<footnote>☒ Johannes Trunk
Trunk@control.tu-berlin.de</footnote>

<footnote>Extended author information available on the last page of the article.</footnote>
28

# 1 Introduction and motivation

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

TEGs are a subclass of timed Petri nets where each place has exactly one input and one output transition and all arcs have weight 1. Timed Event Graphs under Partial Synchronization (TEGsPS) are an extension of TEGs introduced in David-Henriet et al. (2014). A similar extension was introduced in De Schutter and van den Boom (2003), where TEGs with hard and soft synchronization are studied. TEGsPS can express some time-variant phenomena which cannot be expressed by standard TEGs. For instance, partial synchronization (PS) is useful to model systems where particular events can only occur in a specific time window. E.g., at an intersection, a vehicle can only cross when the traffic light is green. Clearly this describes a time-variant behavior, since the vehicle is delayed by a time that depends on its time of arrival at the intersection. If an earliest functioning rule is adopted, the behavior of a TEG can be modeled by linear equations in a specific algebraic structure called dioid. Based on such dioids, a general theory has been developed for performance evaluation and control of TEGs, e.g. Baccelli et al. (1992) and Heidergott et al. (2005). In particular, the problem of output reference control for TEGs was studied in Baccelli et al. (1992); Cohen et al. (1989); Menguy et al. (1998, 2000). Recently, in David-Henriet et al. (2014, 2015, 2016), dioid theory has been applied to TEGsPS and first results have been obtained for performance evaluation and controller synthesis for TEGsPS. In David-Henriet et al. (2014) output reference control was introduced for TEGsPS. There, the earliest evolution of a Timed Event Graph under Partial Synchronization (TEGPS) is modeled as a (max,+)-system with additional constraints. The control problem is then solved for a finite reference output by solving the backward equation for this (max,+)-system. In Hamaci et al. (2006) and Trunk et al. (2017b) output reference control was studied for TEGs with positive integer weights on the arcs. These TEGs exhibit event-variant behavior and can therefore be seen as the counter-part to TEGsPS.

In this paper we investigate TEGsPS where partial synchronization is periodic. To consider only periodic partial synchronization is not overly restrictive as periodic schedules are common in many applications. E.g. in transportation networks: many public transportation system as well as freight railway services work with a periodic schedule. Similarly in manufacturing systems: there are many production processes, where a resource is shared between several machines on the basis of a periodic schedule. We show that for TEGsPS with periodic PS the dynamic behavior can be modeled in a specific dioid called $T_{per}[\gamma]$. A specific time-variant operator is introduced to take PS into account. Similar to transfer functions for standard TEGs in the dioid $M_{in}^{ax}[\gamma, \delta]$, the transfer behavior of TEGsPS is described by ultimately cyclic series in the dioid $T_{per}[\gamma]$. These transfer functions are useful, for instance, for computing the output for a given input of a system, for system composition and for control synthesis.

This paper is organized as follows: Section 2 summarizes the necessary facts on TEGsPS and dioid theory. In Section 3, modeling of TEGsPS in the dioid $T_{per}[\gamma]$ is introduced. Section 4 discusses a decomposition method for elements in $T_{per}[\gamma]$ and provides tools to handle operations on ultimately cyclic series in $T_{per}[\gamma]$. In particular, we show that basic operations on ultimately cyclic series in $T_{per}[\gamma]$ can be reduced to operations between matrices in $M_{in}^{ax}[\gamma, \delta]$. In Section 5, transfer functions for TEGsPS in $T_{per}[\gamma]$ are used to solve the optimal output reference control problem for this system class.

A preliminary version of this work has been reported in Trunk et al. (2018), where the modeling process of a TEGPS in the dioid $T_{per}[\gamma]$ was established and a decomposition into an invertible time-variant and a time-invariant part was discussed. The purpose of this paper is to introduce optimal output reference control for TEGsPS based on the model in
the dioid $T_{per}[\gamma]$. As a prerequisite, results on the residuation of the product in the dioid $T_{per}[\gamma]$ are obtained.

# 2 Timed event graphs and dioids

## 2.1 Timed event graphs

In the following, we briefly recall the necessary facts on TEGs. For details, see Baccelli et al. (1992) and Heidergott et al. (2005). A TEG consists of a set of places $P = \{p_1, \dots, p_n\}$, a set of transitions $T = \{t_1, \dots, t_m\}$ and a set of arcs $A \subseteq (P \times T) \cup (T \times P)$, all with weight 1. Place $p_i$ is an upstream place of transition $t_j$ (and transition $t_j$ is a downstream transition of place $p_i$), if $(p_i, t_j) \in A$. Conversely, $p_i$ is a downstream place of transition $t_j$ (and $t_j$ is an upstream transition of place $p_i$), if $(t_j, p_i) \in A$. For TEGs, each place $p_i$ has exactly one upstream transition and exactly one downstream transition. Moreover, each place $p_i$ exhibits an initial marking $(M_0)_{i \in \mathbb{N}_0}$ and a holding time $(\phi)_i \in \mathbb{N}_0$. A transition $t_j$ is said to be enabled, if the marking in every upstream place is at least 1. When $t_j$ fires, the marking $(M)_i$ in every upstream place $p_i$ is reduced by 1 and the marking $(M)_o$ in every downstream place $p_o$ is increased by 1. The holding time $(\phi)_i$ is the time a token must remain in place $p_i$ before it contributes to the firing of the downstream transition of $p_i$. The set $T$ of transitions is partitioned into input transitions, i.e., transitions without upstream places, output transitions, i.e., transitions without downstream places and internal transitions, i.e., transitions with both upstream and downstream places. We say that a TEG is operating under the earliest functioning rule, if all internal and output transitions are fired as soon as they are enabled.

## 2.2 Timed event graphs under partial synchronization

TEGsPS provide a suitable model for some time-variant discrete event systems. In the following, we give a brief introduction. For further information the reader is invited to consult (David-Henriet et al. 2014). Considering the TEG in Fig. 1a, assuming the earliest functioning rule, incoming tokens in place $p_1$ are immediately transferred to place $p_2$ by the firing of transition $t_2$, as the holding time of place $p_1$ is zero. Note that zero holding times are, by convention, not indicated in visual illustrations of TEGs. In contrast, Fig. 1b illustrates a TEG with PS of transition $t_2$ by transition $t_a$. This means that $t_2$ can only fire if $t_a$ fires, but the firing of $t_a$ does not depend on $t_2$.

<figure><img src="image_3.png" /><figcaption>**Fig. 1** a standard TEG. b PS of $t_2$ by $t_a$, triggered every $\omega$ time units. c equivalent PS expressed by a signal $S_\omega$.</figcaption></figure>
In this example, place $p_3$ (equipped with a holding time of $\omega$) and transition $t_a$, together with the corresponding arcs, constitute an autonomous TEG. Under the earliest functioning rule, the firings of transition $t_a$ generate a periodic signal $S_\omega$ with a period $\omega \in \mathbb{N}$. Therefore, the PS of $t_2$ by $t_a$ can also be described by a predefined signal $S_\omega: \mathbb{Z} \to \{0, 1\}$, enabling the firing of $t_2$ at times $t$ where $S_\omega(t) = 1$. In particular, $S_\omega(t) = 1$ if $t \in \{j\omega \text{ with } j \in \mathbb{Z}\}$ and $0$ otherwise.

106
107
108
109
110
111

**Definition 1** A periodic signal $S: \mathbb{Z} \to \{0, 1\}$ is defined by a string $\langle n_0, n_1, \dots, n_I \rangle$, with $n_i \in \mathbb{N}, 0 \le i \le I$ and a period $\omega \in \mathbb{N}$, such that $\forall j \in \mathbb{Z}$

$$S(t) = \begin{cases} 1 & \text{if } t \in \{n_0 + \omega j, n_1 + \omega j, \dots, n_I + \omega j\}, \\ 0 & \text{otherwise,} \end{cases}$$

where the string $\langle n_0, n_1, \dots, n_I \rangle$ is strictly increasing, i.e., $\forall i \in \{1, \dots, I\}, n_{i-1} < n_i$, and $n_I < \omega$.

112
113
114
115

**Example 1** The signal

$$S_1(t) = \begin{cases} 1 & \text{if } t \in \{\dots, -4, -3, 0, 1, 4, 5, 8, 9, \dots\}, \\ 0 & \text{otherwise,} \end{cases}$$

is a periodic signal with a period $\omega = 4$ and a string $\langle 0, 1 \rangle$. Therefore $\forall j \in \mathbb{Z}$,

$$S_1(t) = \begin{cases} 1 & \text{if } t \in \{0 + 4j, 1 + 4j\}, \\ 0 & \text{otherwise.} \end{cases} \quad (1)$$

**Definition 2** A Timed Event Graph under periodic partial synchronization is a TEG where the firings of some internal and output transitions are synchronized with periodic signals.

118
119

Note that the assumption that only internal and output transitions are subject to PS is not restrictive since we can always add new input transitions and extend the set of internal transitions by the former input transitions. In David-Henriet et al. (2015), ultimately periodic signals are considered for PS of transitions. It was shown that the behavior of a TEGPS with such synchronization signals can be described by recursive equations in state space form. In this work, we focus on (immediately) periodic signals for PS of transitions. To consider only periodic PS allows us to define a dioid of operators to describe the behavior of TEGsPS. In particular, we can show that the transfer behavior of a TEGPS is described by a rational power series of an ultimately cyclic form. Let us note that focusing on periodic signals for a PS of a transition is not overly restrictive as periodic schedules are common in many applications.

120
121
122
123
124
125
126
127
128
129
130

**Example 2** Let us consider a simple supply chain between two factories. Factory 1 is a supplier for factory 2. The products of factory 1 are transported via a train connection to factory 2. This simple supply chain is modelled by the TEG under periodic PS shown in Fig. 2, with periodic PS of transition $t_2$ by the signal, $\forall j \in \mathbb{Z}$

$$S_2(t) = \begin{cases} 1 & \text{if } t \in \{1 + 20j\}, \\ 0 & \text{otherwise.} \end{cases}$$

Transition $t_1$ models the issue of the goods at factory 1 and transition $t_4$ the receipt of goods at factory 2. Transition $t_2, t_3$ and places $p_2, p_3$ model the train line between the factories. The holding time of 10 time units of place $p_3$ models the travel time of trains between the factories. The 2 initial tokens in place $p_2$ describe the maximal capacity of the
<figure><img src="image_4.png" /><figcaption>Fig. 2 Example of a TEGPS</figcaption></figure>

trains. The schedule of the trains is modelled by the signal $S_2$, hence every 20 time units 139 there is a train leaving from factory 1. We will recall this example again in Section 5 and demonstrate how "just-in-time" control for this supply chain can be computed using the methods developed in this paper. 140 141 142

## 2.3 Dioids 143

A dioid $\mathcal{D}$ is an algebraic structure with two binary operations, $\oplus$ (addition) and $\otimes$ (multiplication). Addition is commutative, associative and idempotent (i.e. $\forall a \in \mathcal{D}, a \oplus a = a$). 144 The neutral element for addition, denoted by $\varepsilon$, is absorbing for multiplication (i.e., $\forall a \in \mathcal{D}, a \otimes \varepsilon = \varepsilon \otimes a = \varepsilon$). Multiplication is associative, distributive over addition and has a neutral element denoted by $e$. The element $e$ (resp, $\varepsilon$) is called unit (resp. zero) element of the dioid. 145 146 147 148 149

Note that, as in conventional algebra, the multiplication symbol $\otimes$ is often omitted. A dioid $\mathcal{D}$ is said to be complete if it is closed for infinite sums and if multiplication distributes over infinite sums. A complete dioid is a partially ordered set, with a canonical order $\geq$ defined by $a \oplus b = a \Leftrightarrow a \geq b$. The infimum operator can then be defined by $a, b \in \mathcal{D}, a \wedge b = \bigoplus\{x \in \mathcal{D} | x \oplus a \leq a, x \oplus b \leq b\}$. Moreover, in a complete dioid, the Kleene star of an element $a \in \mathcal{D}$, denoted $a^*$, is defined by $a^* = \bigoplus_{i=0}^{\infty} a^i$ with $a^0 = e$ and $a^{i+1} = a \otimes a^i$. 150 151 152 153 154 155 156

Let $C \subseteq \mathcal{D}$ then $C$ is a subdioid of $\mathcal{D}$ if $e$ and $\varepsilon$ are in $C$ and $C$ is closed for $\oplus$ and $\otimes$. 156

**Theorem 1** (Baccelli et al. 1992) In a complete dioid $\mathcal{D}$, $x = a^*b$ is the least solution of the implicit equation $x = ax \oplus b$. 157 158

Here, the adjective "least" refers to the canonical order in the dioid described above. 159

Both multiplication and addition on a (complete) dioid $\mathcal{D}$ can be readily extended to the matrix case: for matrices $A, B \in \mathcal{D}^{m \times n}$, $C \in \mathcal{D}^{n \times q}$ and a scalar $\lambda \in \mathcal{D}$, matrix addition and multiplication are defined by 160 161 162

$$ (A \oplus B)_{i,j} := (A)_{i,j} \oplus (B)_{i,j}, \quad (\lambda \otimes A)_{i,j} := \lambda \otimes (A)_{i,j}, $$

$$ (A \otimes C)_{i,j} := \bigoplus_{k=1}^{n} ((A)_{i,k} \otimes (C)_{k,j}). $$

Moreover, the order relation on matrices of the same dimension is understood elementwise, i.e. $A \geq B$ iff $(A)_{i,j} \geq (B)_{i,j}, \forall i, j$. The identity matrix, denoted by $I$, is a square matrix with elements $e$ on the diagonal and $\varepsilon$ otherwise. 163 164 165
## 2.4 Complete dioids and residuation theory

167 Residuation theory is a formalism to address the problem of approximate mapping inversion
168 over ordered sets (Baccelli et al. 1992). It applies to complete dioids, since a complete dioid
169 $\mathcal{D}$ is a partially ordered set.

170 **Definition 3** (Baccelli et al. 1992) A mapping $f: \mathcal{D} \to \mathcal{L}$, with $\mathcal{D}$ and $\mathcal{L}$ complete dioids, is residuated if $\forall b \in \mathcal{L}$ the inequality $f(x) \preceq b$ has a greatest solution in $\mathcal{D}$, denoted $f^{\sharp}(b)$. The mapping $f^{\sharp}: \mathcal{L} \to \mathcal{D}$, is called the residual of $f$.

173 **Theorem 2** (Baccelli et al. 1992) A mapping $f: \mathcal{D} \to \mathcal{L}$, with $\mathcal{D}$ and $\mathcal{L}$ complete dioids, is residuated iff $f(\varepsilon) = \varepsilon$ and $f$ is lower-semicontinuous, that is

175 $f\left(\bigoplus_{x \in X} x\right) = \bigoplus_{x \in X} f(x)$, for every (finite or infinite) subset $X$ of $\mathcal{D}$.

176 On a complete dioid the mapping $R_a : x \mapsto xa$, (right multiplication by $a$) resp. $L_a : x \mapsto ax$ (left multiplication by $a$), is lower-semicontinuous and therefore residuated. The residual mappings are denoted $R_a^{\sharp}(b) = b\phi a = \bigoplus \{x | xa \preceq b\}$ (right division by $a$) and $L_a^{\sharp}(b) = a\phi b = \bigoplus \{x | ax \preceq b\}$ (left division by $a$). Left and right division can be extended to the matrix case. For matrices $A \in \mathcal{D}^{m \times n}$, $B \in \mathcal{D}^{m \times q}$, $C \in \mathcal{D}^{n \times q}$

$$ (A \flat B)_{i,j} = \bigwedge_{k=1}^{m} ((A)_{k,i} \flat (B)_{k,j}), \quad (B \flat C)_{i,j} = \bigwedge_{k=1}^{q} ((B)_{i,k} \flat (C)_{j,k}). \quad (2) $$

181 In the following some useful properties of left and right division are summarized, for a
182 proof see Baccelli et al. (1992) or the recent summary paper (Hardouin et al. 2018). For
183 $a, b, x \in \mathcal{D}$ and $\mathcal{D}$ a complete dioid,

$$ (ab) \flat x = b \flat (a \flat x) \qquad x \flat (ba) = (x \flat a) \flat (b) \qquad (3) $$

$$ (a \oplus b) \flat x = (a \flat x) \wedge (b \flat x) \qquad x \flat (a \oplus b) = (x \flat a) \wedge (x \flat b), \qquad (4) $$

$$ (a \flat x) \flat b = a \flat (x \flat b). \qquad (5) $$

## 3 Modeling of TEGs under PS in the Dioid $\mathcal{T}[[\gamma]]$

185 To model TEGsPS, a dater function $x_i : \mathbb{Z} \to \mathbb{Z}_{max} := \{\mathbb{Z}\} \cup \{\infty\} \cup \{-\infty\}$ is associated to each transition $t_i$. The value $x_i(k)$ gives the date (time) when transition $t_i$ fires the $(k+1)^{st}$ time. Naturally, dater functions are nondecreasing functions, i.e., $x_i(k+1) \ge x_i(k)$. The set of dater functions is denoted by $\Sigma$. On $\Sigma$, addition and multiplication by a constant are defined as follows:

$$ x, y \in \Sigma, (x \oplus y)(k) := \max(x(k), y(k)), \\ \lambda \in \mathbb{Z}_{max}, (\lambda \oplus x)(k) := \lambda + x(k). $$

190 The zero element $\tilde{\varepsilon}$ on $\Sigma$ is defined by $\tilde{\varepsilon}(k) = -\infty$, $\forall k \in \mathbb{Z}$. The $\oplus$ operation induces an order relation on $\Sigma$, i.e., for $x, y \in \Sigma$, $x \preceq y \Leftrightarrow x \tilde{\oplus} y = y$. In this order, the top element $\tilde{T}$ is defined by $\tilde{T}(k) = +\infty$, $\forall k \in \mathbb{Z}$. An operator, i.e., a map, $o : \Sigma \to \Sigma$ is linear if (a) $\forall x, y \in \Sigma : o(x \tilde{\oplus} y) = o(x) \tilde{\oplus} o(y)$ and (b) $\lambda \tilde{\oplus} o(x) = o(\lambda \tilde{\oplus} x)$. An operator is additive if
(a) is satisfied. Let $\mathcal{O}$ denote the set of all operators $o : \Sigma \to \Sigma$. Moreover, let $\mathcal{O}_a$ denote 194 the subset of all additive operators in $\mathcal{O}$. 195

**Proposition 1** (Cottenceau et al. 2014) The set $\mathcal{O}_a$ equipped with addition and multiplication: $x \in \Sigma, \forall o_1, o_2 \in \mathcal{O}_a$, 196 197

$$ (o_1 \oplus o_2)(x) := o_1(x) \tilde{\oplus} o_2(x), \quad (o_1 \otimes o_2)(x) := o_1(o_2(x)), \qquad (6) $$

is a noncommutative complete dioid. The identity operator (unit element) is denoted by $e : \forall x \in \Sigma$, $e(x) = x$, the zero operator (zero element) is denoted by $\varepsilon : \forall x \in \Sigma$, $\varepsilon(x) = \tilde{\varepsilon}$ and the top operator (top element) is denoted by $\top : \forall x \in \Sigma \setminus \{\tilde{\varepsilon}\}$, $\top(x) = \tilde{\top}$. 198 199 200

To simplify notation, we write $ox$ instead of $o(x)$ wherever clear from the context. 201

**Definition 4** (Basic operators in $\mathcal{O}$) Dynamic phenomena arising in TEGsPS can be described by the following basic operators in $\mathcal{O}$: 202 203

$$ \tau \in \mathbb{Z}, \delta^{\tau} : \forall x \in \Sigma, (\delta^{\tau} x)(k) = x(k) + \tau, \qquad (7) $$

$$ \eta \in \mathbb{Z}, \gamma^{\eta} : \forall x \in \Sigma, (\gamma^{\eta} x)(k) = x(k - \eta), \qquad (8) $$

$$ \omega, \bar{\omega} \in \mathbb{N}, \Delta_{\omega|\bar{\omega}} : \forall x \in \Sigma, (\Delta_{\omega|\bar{\omega}} x)(k) = \lceil x(k)/\bar{\omega} \rceil \omega, \qquad (9) $$

where $\lceil a \rceil$ is the smallest integer greater than or equal to $a$. 204

It can be easily checked that all these operators are additive, i.e., $\delta^{\tau}, \gamma^{\eta}, \Delta_{\omega|\bar{\omega}} \in \mathcal{O}_a$. The time- and event-shift operator $\delta$ and $\gamma$ are used to model the dynamic behavior of standard TEGs, e.g., Baccelli et al. (1992). In addition we introduce the $\Delta_{\omega|\bar{\omega}}$ operator to consider phenomena caused by PS. 205 206 207 208

**Proposition 2** (Trunk et al. 2018) The basic operators satisfy the following relations 209

$$ \gamma^{\eta} \oplus \gamma^{\eta'} = \gamma^{\min(\eta, \eta')}, \qquad \delta^{\tau} \oplus \delta^{\tau'} = \delta^{\max(\tau, \tau')}, \qquad (10) $$

$$ \gamma^{\eta} \otimes \gamma^{\eta'} = \gamma^{\eta+\eta'}, \qquad \delta^{\tau} \otimes \delta^{\tau'} = \delta^{\tau+\tau'}, \qquad (11) $$

$$ \Delta_{\omega|\bar{\omega}} \otimes \delta^{\bar{\omega}} = \delta^{\omega} \otimes \Delta_{\omega|\bar{\omega}}. \qquad (12) $$

**Remark 1** Equation 12 implies that for $-b < \tau \le 0$, $\Delta_{\omega|\bar{\omega}}\delta^{\tau}\Delta_{\omega|\bar{\omega}} = \Delta_{\omega|\bar{\omega}}$, since, 210

$$ \begin{aligned} (\Delta_{\omega|\bar{\omega}}\delta^{\tau}\Delta_{\omega|\bar{\omega}}x)(k) &= \left\lceil \frac{x(k)/\bar{\omega}b + \tau}{b} \right\rceil \omega = \left\lceil \left\lceil \frac{x(k)}{\bar{\omega}} \right\rceil + \frac{\tau}{b} \right\rceil \omega \\ &= \left\lceil \frac{x(k)}{\bar{\omega}} \right\rceil \omega \quad \text{since } -1 < \tau/b \le 0, \\ &= (\Delta_{\omega|\bar{\omega}}x)(k). \end{aligned} $$

## 3.1 Dioid of time operators $\mathcal{T}$ 211

In the following, we introduce a dioid of specific time operators in order to model the time-variant behavior of periodic PS. 212 213
214 **Definition 5** (Dioid of T-operators $\mathcal{T}$) We denote by $\mathcal{T}$ the dioid of operators obtained by addition and composition of operators in $(\varepsilon, \varepsilon, \delta^5, \Delta_{\omega|\omega}, \top)$ with $\zeta \in \mathbb{Z}$, and $\omega, \bar{\omega} \in \mathbb{N}$. The elements of $\mathcal{T}$ are called T-operators (T is for time).

217 For example, $\delta^3 \Delta_{4|4} \delta^1 \Delta_{3|2} \in \mathcal{T}$. Since a T-operator only describes a time relation in a system, e.g., a delay, we can associate a function $\mathcal{R}_v : \mathbb{Z}_{max} \to \mathbb{Z}_{max}$ to a T-operator $v$. This function, when evaluated on $t$, is obtained by replacing $x(k)$ by $t$ in the expression of $v(x)(k)$. For example, $((\Delta_{3|4} \delta^1 \oplus \delta^2 \Delta_{3|3})x)(k) = \max(\lceil x(k) + 1 \rceil/4 \rceil 3, 2 + \lceil x(k)/3 \rceil 3)$ and therefore $\mathcal{R}_{\Delta_{3|4} \delta^1 \oplus \delta^2 \Delta_{3|3}}(t) = \max(\lceil(t+1)/4 \rceil 3, 2 + \lceil t/3 \rceil 3)$. The interpretation of $\mathcal{R}_v$ is as follows. Let $x_1$, respectively $x_2$, be the dater functions associated with transitions $t_1$, respectively $t_2$. If $v$ maps $x_1$ to $x_2$, then $\mathcal{R}_v$ maps the time of the $(k+1)^{st}$ firing of $t_1$ into the time of the $(k+1)^{st}$ firing of $t_2$. $\mathcal{R}_v$ is therefore called the release-time function associated to the T-operator $v$. We denote by $\mathcal{R}$ the set of functions $\mathcal{R}_v$ generated by all operators $v$ in $\mathcal{T}$. Clearly, there is an isomorphism between the set of T-operators and the set $\mathcal{R}$. The order relation over the dioid $\mathcal{T}$ corresponds to the order induced by the max operation on $\mathcal{R}$.

229 For $v_1, v_2 \in \mathcal{T}$,

$$ 
\begin{aligned}
v_1 \ge v_2 &\Leftrightarrow v_1 \oplus v_2 = v_1 \Leftrightarrow v_1 x \oplus v_2 x = v_1 x, \quad \forall x \in \Sigma, \\
&\Leftrightarrow \max((v_1 x)(k), (v_2 x)(k)) = (v_1 x)(k), \quad \forall x \in \Sigma, \forall k \in \mathbb{Z}, \\
&\Leftrightarrow \mathcal{R}_{v_1}(t) \ge \mathcal{R}_{v_2}(t), \quad \forall t \in \mathbb{Z}_{max}.
\end{aligned} 
\quad (13) 
$$

230 **Definition 6** (Periodic T-operators) A T-operator $v \in \mathcal{T}$ is said to be $\omega$-periodic if its corresponding function $\mathcal{R}_v$ is quasi-$\omega$-periodic, i.e., $\exists \omega \in \mathbb{N}$ such that $\forall t \in \mathbb{Z}_{max}, \mathcal{R}_v(t + \omega) = \omega + \mathcal{R}_v(t)$. The set of $\omega$-periodic T-operators is denoted by $\mathcal{T}_\omega$. Moreover the set of periodic operators is defined by $\mathcal{T}_{per} = \bigcup_{\omega \in \mathbb{N}} \mathcal{T}_\omega$.

$\mathcal{T}_\omega$ and $\mathcal{T}_{per}$ are subdioids of $\mathcal{T}$.

234 **Example 3** The operator $\Delta_{4|4}$ is 4-periodic and the operator $\Delta_{3|3}\delta^2$ is 3-periodic as $\mathcal{R}_{\Delta_{4|4}}(t) = \lceil t/4 \rceil 4$ and $\mathcal{R}_{\Delta_{3|3}\delta^2}(t) = \lceil (t+2)/3 \rceil 3$. Therefore $\Delta_{4|4} \in \mathcal{T}_4, \Delta_{3|3}\delta^2 \in \mathcal{T}_3$. Evidently, both operators are also 12-periodic and therefore $\Delta_{4|4}, \Delta_{3|3}\delta^2 \in \mathcal{T}_{12}$.

237 **Proposition 3** (Trunk et al. 2018) An $\omega$-periodic T-operator $v \in \mathcal{T}_\omega$ has an $\omega$-periodic canonical form given by a finite sum $\bigoplus_{i=1}^I \delta^{\tau_i} \Delta_{\omega|\omega} \delta^{\tau'_i}$, where $\tau_i < \tau_{i+1} \forall i \in \{1, \dots, I-1\}$, $I \le \omega$ and $-\omega < \tau'_i \le 0, \forall i \in \{1, \dots, I\}$.

240 **Remark 2** Clearly each $\omega$-periodic operator $v \in \mathcal{T}_{per}$ is also $n\omega$-periodic with $n \ge 1$ and can be represented as $\bigoplus_{i=1}^I \delta^{\tau_i} \Delta_{n\omega|n\omega} \delta^{\tau'_i}$ and $I \le n\omega$.

242 **Proposition 4** The 1-periodic identity operator $e = \Delta_{1|1}$ can be represented in the specific form,

$$ e = \bigoplus_{i=0}^{\omega-1} \delta^{-i} \Delta_{\omega|\omega} \delta^{1+i-\omega}. \quad (14) $$
Proof Recall the isomorphism between T-operators and the set $\mathcal{R}$. Hence it is sufficient to show that $\mathcal{R}_e = \mathcal{R}_{\bigoplus_{i=0}^{\omega-1} \delta^{-i} \Delta_{\omega|\omega} \delta^{1+i-\omega}}$. Moreover, since $\forall t \in \mathbb{Z}_{max}$, $\mathcal{R}_e(t) = t$, it remains to show that $\forall t \in \mathbb{Z}_{max}$, $\mathcal{R}_{\bigoplus_{i=0}^{\omega-1} \delta^{-i} \Delta_{\omega|\omega} \delta^{1+i-\omega}}(t) = t$. 244

$$ \mathcal{R}_{\bigoplus_{i=0}^{\omega-1} \delta^{-i} \Delta_{\omega|\omega} \delta^{1+i-\omega}}(t) = \max \left( \left\lfloor \frac{t+1-\omega}{\omega} \right\rfloor \omega, \left\lfloor \frac{t+2-\omega}{\omega} \right\rfloor \omega - 1, \dots, \left\lfloor \frac{t}{\omega} \right\rfloor \omega - (\omega-1) \right). \quad (15) $$

Because $\mathcal{R}_{\bigoplus_{i=0}^{\omega-1} \delta^{-i} \Delta_{\omega|\omega} \delta^{1+i-\omega}}(t)$ is a quasi $\omega$-periodic function, Definition 6, it is sufficient to evaluate Eq. 15 for $t = \{1-\omega, \dots, 0\}$. This leads to, 247

$$ \mathcal{R}_{\bigoplus_{i=0}^{\omega-1} \delta^{-i} \Delta_{\omega|\omega} \delta^{1+i-\omega}}(0) = \max \left( \left\lfloor \frac{1-\omega}{\omega} \right\rfloor \omega, \left\lfloor \frac{2-\omega}{\omega} \right\rfloor \omega - 1, \dots, \left\lfloor \frac{0}{\omega} \right\rfloor \omega - (\omega-1) \right) = 0 $$

$$ \mathcal{R}_{\bigoplus_{i=0}^{\omega-1} \delta^{-i} \Delta_{\omega|\omega} \delta^{1+i-\omega}}(-1) = \max \left( \left\lfloor \frac{-\omega}{\omega} \right\rfloor \omega, \left\lfloor \frac{1-\omega}{\omega} \right\rfloor \omega - 1, \dots, \left\lfloor \frac{-1}{\omega} \right\rfloor \omega - (\omega-1) \right) = -1 $$

$$ \mathcal{R}_{\bigoplus_{i=0}^{\omega-1} \delta^{-i} \Delta_{\omega|\omega} \delta^{1+i-\omega}}(1-\omega) = \max \left( \left\lfloor \frac{2-2\omega}{\omega} \right\rfloor \omega, \left\lfloor \frac{3-2\omega}{\omega} \right\rfloor \omega - 1, \dots, \left\lfloor \frac{1-\omega}{\omega} \right\rfloor \omega - (\omega-1) \right) = 1-\omega. $$

□ 249

Example 4 The identity operator $e = \Delta_{1|1}$ can be represented as $e = \Delta_{3|3}\delta^{-2} \oplus \delta^{-1}\Delta_{3|3}\delta^{-1} \oplus \delta^{-2}\Delta_{3|3}$. Figure 3 illustrates that indeed $\mathcal{R}_e(t) = \mathcal{R}_{\Delta_{3|3}\delta^{-2} \oplus \delta^{-1}\Delta_{3|3}\delta^{-1} \oplus \delta^{-2}\Delta_{3|3}}(t) = \max(\mathcal{R}_{\Delta_{3|3}\delta^{-2}}(t), \mathcal{R}_{\delta^{-1}\Delta_{3|3}\delta^{-1}}(t), \mathcal{R}_{\delta^{-2}\Delta_{3|3}}(t))$. 250

The time-variant behavior caused by a periodic PS of a transition can be conveniently modeled in the dioid $\mathcal{T}$. 253

<figure><img src="image_5.png" /><figcaption>Fig. 3 $\mathcal{R}_e(t) = \max(\mathcal{R}_{\Delta_{3|3}\delta^{-2}}(t), \mathcal{R}_{\delta^{-1}\Delta_{3|3}\delta^{-1}}(t), \mathcal{R}_{\delta^{-2}\Delta_{3|3}}(t))$</figcaption></figure>
For this, recall the definition of a periodic signal $\mathcal{S}$ (Definition 1). We associate with a periodic signal $\mathcal{S}: \mathbb{Z} \to \{0, 1\}$ characterized by $\langle n_0, \dots, n_I \rangle$ and period $\omega$ a function $\mathcal{R}_S: \mathbb{Z}_{max} \to \mathbb{Z}_{max}$. This function $\mathcal{R}_S(t)$ is defined by, $\forall j \in \mathbb{Z}$,

$$ \mathcal{R}_S(t) = \begin{cases} -\infty & \text{if } t = -\infty \\ n_0 + \omega j & \text{if } (n_I - \omega) + \omega j < t \le n_0 + \omega j, \\ n_1 + \omega j & \text{if } n_0 + \omega j < t \le n_1 + \omega j, \\ \vdots & \\ n_I + \omega j & \text{if } n_{I-1} + \omega j < t \le n_I + \omega j, \\ \infty & \text{if } t = \infty. \end{cases} \quad (16) $$

Example 5 The function $\mathcal{R}_{S_1}(t)$ (Fig. 4b) associated to the signal $S_1$ (Fig. 4) given in Example 1 is

$$ \mathcal{R}_{S_1}(t) = \begin{cases} -\infty & \text{if } t = -\infty \\ 0 + 4j & \text{if } -3 + 4j < t \le 0 + 4j, \\ 1 + 4j & \text{if } 0 + 4j < t \le 1 + 4j, \\ \infty & \text{if } t = \infty. \end{cases} $$

The value of $\mathcal{R}_S(t)$ can be interpreted as the next time when the signal $\mathcal{S}$ enables the firing of the corresponding transition. Clearly, an $\omega$-periodic signal $\mathcal{S}$ leads to a corresponding function $\mathcal{R}_S(t)$ which satisfies $\forall t \in \mathbb{Z}_{max}, \mathcal{R}_S(t + \omega) = \omega + \mathcal{R}_S(t)$.

To prove that a periodic PS of a transition (i.e., the PS is specified by a periodic signal $\mathcal{S}$) admits an operator representation in the dioid $\mathcal{T}$, we must show the existence of an operator $v \in \mathcal{T}$ such that $\mathcal{R}_v = \mathcal{R}_S$.

**Proposition 5** (Trunk et al. 2018) A periodic partial synchronization of a transition by the signal $\mathcal{S}$ in Definition 1 has an operator representation given by

$$ v = \delta^{n_0} \Delta_{\omega|\omega} \delta^{-n_1} \oplus \delta^{n_1-\omega} \Delta_{\omega|\omega} \delta^{-n_0} \oplus \dots \oplus \delta^{n_I-\omega} \Delta_{\omega|\omega} \delta^{-n_{(I-1)}}. \quad (17) $$

Example 6 Consider the TEGPS shown in Fig. 5, where the signal $S_1$ is given in Eq. 1 (Example 1) and later function $x_1(k)$ (resp. $x_2(k)$) is associated with transition $t_1$ (resp. $t_2$).

<figure><img src="image_6.png" /><figcaption>Fig. 4 Signal $S_1$ and the associated function $\mathcal{R}_{S_1}$</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>**Fig. 5** Simple TEGPS with a
periodic PS of $t_2$</figcaption></figure>

According to Proposition 5, the behavior of the periodic PS of transition $t_2$ is modeled by 270
the following operator: 271

$$v_{S_1} = \delta^0 \Delta_{4|4} \delta^{-1} \oplus \delta^{-3} \Delta_{4|4} \delta^{-0} = \delta^{-3} \Delta_{4|4} \oplus \Delta_{4|4} \delta^{-1},$$

where the latter equality holds as $\delta^0 = e$. 272

Since the holding time of place $p_1$ is 0 and there are no initial tokens in the place $p_1$ this operator describes the firing relation between $t_1$ and $t_2$, i.e., $x_2 = (\delta^{-3} \Delta_{4|4} \oplus \Delta_{4|4} \delta^{-1})x_1$. Therefore, $x_2(k) = \max(-3 + \lceil x_1(k)/4 \rceil, \lceil (x_1(k) - 1)/4 \rceil)$. 273
274
275

**Remark 3** Due to the influence of the PS, this firing relation between $t_1$ and $t_2$ is time-variant. For instance, if the $(k+1)^{st}$ firing of $t_1$ is at time instant $x_1(k) = 1$, then the $(k+1)^{st}$ firing of $t_2$ is at $x_2(k) = 1$, i.e., we have no delay. In contrast, if the $(k+1)^{st}$ firing of $t_1$ is at time instant $x_1(k) = 2$, then the $(k+1)^{st}$ firing of $t_2$ is at $x_2(k) = 4$, and the delay is 2. 276
277
278
279

## 3.2 Dioid $\mathcal{T}[[\gamma]]$ 280

Since the $\gamma$ operator commutes with all T-operators, i.e., $\forall v \in \mathcal{T}$, $v\gamma = \gamma v$, we can define the dioid $\mathcal{T}[[\gamma]]$ as follows. 281
282

**Definition 7** (Dioid $\mathcal{T}[[\gamma]]$) We denote by $\mathcal{T}[[\gamma]]$ the quotient dioid in the set of formal power series in one variable $\gamma$ with exponents in $\mathbb{Z}$ and coefficients in the noncommutative complete dioid $\mathcal{T}$ induced by the equivalence relation, $\forall s \in \mathcal{T}$, 283
284
285

$$s = s(\gamma^*). \qquad (18)$$

Hence we identify two series $s_1, s_2$ with the same equivalence class, if $s_1\gamma^* = s_2\gamma^*$. It is helpful to think of $s\gamma^*$ as the representative of the equivalence class of $s$. Note that we can interpret elements in $\mathcal{T}[[\gamma]]$ as nondecreasing functions $s : \mathbb{Z} \to \mathcal{T}$, where $s(\eta)$ refers to the coefficient of $\gamma^\eta$. Hence, $\forall \eta \in \mathbb{Z}$, $s(\eta) \le s(\eta + 1)$. For a fundamental mathematical background on quotient dioids, the reader is invited to consult (Baccelli et al. 1992). Moreover, in Hardouin et al. (2018) quotient dioids are studied from a didactic point of view. 286
287
288
289
290
291

**Definition 8** Let $s_1, s_2 \in \mathcal{T}[[\gamma]]$, then addition and multiplication are defined by 292

$$s_1 \oplus s_2 := \bigoplus_{\eta \in \mathbb{Z}} (s_1(\eta) \oplus s_2(\eta))\gamma^{\eta},$$

$$s_1 \otimes s_2 := \bigoplus_{\eta \in \mathbb{Z}} \left( \bigoplus_{n+n'=\eta} (s_1(n) \otimes s_2(n')) \right) \gamma^{\eta}.$$
We denote by $\mathcal{T}_{per}[\gamma]$ the subdioid of $\mathcal{T}[\gamma]$, obtained by restricting the coefficients $v$ to periodic operators, i.e., $v \in \mathcal{T}_{per}$. As before, $\oplus$ defines an order on $\mathcal{T}[\gamma]$, i.e., $a, b \in \mathcal{T}[\gamma] : a \oplus b = b \Leftrightarrow a \leq b$. Hence $\forall s_1, s_2 \in \mathcal{T}[\gamma]$, $s_1 \leq s_2 \Leftrightarrow s_1(\eta) \leq s_2(\eta)$, $\eta \in \mathbb{Z}$. A monomial in $\mathcal{T}[\gamma]$ is defined by $v\gamma^\eta$, where $v \in \mathcal{T}$ and $\eta \in \mathbb{Z}$. The ordering of two monomials $v_1\gamma^{\eta_1}, v_2\gamma^{\eta_2} \in \mathcal{T}[\gamma]$ can be checked as follows,

$$v_1\gamma^{\eta_1} \leq v_2\gamma^{\eta_2} \Leftrightarrow \begin{cases} v_1 \leq v_2, \\ \eta_1 \geq \eta_2. \end{cases} \qquad (19)$$

A polynomial is a finite sum of monomials, i.e., $\bigoplus_{i=1}^{I} v_i \gamma^{\eta_i}$.

**Proposition 6** Let $p \in \mathcal{T}_{per}[\gamma]$ be a polynomial, then $p$ has a canonical form $p = \bigoplus_{j=1}^{I} v_j \gamma^{\eta'_j}$ such that $\forall j \in \{1, \dots, J\}$, the $\omega$-periodic T-operator $v'_j$ is in the canonical form of Proposition 3, and coefficients and exponents are strictly ordered, i.e., for $j \in \{1, \dots, J-1\}$, $\eta'_j < \eta'_{j+1}$ and $v'_j < v'_{j+1}$.

*Proof* Without loss of generality we can assume that $p = \bigoplus_{i=1}^{I} v_i \gamma^{\eta_i}$, with $\eta_i < \eta_{i+1}$, $i = 1, \dots, I-1$. In $\mathcal{T}_{per}[\gamma]$, we identify all elements $s$ with $sy^*$, hence can also identify $p$ and

$$p' = \bigoplus_{i=1}^{I} \left( \bigoplus_{j=1}^{i} v_j \right) \gamma^{\eta_i}$$

as $p\gamma^* = p'\gamma^*$. Hence, $v_i' \leq v'_{i+1}$. If $v_i' = v'_{i+1}$ we can write $v_i'\gamma^{\eta_i} \oplus v'_{i+1}\gamma^{\eta_{i+1}} = v_i'(\gamma^{\eta_i} \oplus \gamma^{\eta_{i+1}}) = v_i'\gamma^{\eta_i}$. Therefore, we can write $p'$ as $\bigoplus_{j=1}^{J} v_j'\gamma^{\eta'_j}$ with $v_j' < v_{j+1}$ and $J \leq I$. $\square$

**Definition 9** (Ultimately Cyclic Series in $\mathcal{T}_{per}[\gamma]$) : A series $s \in \mathcal{T}_{per}[\gamma]$ is said to be ultimately cyclic if it can be written as $s = p \oplus q(\gamma^\eta \delta^\tau)^*$, where $\eta, \tau \in \mathbb{N}$ and $p, q$ are polynomials in $\mathcal{T}_{per}[\gamma]$.

An element $s \in \mathcal{T}[\gamma]$ has a three dimensional graphical representation in $\mathbb{Z}_{max} \times \mathbb{Z}_{max} \times \mathbb{Z}$. Given a series $s = \bigoplus_i v_i \gamma^i \in \mathcal{T}[\gamma]$, this graphical representation is obtained by depicting for every $i$ the release-time function $R_{v_i} : \mathbb{Z}_{max} \to \mathbb{Z}_{max}$ of the coefficient $v_i$ in the (input-time $\times$ output-time)-plane of $i$.

**Example 7** For the graphical representation of the polynomial $p = (\delta^1 \Delta_{4|4} \delta^{-1} \oplus \delta^{-2} \Delta_{4|4})\gamma^0 \oplus (\delta^5 \Delta_{4|4} \delta^{-1} \oplus \delta^2 \Delta_{4|4})\gamma^2 \oplus (\delta^5 \Delta_{4|4} \oplus \delta^6 \Delta_{4|4} \delta^{-1})\gamma^4 \in \mathcal{T}_{per}[\gamma]$, respectively its representative

$$p\gamma^* = (\delta^1 \Delta_{4|4} \delta^{-1} \oplus \delta^{-2} \Delta_{4|4})\gamma^0 \oplus (\delta^1 \Delta_{4|4} \delta^{-1} \oplus \delta^{-2} \Delta_{4|4})\gamma^1, \\ (\delta^5 \Delta_{4|4} \delta^{-1} \oplus \delta^2 \Delta_{4|4})\gamma^2 \oplus (\delta^5 \Delta_{4|4} \delta^{-1} \oplus \delta^2 \Delta_{4|4})\gamma^3 \\ \oplus (\delta^5 \Delta_{4|4} \oplus \delta^6 \Delta_{4|4} \delta^{-1})\gamma^4 \oplus (\delta^5 \Delta_{4|4} \oplus \delta^6 \Delta_{4|4} \delta^{-1})\gamma^5 \oplus \dots,$$

see Fig. 6. The slices in the (I/O-time)-plane for the event-shift values $k = 0, 1$ are illustrated in Fig. 7a. These slices correspond to the release-time function $R_{\delta^1 \Delta_{4|4} \delta^{-1} \oplus \delta^{-2} \Delta_{4|4}}$ of the coefficient $\delta^1 \Delta_{4|4} \delta^{-1} \oplus \delta^{-2} \Delta_{4|4}$ for $\gamma^0$ (resp. $\gamma^1$) in $p$. The slices for $k = 2, 3$ and $k \geq 4$
<caption>**Fig. 6** 3D representation of polynomial</caption>

$$p = (\delta^1 \Delta_{4|4} \delta^{-1} \oplus \delta^{-2} \Delta_{4|4}) \gamma^0 \oplus (\delta^5 \Delta_{4|4} \delta^{-1} \oplus \delta^2 \Delta_{4|4}) \gamma^2 \oplus (\delta^5 \Delta_{4|4} \oplus \delta^6 \Delta_{4|4} \delta^{-1}) \gamma^4.$$

<figure><img src="image_8.png" /></figure>

are shown in Fig. 7b and c. To improve readability, the graphical representation for elements $s \in \mathcal{T}[\llbracket \gamma \rrbracket]$ has been truncated to non-negative values in Figs. 6 and 7.

An important subdioid of $\mathcal{T}[\llbracket \gamma \rrbracket]$ is the dioid $M_{in}^{ax}[\llbracket \gamma, \delta \rrbracket]$. This dioid is obtained by restricting the coefficients $v$ to the set $\{\varepsilon, \delta^\tau\}$ of T-operators, i.e., an element in $M_{in}^{ax}[\llbracket \gamma, \delta \rrbracket]$ is written as $\bigoplus_i \delta^{\tau_i} \gamma^{n_i}$ with $\tau_i, n_i \in \mathbb{Z}$. This dioid has been extensively studied, e.g. Gaubert and Klimann (1991) and Baccelli et al. (1992). The product of two monomials

<figure><img src="image_9.png" /><figcaption>**Fig. 7** Slices of the coefficients of $p$ in the (I/O-time)-plane. **a** $\mathcal{R}_{\delta^1 \Delta_{4|4} \delta^{-1} \oplus \delta^{-2} \Delta_{4|4}}$, **b** $\mathcal{R}_{\delta^5 \Delta_{4|4} \delta^{-1} \oplus \delta^2 \Delta_{4|4}}$ and **c** $\mathcal{R}_{\delta^5 \Delta_{4|4} \delta^{-6} \Delta_{4|4} \delta^{-1}}$</figcaption></figure>
γ<sup>n1</sup>δ<sup>f1</sup>, γ<sup>n2</sup>δ<sup>f2</sup> ∈ M<sub>in</sub><sup>ax</sup> [[γ, δ]] is obtained by, γ<sup>n1</sup>δ<sup>f1</sup> ⊗ γ<sup>n2</sup>δ<sup>f2</sup> = γ<sup>n1+n2</sup>δ<sup>f1+f2</sup>. Moreover, Eq. 19 is simplified to γ<sup>n1</sup>δ<sup>f1</sup> ≤ γ<sup>n2</sup>δ<sup>f2</sup> ⇔ (n<sub>1</sub> ≥ n<sub>2</sub> and t<sub>1</sub> ≤ t<sub>2</sub>), and as a consequence of Eq. 10,

$$
\gamma^n \delta^{f1} \oplus \gamma^n \delta^{f2} = \gamma^n \delta^{\max(t_1, t_2)}, \quad \gamma^{n1} \delta^t \oplus \gamma^{n2} \delta^t = \gamma^{\min(n_1, n_2)} \delta^t. \quad (20)
$$

A comprehensive description of calculations with series in $M_{in}^{ax}$ [[γ, δ]] can be found in Baccelli et al. (1992). It is well known that the input-output behavior of a standard TEG can be described by a transfer function matrix composed of ultimately cyclic series in $M_{in}^{ax}$ [[γ, δ]]. Moreover, based on $M_{in}^{ax}$ [[γ, δ]], methods for performance evaluation and controller synthesis have been introduced for TEGs, e.g. Gaubert and Klimann (1991), Maia et al. (2003), and Hardouin et al. (2017). In (Hardouin et al. 2009), software tools have been made available for computations in $M_{in}^{ax}$ [[γ, δ]]. The dioid $M_{in}^{ax}$ [[γ, δ]] plays a key role in this paper. In particular, in Section 4, we show that all relevant operations on ultimately cyclic series $s \in \mathcal{T}_{per}[[\gamma]]$ can be reduced to operations on matrices in $M_{in}^{ax}$ [[γ, δ]]. We can therefore use the existing tools for $M_{in}^{ax}$ [[γ, δ]] to study TEGs under periodic PS.

3.3 Modeling of TEGsPS in $\mathcal{T}_{per}[\gamma]$

A TEG under periodic PS operating under the earliest functioning rule admits a representa-
tion in $\mathcal{T}_{per}[\gamma]$ of the form

$$
x = Ax \oplus Bu, \quad y = Cx. \tag{21}
$$

This is reminiscent of the state space form in "classical" systems theory. In the sequel, we will therefore refer to this representation as a state space model. **x** (resp. **u**, **y**) refers to the vector of dater functions of internal (resp. input, output) transitions. The matrices **A** ∈ **T**<sub>per</sub>[[**γ**]]<sup>n×n</sup>, **B** ∈ **T**<sub>per</sub>[[**γ**]]<sup>n×g</sup> and **C** ∈ **T**<sub>per</sub>[[**γ**]]<sup>p×n</sup> describe the influence of transitions on each other, encoded by operators in **T**<sub>per</sub>[[**γ**]]. Hence, **n** refers to the number of internal transitions of the TEGPS, while **p** and **q** are the number of output and input transitions. Let us consider a path constituted by the arcs (t<sub>j</sub>, p<sub>i</sub>) and (p<sub>i</sub>, t<sub>o</sub>) with a synchronization of transition t<sub>o</sub> by a periodic signal S<sub>o</sub>. The influence of transition t<sub>j</sub> on transition t<sub>o</sub> is coded as an operator

v_{t_o} \delta^{(\phi)_i} \gamma^{(\mathcal{M}_0)_i}

where $v_{t_o}$ is the operator representation of the signal $S_o$ corresponding to the PS of $t_o$ (see Example 6), $(\phi)_i$ is the holding time of place $p_i$ and $(\mathcal{M}_0)_i$ is the initial marking of $p_i$.

Example 8 Recall the TEGPS in Fig. 2 with PS of transition $t_2$ by the signal, $\forall j \in \mathbb{Z}$

$$
S_2(t) = \begin{cases} 1 & \text{if } t \in \{1 + 20j\}, \\ 0 & \text{otherwise.} \end{cases}
$$
As $\omega = 20$, $I = 0$, $n_0 = 1$, according to Proposition 5, $v_{S_2} = \delta^1 \Delta_{20|20} \delta^{-1}$. The influence of $t_3$ on transition $t_2$ via the path $(t_3, p_2)(p_2, t_2)$, is coded by the operator $v_{S_2} \delta^0 \gamma^2 = v_{S_2} \gamma^2 = \delta^1 \Delta_{20|20} \delta^{-1} \gamma^2$. Moreover, by assigning a dater function $u$ (resp. $x_1, x_2, y$) to transition $t_1$ (resp. $t_2, t_3, t_4$), the earliest functioning of the TEGPS is described in state space form
$$ \mathbf{x} = \mathbf{A}\mathbf{x} \oplus \mathbf{B}u; \mathbf{y} = \mathbf{C}\mathbf{x}, \text{ where} $$

$$
\mathbf{A} = \begin{bmatrix} \varepsilon & \delta^1 \Delta_{20|20} \delta^{-1} \gamma^2 \\ \delta^{10} & \varepsilon \end{bmatrix}, \quad \mathbf{B} = \begin{bmatrix} \delta^1 \Delta_{20|20} \delta^{-1} \\ \varepsilon \end{bmatrix}, \quad \mathbf{C} = [\varepsilon \quad \mathbf{e}].
$$
According to Theorem 1, the least solution of equation $\mathbf{x} = \mathbf{A}\mathbf{x} \oplus \mathbf{B}u$ is $\mathbf{x} = \mathbf{A}^*\mathbf{B}u$.
Therefore, the transfer function matrix $\mathbf{H}$ of a TEGPS can be obtained by $\mathbf{y} = \mathbf{H}u =$
CA*Bu. In Trunk et al. (2018) it was shown that the entries of the transfer function matrix are ultimately cyclic series in $\mathcal{T}_{per}[\gamma]$. In order to compute this transfer function matrix, to compute system compositions, and to obtain control, we have to perform addition, multiplication and the Kleene star operation of series in $\mathcal{T}_{per}[\gamma]$. In the next section, we show how these operations between series in $\mathcal{T}_{per}[\gamma]$ can be reduced to operations between matrices in $M_{in}^{ax}[\gamma, \delta]$.

## 4 Core representation of a series in $\mathcal{T}_{per}[\gamma]$

In this section, we propose a specific decomposition of ultimately cyclic series in $\mathcal{T}_{per}[\gamma]$. We show that such series $s \in \mathcal{T}_{per}[\gamma]$ with period $\omega$ can always be represented as $s = \mathbf{m}_{\omega}\mathbf{Q}\mathbf{b}_{\omega}$ where $\mathbf{Q}$ is a square matrix in $M_{in}^{ax}[\gamma, \delta]$ of size $\omega \times \omega$, $\mathbf{m}_{\omega}$ is a row vector defined as

$$ \mathbf{m}_{\omega} := [ \Delta_{\omega|1} \quad \delta^{-1} \Delta_{\omega|1} \quad \dots \quad \delta^{1-\omega} \Delta_{\omega|1} ] \quad (22) $$

and $\mathbf{b}_{\omega}$ is a column vector defined as

$$ \mathbf{b}_{\omega} := [ \Delta_{1|\omega} \delta^{1-\omega} \quad \dots \quad \Delta_{1|\omega} \delta^{-1} \quad \Delta_{1|\omega} ]^T. \quad (23) $$

This representation is called core representation with core matrix $\mathbf{Q}$. We first demonstrate how to obtain this form on a small example and then provide a formal proof.

**Example 9** Consider the following series in $\mathcal{T}_{per}[\gamma]$,

$$ s = \Delta_{2|2} \oplus \delta^1 \Delta_{2|2} \delta^{-1} \oplus \delta^2 \Delta_{2|2} \gamma^2 (\delta^2 \gamma^2)^*. $$

Because of $\Delta_{\omega|\omega} = \Delta_{\omega|b}\Delta_{b|\omega}$ (Remark 1) and $\delta^{\omega}\Delta_{\omega|\omega} = \Delta_{\omega|\omega}\delta^{\omega}$, see Eq. 12, and as $\gamma$ commutes with all T-operators, this series can be rewritten as

$$ s = \Delta_{2|1} \underbrace{\mathbf{e} \quad \Delta_{1|2} \oplus \delta^{-1} \Delta_{2|1}}_{M_1} \underbrace{\delta^1 \quad \Delta_{1|2} \delta^{-1} \oplus \Delta_{2|1}}_{M_2} \underbrace{\delta^1 \gamma^2 (\delta^1 \gamma^2)^*}_{S_1} \Delta_{1|2}. $$

Clearly $M_1, M_2$ and $S_1$ are elements in $M_{in}^{ax}[\gamma, \delta]$. We now can rewrite $s$ in the core representation,

$$ s = \underbrace{[ \Delta_{2|1} \quad \delta^{-1} \Delta_{2|1} ]}_{\mathbf{m}_2} \underbrace{\left[ \begin{array}{cc} \varepsilon & \varepsilon \oplus \delta^1 \gamma^2 (\delta^1 \gamma^2)^* \\ \delta^1 & \varepsilon \end{array} \right]}_{\mathbf{Q}} \underbrace{\left[ \begin{array}{c} \Delta_{1|2} \delta^{-1} \\ \Delta_{1|2} \end{array} \right]}_{\mathbf{b}_2}, $$

which is in the required form.

**Proposition 7** Let $s = \bigoplus_i v_i \gamma^i \in \mathcal{T}_{per}[\gamma]$ be an $\omega$-periodic series, then $s$ can be written as $s = \mathbf{m}_{\omega}\mathbf{Q}\mathbf{b}_{\omega}$, where $\mathbf{Q} \in M_{in}^{ax}[\gamma, \delta]^{\omega \times \omega}$ and $\mathbf{m}_{\omega}, \mathbf{b}_{\omega}$ have the form Eqs. 22 and 23.

**Proof** $s$ being an $\omega$-periodic series implies that all coefficients $v_i$ of $s$ are $\omega$-periodic T-operators. Then, due to Proposition 3, all coefficients can be expressed in canonical form $v_i = \bigoplus_{j=1}^{J_i} \delta^{\tau_{ij}} \Delta_{\omega|\omega} \delta^{\tau'_{ij}}$ with $J_i \le \omega$ and $-\omega < \tau'_{ij} \le 0$. Then $s$ can be rewritten as

$$ s = \bigoplus_i \left( \bigoplus_{j=1}^{J_i} \delta^{\tau_{ij}} \Delta_{\omega|\omega} \delta^{\tau'_{ij}} \right) \gamma^i. $$
387 By using $\Delta_{\omega|\omega} = \Delta_{\omega|1}\Delta_{1|\omega}$ (Remark 1), $\delta^\omega \Delta_{\omega|1} = \Delta_{\omega|1}\delta^1$ Eq. 12 and $v\gamma = \gamma v$, $\forall v \in \mathcal{T}$,

388 the series s is written as

$$s = \bigoplus_i \left( \bigoplus_{j=1}^{J_i} \delta^{\tilde{\tau}_{ij}} \Delta_{\omega|1} \delta^{\hat{\tau}_{ij}} \gamma^i \Delta_{1|\omega} \delta^{\tau'_{ij}} \right),$$

389 where $-\omega < \tilde{\tau}_{ij} = \tau_{ij} - [\tau_{ij}/\omega]\omega \le 0$ and $\hat{\tau}_{ij} = [\tau_{ij}/\omega]$. Observe that $-\omega < \tilde{\tau}_{ij}$, $\tau'_{ij} \le 0$

390 hence we can express s by

$$s = [\Delta_{\omega|1} \delta^{-1} \Delta_{\omega|1} \cdots \delta^{1-\omega} \Delta_{\omega|1}] \left( \bigoplus_i \left( \bigoplus_{j=1}^{J_i} \mathbf{Q}_{ij} \right) \right) \begin{bmatrix} \Delta_{1|\omega} \delta^{1-\omega} \\ \vdots \\ \Delta_{1|\omega} \delta^{1-\omega} \\ \Delta_{1|\omega} \end{bmatrix}.$$

391 where the entry $(\mathbf{Q}_{ij})_{1-\tilde{\tau}_{ij}, \omega+\tau'_{ij}} = \delta^{\tilde{\tau}_{ij}} \gamma^i$ and all other entries of $\mathbf{Q}_{ij}$ are equal to $\varepsilon$. Hence,

392 $s$ is in the required form $s = \mathbf{m}_\omega \mathbf{Q}\mathbf{b}_\omega$, where $\mathbf{Q} = \bigoplus_i \left( \bigoplus_{j=1}^{J_i} \mathbf{Q}_{ij} \right)$. $\square$

393 Let us note that the core $\mathbf{Q}$ of a series $s \in \mathcal{T}_{per}[\gamma]$ is not unique. In other words, we can

394 express the same series with different cores, i.e., we may have $s = \mathbf{m}_\omega \mathbf{Q}\mathbf{b}_\omega = \mathbf{m}_\omega \tilde{\mathbf{Q}}\mathbf{b}_\omega$ with

395 $\mathbf{Q}, \tilde{\mathbf{Q}} \in \mathcal{M}_{in}^{ax}[[\gamma, \delta]]^{\omega \times \omega}$ but $\mathbf{Q} \neq \tilde{\mathbf{Q}}$. We illustrate this in the following example.

396 Example 10 Recall the series $s = \Delta_{2|2} \oplus \delta^1 \Delta_{2|2} \delta^{-1} \oplus \delta^2 \gamma^2 (\delta^2 \gamma^2)^* \Delta_{2|2}$ given in Example

397 9. The series s can be expressed by $\mathbf{m}_2 \tilde{\mathbf{Q}}\mathbf{b}_2$ where,

$$\tilde{\mathbf{Q}} = \begin{bmatrix} e & e \oplus \delta^1 \gamma^2 (\delta^1 \gamma^2)^* \\ \delta^1 & \varepsilon \end{bmatrix}.$$

398 Clearly $\tilde{\mathbf{Q}} \neq \mathbf{Q}$ see Example 9. However, $\tilde{\mathbf{Q}}$ is a valid core of s since

$$\mathbf{m}_2 \tilde{\mathbf{Q}} \mathbf{b}_2 = \mathbf{m}_2 \begin{bmatrix} \Delta_{1|2} \delta^{-1} \oplus \Delta_{1|2} \oplus \delta^1 \gamma^2 (\delta^1 \gamma^2)^* \Delta_{1|2} \\ \delta^1 \Delta_{1|2} \delta^{-1} \end{bmatrix}.$$

399 Because of Eq. 10 $\Delta_{1|2} \delta^{-1} \oplus \Delta_{1|2} = \Delta_{1|2}(\delta^{-1} \oplus \delta^0) = \Delta_{1|2}$, and therefore

$$\begin{aligned} \mathbf{m}_2 \tilde{\mathbf{Q}} \mathbf{b}_2 &= [\Delta_{2|1} \delta^{-1} \Delta_{2|1}] \begin{bmatrix} \Delta_{1|2} \oplus \delta^1 \gamma^2 (\delta^1 \gamma^2)^* \Delta_{1|2} \\ \delta^1 \Delta_{1|2} \delta^{-1} \end{bmatrix} \\ &= \Delta_{2|1} \Delta_{1|2} \oplus \Delta_{2|1} \delta^1 \gamma^2 (\delta^1 \gamma^2)^* \Delta_{1|2} \oplus \delta^{-1} \Delta_{2|1} \delta^1 \Delta_{1|2} \delta^{-1} \\ &= \Delta_{2|2} \oplus \delta^1 \Delta_{2|2} \delta^{-1} \oplus \delta^2 \gamma^2 (\delta^2 \gamma^2)^* \Delta_{2|2} = s. \end{aligned}$$

400 To show how the core form can be used to perform basic operations between ultimately

401 cyclic series in $\mathcal{T}_{per}[\gamma]$ we first elaborate some properties of the $\mathbf{m}_\omega$-vector and $\mathbf{b}_\omega$-vector.

402 The scalar product $\mathbf{m}_\omega \mathbf{b}_\omega$ of these two vectors is the identity e:

$$\begin{aligned} \mathbf{m}_\omega \otimes \mathbf{b}_\omega &= \delta^0 \Delta_{\omega|1} \Delta_{1|\omega} \delta^{1-\omega} \oplus \cdots \oplus \delta^{1-\omega} \Delta_{\omega|1} \Delta_{1|\omega} \delta^0 \\ &= \delta^0 \Delta_{\omega|\omega} \delta^{1-\omega} \oplus \cdots \oplus \delta^{1-\omega} \Delta_{\omega|\omega} \delta^0 = e, \end{aligned} \quad (24)$$

403 where the latter equality holds because of Proposition 4. The dyadic product $\mathbf{b}_\omega \otimes \mathbf{m}_\omega$ is a

404 square matrix in $\mathcal{M}_{in}^{ax}[[\gamma, \delta]]$ denoted by $\mathbf{N}$. For $i, j \in \{1, \dots, \omega\}$, the entry $(\mathbf{b}_\omega \otimes \mathbf{m}_\omega)_{i,j}$

405 is given by,

$$(\mathbf{N})_{i,j} = (\mathbf{b}_\omega \otimes \mathbf{m}_\omega)_{i,j} = \Delta_{1|\omega} \delta^{(i-j)+(1-\omega)} \Delta_{\omega|1}.$$
Then, because of $\Delta_{1|\omega}\delta^{-\omega} = \delta^{-1}\Delta_{1|\omega}$ and $\Delta_{1|\omega}\delta^n\Delta_{\omega|1} = \Delta_{1|1} = e$ for $-\omega < n \le 0$, see
Remark 1,

$$ (\mathbf{N})_{i,j} = \begin{cases} e, & j \le i, \\ \delta^{-1}, & j > i, \end{cases} \qquad 407 $$

i.e.,

408

$$ \mathbf{N} = \mathbf{b}_{\omega} \otimes \mathbf{m}_{\omega} = \begin{bmatrix} e & \delta^{-1} & \cdots & \delta^{-1} \\ \vdots & \vdots & \ddots & \vdots \\ \vdots & \vdots & \ddots & \delta^{-1} \\ e & \cdots & \cdots & e \end{bmatrix}. \qquad (25) $$

**Proposition 8** (Trunk et al. 2018) The following relations hold:

409

$$ \mathbf{N} \oplus \mathbf{I} = \mathbf{N}, $$

$$ \mathbf{N} \otimes \mathbf{N} = \mathbf{N}, $$

$$ \mathbf{N} \otimes \mathbf{b}_{\omega} = \mathbf{b}_{\omega}, $$

$$ \mathbf{m}_{\omega} \otimes \mathbf{N} = \mathbf{m}_{\omega}. $$

**4.1 Greatest core matrix**

410

From Example 10 it is clear that a series $s \in \mathcal{T}_{per}[\gamma]$ may have several core representations.

In the following, we show that a series $s \in \mathcal{T}_{per}[\gamma]$ admits a unique greatest core, denoted

$\hat{\mathbf{Q}}$, i.e, $s = \mathbf{m}_{\omega}\hat{\mathbf{Q}}\mathbf{b}_{\omega}$ and $\hat{\mathbf{Q}} \ge \mathbf{Q}$ for all core matrices $\mathbf{Q}$ such that $s = \mathbf{m}_{\omega}\mathbf{Q}\mathbf{b}_{\omega}$. Note that, the inequality is in the sense of the dioid $M_{in}^{ax}[\gamma, \delta]$. This decomposition $s = \mathbf{m}_{\omega}\hat{\mathbf{Q}}\mathbf{b}_{\omega}$ is particularly useful to compute residuation of series in $\mathcal{T}_{per}[\gamma]$.

**Proposition 9** For $D \in \mathcal{T}[\gamma]^{1 \times \omega}$ and $P \in \mathcal{T}[\gamma]^{\omega \times 1}$ one has:

416

$$ \mathbf{m}_{\omega} \triangleleft D = \mathbf{b}_{\omega} \otimes D, \qquad (26) $$

$$ P \triangleleft \mathbf{b}_{\omega} = P \otimes \mathbf{m}_{\omega}. \qquad (27) $$

For $O \in \mathcal{T}[\gamma]^{n \times \omega}$ and $G \in \mathcal{T}[\gamma]^{\omega \times n}$ one has:

417

$$ (ON) \triangleleft \mathbf{m}_{\omega} = ON \otimes \mathbf{b}_{\omega}, \qquad (28) $$

$$ \mathbf{b}_{\omega} \triangleleft (NG) = \mathbf{m}_{\omega} \otimes (NG). \qquad (29) $$

**Proof** By definition, $\mathbf{m}_{\omega} \triangleleft D$ is the greatest solution of inequality

418

$$ \mathbf{m}_{\omega} \otimes X \le D. \qquad (30) $$

Clearly since $\mathbf{m}_{\omega}\mathbf{b}_{\omega} = e, \mathbf{b}_{\omega}D$ satisfies Eq. 30 with equality. It remains to be shown that

$\mathbf{b}_{\omega}D$ is the greatest solution of Eq. 30. For this, assume that there exists $X' \ge \mathbf{b}_{\omega}D$ solving Eq. 30, i.e., $\mathbf{m}_{\omega}X' \le D$. Multiplication is order preserving, hence left multiplication by $\mathbf{b}_{\omega}$ results in

419
420
421
422

$$ \mathbf{N} \otimes X' \le \mathbf{b}_{\omega}D. $$

Furthermore, $X' \le \mathbf{N} \otimes X'$ as $\mathbf{N} = \mathbf{I} \oplus \mathbf{N}$. Hence, $X' \le \mathbf{b}_{\omega}D$ and therefore $X' = \mathbf{b}_{\omega}D$.

This proves that $\mathbf{b}_{\omega}D$ is indeed the greatest solution of Eq. 30. Similarly, $X = P\mathbf{m}_{\omega}$ solves $X\mathbf{b}_{\omega} \le P$ with equality. Suppose $X' \ge P\mathbf{m}_{\omega}$ is a solution, i.e., $X' \otimes \mathbf{b}_{\omega} \le P$. Right multiplication by $\mathbf{m}_{\omega}$ gives

423
424
425
426

$$ X' \le X' \otimes \mathbf{N} \le P \otimes \mathbf{m}_{\omega}. $$
427 Therefore $X' = P \otimes m_\omega$ and $P \otimes m_\omega$ is indeed the greatest solution, and hence
428 $P \otimes m_\omega = P \nparallel b_\omega$. To prove Eq. 28, note that by Proposition 8 ON $\otimes b_\omega \otimes m_\omega =$
429 ON. Therefore ON $\otimes b_\omega$ is a solution of $X \otimes m_\omega \leq$ ON. Assume that $X' \geq$
430 ON $\otimes b_\omega$ is another solution, i.e., $X'm_\omega \leq$ ON. Right multiplication by $b_\omega$ results in
431 $X' \leq$ ON $\otimes b_\omega$. Hence, ON $\otimes b_\omega$ is the greatest solution of $X \otimes m_\omega \leq$ ON and
432 $X \otimes m_\omega \leq$ ON and ON $\otimes b_\omega = ON \nparallel m_\omega$. Equation 29 is shown analogously. $\square$

433 **Proposition 10** Let $m_\omega Qb_\omega \in \mathcal{T}_{per}[\gamma]$ be a decomposition of $s \in \mathcal{T}_{per}[\gamma]$. The greatest core matrix is given by $\hat{Q} = NQN$.

435 **Proof** Consider the inequality $m_\omega \tilde{X} b_\omega \leq s$. Because of Proposition 9, its greatest solution
436 $\tilde{X} = m_\omega \nparallel s \nparallel b_\omega = m_\omega \nparallel m_\omega Qb_\omega \nparallel b_\omega$ is given by

$$ \tilde{X} = b_{\omega}m_{\omega}Qb_{\omega}m_{\omega} = NQN = \hat{Q}. $$

437 Moreover, because of (Proposition 8)

$$ m_{\omega}\hat{Q}b_{\omega} = m_{\omega}NQNb_{\omega} = m_{\omega}Qb_{\omega} = s. $$

438

$\square$

## 4.2 Operations between core matrices

440 To perform addition and multiplication of two ultimately cyclic series $s_1 =$
441 $m_{\omega_1}Q_1b_{\omega_1}$, $s_2 = m_{\omega_2}Q_2b_{\omega_2} \in \mathcal{T}_{per}[\gamma]$ in core form, it is necessary to express the core
442 matrices $Q_1 \in M_{in}^{ax}[[\gamma, \delta]]^{\omega_1 \times \omega_1}$ and $Q_2 \in M_{in}^{ax}[[\gamma, \delta]]^{\omega_2 \times \omega_2}$ with identical dimensions.
443 This is possible by expressing both series with their least common period $\omega = \text{lcm}(\omega_1, \omega_2)$.

444 **Proposition 11** (Trunk et al. 2018)

445 A series $s = m_\omega Qb_\omega \in \mathcal{T}_{per}[\gamma]$ can be expressed with a multiple period $n\omega$ by extend-
446 ing the core matrix $Q$, i.e., $s = m_\omega Qb_\omega = m_{n\omega}Q'b_{n\omega}$, where $Q' \in M_{in}^{ax}[[\gamma, \delta]]^{n\omega \times n\omega}$ is
447 given by

$$ Q' = \begin{bmatrix} \Delta_{1|n}\delta^{1-n}NQN\Delta_{n|1} & \cdots & \Delta_{1|n}\delta^{1-n}NQN\delta^{1-n}\Delta_{n|1} \\ \vdots & \ddots & \vdots \\ \Delta_{1|n}NQN\Delta_{n|1} & \cdots & \Delta_{1|n}NQN\delta^{1-n}\Delta_{n|1} \end{bmatrix}. $$

448 **Proposition 12** (Sum of series (Trunk et al. 2018)) Let $s = m_\omega Qb_\omega$, $s' = m_\omega Q'b_\omega \in \mathcal{T}_{per}[\gamma]$. Then $s \oplus s' = m_\omega Q''b_\omega$, where $Q'' = Q \oplus Q'$.

450 **Proposition 13** (Product of series (Trunk et al. 2018)) Let $s = m_\omega Qb_\omega$, $s' = m_\omega Q'b_\omega \in \mathcal{T}_{per}[\gamma]$. Then $s \otimes s' = m_\omega Q''b_\omega$, where $Q'' = QNQ'$.

452 **Proposition 14** (Kleene star of series (Trunk et al. 2018)) Let $s = m_\omega Qb_\omega \in \mathcal{T}_{per}[\gamma]$. Then,

$$ s^* = m_{\omega}(QN)^*b_{\omega}. \qquad (31) $$

454 **Proposition 15** Let $s = m_\omega \hat{Q}b_\omega$, $s' = m_\omega \hat{Q}' b_\omega$ be ultimately cyclic series in $\mathcal{T}_{per}[\gamma]$ with $\hat{Q}$, respectively $\hat{Q}'$, their greatest core matrices. Then,

$$ s' \nparallel s = m_{\omega}(\hat{Q}' \nparallel \hat{Q})b_{\omega}, \quad s \nparallel s' = m_{\omega}(\hat{Q} \nparallel \hat{Q}')b_{\omega} $$
Proof

$$
\begin{align*}
(\mathbf{m}_\omega \hat{\mathbf{Q}}' \mathbf{b}_\omega) \diamond (\mathbf{m}_\omega \hat{\mathbf{Q}} \mathbf{b}_\omega) &= (\hat{\mathbf{Q}}' \mathbf{b}_\omega) \diamond (\mathbf{m}_\omega \diamond (\mathbf{m}_\omega \hat{\mathbf{Q}} \mathbf{b}_\omega)), \quad \text{(because of (3))} \\
&= (\hat{\mathbf{Q}}' \mathbf{b}_\omega) \diamond (\mathbf{b}_\omega \mathbf{m}_\omega \hat{\mathbf{Q}} \mathbf{b}_\omega), \quad \text{(because of (26))} \\
&= (\hat{\mathbf{Q}}' \mathbf{b}_\omega) \diamond (\hat{\mathbf{Q}} \mathbf{b}_\omega), \quad \text{(as } \mathbf{N}\hat{\mathbf{Q}} = \hat{\mathbf{Q}}, \text{ Proposition 10)} \\
&= (\hat{\mathbf{Q}}' \mathbf{b}_\omega) \diamond (\hat{\mathbf{Q}} \nparallel \mathbf{m}_\omega) \quad \text{(from (28) and Proposition 10)} \\
&= \mathbf{b}_\omega \diamond (\hat{\mathbf{Q}}' \diamond (\hat{\mathbf{Q}} \nparallel \mathbf{m}_\omega)), \quad \text{(because of (3))} \\
&= \mathbf{b}_\omega \diamond ((\hat{\mathbf{Q}}' \diamond \hat{\mathbf{Q}}) \nparallel \mathbf{m}_\omega) \quad \text{(because of (5))} \\
&= \mathbf{m}_\omega (\hat{\mathbf{Q}}' \diamond \hat{\mathbf{Q}}) \mathbf{b}_\omega, \quad \text{(because of Proposition 9).}
\end{align*}
$$

The proof of the second part of Proposition 15 is analogous.

<figure><img src="image_10.png" /></figure>

456

Due to Propositions 12, 13, 14 and 15, it is clear that computation of the sum and product, Kleene star operation and product residuation of ultimately cyclic series in $\mathcal{T}_{per}[\gamma]$ can be done based on the core of the series, i.e. in the dioid $M_{in}^{ax}[\gamma, \delta]$. Finally, let us note that this core form of series $s \in \mathcal{T}_{per}[\gamma]$ is similar to the core form of series $s \in \mathcal{E}[\delta]$, see (Trunk et al. 2017a). More generally the dioid $\mathcal{T}_{per}[\gamma]$ with periodic time-operators can be seen as the counter part of the dioid $\mathcal{E}[\delta]$, introduced in Cottenceau et al. (2014), with periodic event-operators. The dioid $\mathcal{E}[\delta]$ is useful to obtain transfer function matrices for WBTEG.

457

458

459

460

461

462

463

464

5 Output reference control

465

In this section, we address the following control problem for TEGs under periodic PS. A reference dater function $\bar{z}$ is given for the output $\bar{y}$. We want to determine the greatest input dater function $\bar{u}$ that leads to an output $\bar{y} \le \bar{z}$. The reference dater specifies that the firings of the output transition (which in a manufacturing context, may for example correspond to completion of workpieces) should occur no latter than given instants of time. This has to be achieved by firing the input transition as late as possible. In a manufacturing context, this may correspond to feeding raw material as late as possible. This kind of optimal output reference control is often called "just-in-time" control. For standard TEGs the problem of output reference control was studied in Baccelli et al. (1992), Cohen et al. (1989), Menguy et al. (1998), and Menguy et al. (2000). It is well known for standard TEGs, that the output to an arbitrary input dater function can simply be computed by using the transfer function model $h \in M_{in}^{ax}[[\gamma, \delta]]$ of the TEG and expressing the input dater as a series $u \in M_{in}^{ax}[[\gamma, \delta]]$. Then $y = h \otimes u$. Hence, the optimal control problem for standard TEGs simply amounts computing $u_{opt} = h \diamond z$, see Baccelli et al. (1992) and Cohen et al. (1989) for a detailed description. In the following, we show how the earliest response of a TEG under periodic PS can be computed based on its transfer function $h \in \mathcal{T}_{per}[\gamma]$ and then how the optimal just-in-time control problem for a TEG under periodic PS can be addressed. For this, we first need to provide some additional algebraic background.

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483
484 **5.1 Subdioids of $\mathcal{T}_{per}[\gamma]$**

Recall that an operator $v \in \mathcal{T}$ is called $\omega$-periodic if $\exists \omega \in \mathbb{N}$ such that $\forall k \in \mathbb{Z}_{max}, \mathcal{R}_v(k + \omega) = \omega + \mathcal{R}_v(k)$ (Definition 6) and that the set of $\omega$-periodic T-operators is denoted by $\mathcal{T}_\omega$. Analogously we say $s \oplus_i v_i \gamma^i \in \mathcal{T}_{per}[\gamma]$ is an $\omega$-periodic series, iff all coefficients are $\omega$-periodic T-operators, i.e., $\forall i, v_i \in \mathcal{T}_\omega$. The set of $\omega$-periodic series is denoted by $\mathcal{T}_\omega[\gamma]$.

489 **Proposition 16** The set of $\omega$-periodic series $\mathcal{T}_\omega[\gamma]$ with addition and multiplication given in Definition 8 is a complete subdioid of the dioid $\mathcal{T}_{per}[\gamma]$.

491 **Proof** According to Propositions 12 and 13, $\mathcal{T}_\omega[\gamma]$ is closed under (infinite) addition and multiplication. $\square$

493 **Remark 4** The subdioid $\mathcal{T}_1[\gamma]$ of $\mathcal{T}_{per}[\gamma]$, i.e. the set of 1-periodic series, is the dioid
494 $\mathcal{M}_{in}^{ax}[\gamma, \delta]$. Moreover, as any 1-periodic series is also $\omega$-periodic ($\omega \in \mathbb{N}$), $\mathcal{M}_{in}^{ax}[\gamma, \delta]$ is subdioid of $\mathcal{T}_\omega[\gamma]$ for any $\omega \in \mathbb{N}$.

496 Due to the subdioid structure of $\mathcal{T}_{per}[\gamma]$, one can define the canonical injection $\text{Inj} : \mathcal{M}_{in}^{ax}[\gamma, \delta] \to \mathcal{T}_{per}[\gamma]$, with $\text{Inj}(x) = x$. For a graphical illustration of this canonical injection see the following example.

499 **Example 11** Let us consider the series $s = \gamma^1 \delta^2 \oplus (\gamma^3 \delta^3 \oplus \gamma^5 \delta^4)(\gamma^3 \delta^2)^* \in \mathcal{M}_{in}^{ax}[\gamma, \delta]$,
500 with a graphical representation given in Fig. 8a. The graphical representation of the canonical injection $\text{Inj}(s) \in \mathcal{T}_{per}[\gamma]$ is shown in Fig. 8b. The series $s \in \mathcal{M}_{in}^{ax}[\gamma, \delta]$ (Fig. 8a)

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

(a) Graphical representation of $s \in \mathcal{M}_{in}^{ax}[\gamma, \delta]$.

(b) Graphical representation of $\text{Inj}(s) \in \mathcal{T}_{per}[\gamma]$.

**Fig. 8** Illustration of the canonical injection $\text{Inj} : \mathcal{M}_{in}^{ax}[\gamma, \delta] \to \mathcal{T}_{per}[\gamma]$ of the series $s = \gamma^1 \delta^2 \oplus (\gamma^3 \delta^3 \oplus \gamma^5 \delta^4)(\gamma^3 \delta^2)^* \in \mathcal{M}_{in}^{ax}[\gamma, \delta]$
corresponds to the event-shift/output-time plane for the input-time value 0 of the 3D representation of the series $\text{Inj}(s) \in \mathcal{T}_{\text{per}}[\gamma]$ (Fig. 8b). Moreover, the canonical injection $\text{Inj}(s) \in \mathcal{T}_{\text{per}}[\gamma]$ is 1-periodic, this means the coefficients $v_i$ of $\gamma^i$ are 1-periodic, i.e., $\mathcal{R}_{v_i}(t)$ are quasi 1-periodic. Therefore, the event-shift/output-time plane for the input-time value 1 corresponds to the series $\delta^1 s \in \mathcal{M}_{in}^{ax}[[\gamma, \delta]]$ and for the input-time value 2 to the series $\delta^2 s \in \mathcal{M}_{in}^{ax}[[\gamma, \delta]]$, etc.

**Lemma 1** Let $v\gamma^n \in \mathcal{T}_\omega[\gamma]$ be an $\omega$-periodic monomial. Then the residual $\text{Inj}^\omega(v\gamma^n)$ is given by

$$ \text{Inj}^\omega(v\gamma^n) = \delta^{\min\{0, \dots, \omega-1\}} (\mathcal{R}_{v_i}(t)-t) \gamma^n. \quad (32) $$

*Proof* By definition, $\text{Inj}^\omega(v\gamma^n)$ is the greatest solution $x \in \mathcal{M}_{in}^{ax}[[\gamma, \delta]]$ of the following inequality:

$$ v\gamma^n \ge \text{Inj}(x) = \text{Inj} \left( \bigoplus_i \gamma^{\eta_i} \delta^{\xi_i} \right) = \bigoplus_i \gamma^{\eta_i} \delta^{\xi_i}. \quad (33) $$

Clearly, the least $\eta_i$ such that inequality Eq. 33 holds are $n$ and thus,

$$ v\gamma^n \ge \bigoplus_i (\gamma^n \delta^{\xi_i}) = \gamma^n \delta^\tau. \quad (34) $$

where the latter equality holds for $\tau = \max_i(\xi_i)$, because of Eq. 20. Since the inequality $v\gamma^n \ge \gamma^n \delta^\tau$ in $\mathcal{T}_\omega[\gamma]$ holds iff the inequality $v \ge \delta^\tau$ in $\mathcal{T}_\omega$ holds, it remains to find the greatest $\tau$ such that $v \ge \delta^\tau$ holds. By considering the isomorphism between T-operators and release-time functions, see Eq. 13, this is equivalent to $\mathcal{R}_v(t) \ge \mathcal{R}_{\delta^\tau}(t)$, $\forall t \in \mathbb{Z}_{\max}$.

By using $\mathcal{R}_{\delta^\tau}(t) = \tau + t$, see Eq. 7, one obtains

$$ \mathcal{R}_v(t) \ge \tau + t \Leftrightarrow \tau \le \mathcal{R}_v(t) - t, \quad \forall t \in \mathbb{Z}_{\max}. \quad (35) $$

Since $\mathcal{R}_v$ is a quasi $\omega$-periodic function it is sufficient to evaluate the function for $\forall t \in \{0, \dots, \omega-1\}$. Therefore the greatest $\tau$ such that Eq. 35 (resp. Eq. 34) holds is

$$ \tau = \min_{t=0, \dots, \omega-1} (\mathcal{R}_v(t) - t). \quad \square \quad 520 $$

Lemma 1 can be extended to arbitrary series in $\mathcal{T}_\omega[\gamma]$. To do this, note that the canonical representation in Proposition 6 can be generalized to infinite sums.

**Proposition 17** Let $s = \bigoplus_i v_i \gamma^{n_i} \in \mathcal{T}_\omega[\gamma]$ be an $\omega$-periodic series in canonical representation. Then

$$ \text{Inj}^\omega(s) = \bigoplus_i \delta^{\min\{0, \dots, \omega-1\}} (\mathcal{R}_{v_i}(t)-t) \gamma^{n_i}. \quad (36) $$

*Proof* Consider $s = \bigoplus_i v_i \gamma^{n_i}$ in the canonical form, i.e., $n_i < n_{i+1}$ and $v_i < v_{i+1}$ and let $\mathcal{R}_{v_i}$ be the release-time function associated with $v_i$. Recall that $\text{Inj}^\omega(s)$ is the greatest solution $x$ in $\mathcal{M}_{in}^{ax}[[\gamma, \delta]]$ of inequality $\text{Inj}(x) \le s$. This is given by $\bigoplus_i \delta^{\tau_i} \gamma^{n_i}$ where $\tau_i$ is the greatest integer such that $\delta^{\tau_i} \le v_i$. Repeating the first step of the proof of Lemma 1, this is given by $\tau_i = \min_{t=0, \dots, \omega-1} (\mathcal{R}_{v_i}(t) - t)$. $\square$
5.1.1 Zero slice mapping $\Psi_{\omega} : \mathcal{T}_{\omega}[\gamma] \to \mathcal{M}_{in}^{ax}[\gamma, \delta]$

Recall that $\mathcal{M}_{in}^{ax}[\gamma, \delta]$ is a subdioid of $\mathcal{T}_{\omega}[\gamma]$, hence we can define a specific projection

from $\mathcal{T}_{\omega}[\gamma]$ into $\mathcal{M}_{in}^{ax}[\gamma, \delta]$ as follows.

Definition 10 Let $s = \bigoplus_i v_i \gamma^{n_i} \in \mathcal{T}_{\omega}[\gamma]$ be an $\omega$-periodic series, then

$$ \Psi_{\omega}(s) = \Psi_{\omega} \left( \bigoplus_i v_{is} \gamma^{n_i} \right) = \bigoplus_i \gamma^{n_i} \delta^{\mathcal{R}v_i(0)}. \quad (37) $$

This projection $\Psi_{\omega}$ has an intuitive graphical interpretation. For a given $s \in \mathcal{T}_{\omega}[\gamma]$ the series $\Psi_{\omega}(s) \in \mathcal{M}_{in}^{ax}[\gamma, \delta]$ corresponds to the slice in the event/output-time plane of the

3D representation of $s \in \mathcal{T}_{\omega}[\gamma]$ at the input-time value 0. Thus, this projection is also called zero-slice mapping.

Example 12 Consider the polynomial $p = (\delta^1 \Delta_{4|4} \delta^{-1} \oplus \delta^{-2} \Delta_{4|4}) \gamma^0 \oplus (\delta^5 \Delta_{4|4} \delta^{-1} \oplus$

$\delta^2 \Delta_{4|4}) \gamma^2 \oplus (\delta^5 \Delta_{4|4} \oplus \delta^6 \Delta_{4|4} \delta^{-1}) \gamma^4 \in \mathcal{T}_{per}[\gamma]$ from Example 7 with graphical

representation given in Fig. 6. Then,

$$ \Psi_4(p) = \delta^1 \gamma^0 \oplus \delta^5 \gamma^2 \oplus \delta^6 \gamma^4. $$

The series $\Psi_4(p)$ corresponds to the slice in the (event-shift/output-time)-plane for the input-time value $t = 0$ in the 3D representation of $p$, see Fig. 9a and b.

The projection $\Psi_{\omega}$ is by definition lower-semicontinuous, therefore $\Psi_{\omega}$ is residuated.

<figure><img src="image_13.png" /><figcaption>Fig. 9 Illustration of Projection $\Psi_4(p)$</figcaption></figure>
**Proposition 18** Let $s = \bigoplus_i \gamma^{n_i} \delta^{\tau_i} \in \mathcal{M}_{in}^{ax} [[\gamma, \delta]].$ The residual $\Psi_{\omega}^{\sharp}(s) \in \mathcal{T}_{\omega}[[\gamma]]$ of $s$ is 544

$$ \Psi_{\omega}^{\sharp}(s) = \bigoplus_{i} \gamma^{n_i} \delta^{\tau_i} \Delta_{\omega|\omega} = s \Delta_{\omega|\omega}. \quad (38) $$

*Proof* By definition of the resudiated mapping, $\Psi_{\omega}^{\sharp}(s) \in \mathcal{T}_{\omega}[[\gamma]]$ is the greatest solution of inequality 545

$$ s = \bigoplus_i \gamma^{n_i} \delta^{\tau_i} \geq \Psi_{\omega}(x). \quad (39) $$

We first show that Eq. 38 satisfies Eq. 39 with equality.

547

$$ \Psi_{\omega} \left( \bigoplus_i \gamma^{n_i} \delta^{\tau_i} \Delta_{\omega|\omega} \right) = \bigoplus_i \gamma^{n_i} \delta^{\mathcal{R}_{\bar{\delta}}^{\tau_i} \Delta_{\omega|\omega}} \quad (0) = \bigoplus_i \gamma^{n_i} \delta^{\tau_i}, $$

since $\mathcal{R}_{\delta^{\tau_i} \Delta_{\omega|\omega}}(0) = \tau_i + \lceil 0/\omega \rceil \omega = \tau_i$, see Eqs. 7 and 9. Taking into account that $\Psi_{\omega}$ is isotone, it remains to show that $\bigoplus_i \gamma^{n_i} \delta^{\tau_i} \Delta_{\omega|\omega}$ is the greatest solution of 548

$$ s = \bigoplus_i \gamma^{n_i} \delta^{\tau_i} = \Psi_{\omega}(x) \quad (40) $$

For this, let $x = \bigoplus_j v_j \gamma^{n_j}$ be an arbitrary series in $\mathcal{T}_{\omega}[[\gamma]]$. Then $\Psi_{\omega}(x) = \bigoplus_j \gamma^{n_j} \delta^{\mathcal{R}_{v_j}(0)}$. Clearly, to achieve equality we need $\eta_j = n_i$ and $\mathcal{R}_{v_j}(0) = \tau_i$. Furthermore, we are looking for the greatest $v_j \in \mathcal{T}_{\omega}$, such that $\tau_i = \mathcal{R}_{v_j}(0)$. Due to the canonical form (Proposition 3) we can write an $\omega$-periodic T-operator $v_j$ as $\bigoplus_{i=1}^{\omega} \delta^{\zeta_i} \Delta_{\omega|\omega} \gamma^{\zeta_i'}$ with $-\omega < \zeta_i' \le 0$. This operator corresponds to the release-time function 550

$$ \mathcal{R}_{v_j}(t) = \max_{i=1, \dots, \omega} \left( \zeta_i + \left\lceil \frac{\zeta_i' + t}{\omega} \right\rceil \omega \right). $$

553
554

Now we examine $\mathcal{R}_{v_j}(t)$ for $t=0$, thus

555

$$ \mathcal{R}_{v_j}(0) = \max_{i=1, \dots, \omega} \left( \zeta_i + \left\lceil \frac{\zeta_i'}{\omega} \right\rceil \omega \right). $$

Recall that $-\omega < \zeta_i' \le 0$, hence $\mathcal{R}_{v_j}(t) = \tau_i + \lceil (0+t)/\omega \rceil \omega$ is the greatest quasi $\omega$-periodic release-time function such that $\mathcal{R}_{v_j}(0) = \tau_i$. The corresponding greatest T-operator is accordingly $\delta^{\tau_i} \Delta_{\omega|\omega}$. $\square$ 556
557
558

556

557

<figure><img src="image_14.png" /></figure>

### 5.1.2 Dater functions and series in $\mathcal{M}_{in}^{ax} [[\gamma, \delta]]$ 559

A convenient way to compute the output of a TEG under periodic PS is to express its input and output dater functions as series in $\mathcal{M}_{in}^{ax} [[\gamma, \delta]]$. The following proposition gives a link between dater functions and series in $\mathcal{M}_{in}^{ax} [[\gamma, \delta]]$. 560
561
562

560

561

562

**Proposition 19** (Baccelli et al. 1992) A dater function $\bar{d}: \mathbb{Z} \to \mathbb{Z}_{max}$ can be expressed as a series $d \in \mathcal{M}_{in}^{ax} [[\gamma, \delta]]$, such that, 563
564

563

564

$$ d = \left( \bigoplus_{\{k \in \mathbb{Z} | -\infty < \bar{d} < +\infty\}} \gamma^k \delta^{\bar{d}} \right) \oplus \left( \bigoplus_{\{k \in \mathbb{Z} | \bar{d} = +\infty\}} \gamma^k \delta^{*} \right). \quad (41) $$

For a more detailed description of the link between dater functions and the associated series in $\mathcal{M}_{in}^{ax} [[\gamma, \delta]]$, see e.g. Baccelli et al. (1992) and Cohen et al. (1991). The impulse is a specific dater function, namely $\mathcal{I}(k) = -\infty$ if $k < 0$ and 0 otherwise. Hence, an impulse 565
566
567

565

566

567
568 as the input of a TEG corresponds to an infinity of firings of its input transition at time 0.

569 The $M_{in}^{ax}$ [[γ, δ]] series corresponding to an impulse is the unit element $e \in M_{in}^{ax}$ [[γ, δ]]
570 see Baccelli et al. (1992) and Cohen et al. (1991).

571 Moreover, a dater function $\bar{d}$ and its series representation $d \in M_{in}^{ax}$ [[γ, δ]] are related by

$$ \bar{d}(k) = (d\mathcal{I})(k) $$

572 The impulse response of a TEG can be readily expressed via the TEG transfer function

573 $h \in M_{in}^{ax}$ [[γ, δ]]. The dater function $\bar{y}_{\mathcal{I}}$ is the impulse response is characterized by

$$ \bar{y}_{\mathcal{I}}(k) = (h\mathcal{I})(k) $$

574 while the corresponding series is obtained by

$$ y_{\mathcal{I}} = h \otimes e = h. $$

575 Similarly, the response to an arbitrary input series $u$ (with dater function $\bar{u}$) is

$$ y = h \otimes u, $$

576 respectively

$$ \bar{y}(k) = (h\bar{u})(k) = (h(u\mathcal{I}))(k). $$

577 In contrast, the transfer function $h \in \mathcal{T}_{per}$ [[γ]] of a TEG under periodic PS is not entirely

578 characterized by the impulse response. As the impulse corresponds to an infinity of firings

579 at time 0, the impulse response of a TEG under periodic PS is characterized by the slice

580 in the (event-shift/output-time)-plane at the input-time value 0 of the 3D representation of

581 its transfer function $h \in \mathcal{T}_{per}$ [[γ]], see e.g., Example 12. Hence, for a TEG under periodic

582 PS with transfer function $h$, the impulse response $\bar{y} = (h\mathcal{I})$ corresponds to the series $y =$

583 $\Psi_{\omega}(h) \in M_{in}^{ax}$ [[γ, δ]], see Definition 10 and Example 12. It should be clear that in contrast

584 to standard TEGs, the impulse response of a TEG under periodic PS only provides partial

585 information of its transfer function. For TEGs under periodic PS, the above duality between

586 representing the output as counter function and series in $M_{in}^{ax}$ [[γ, δ]] reads as follows. Let

587 $h \in \mathcal{T}_{per}$ [[γ]] be the transfer function of the TEG under periodic PS and $\bar{u} \in \Sigma$, respectively

588 $u \in M_{in}^{ax}$ [[γ, δ]], be the input. Then we obtain the output counter function $\bar{y} \in \Sigma$ by

$$ \bar{y}(k) = (h\bar{u})(k), $$

589 and the corresponding output series $y \in M_{in}^{ax}$ [[γ, δ]] by

$$ y = \Psi_{\omega}(h \otimes \text{Inj}(u)). \quad (42) $$

590 Example 13 Recall the simple supply chain in Example 2 with the TEGPS model shown in

591 Fig. 2. The transfer function is $h = \delta^{11}(\gamma^2\delta^{20})^{*}\Delta_{20|20}\delta^{-1}$. This transfer function was com-

592 puted with the ETVO toolbox (Cottenceau et al. 2019) available online at: http://perso-laris.

593 univ-angers.fr/~cottenceau/etvo.html, this toolbox implements the algorithms given in this

594 section. Moreover, consider the following input dater function:

$$ \bar{u}(k) = \begin{cases} -\infty & \text{for } k < 0; \\ 0 & \text{for } k = 0; \\ 5 & \text{for } k = 1, 2; \\ 35 & \text{for } k = 3, 4, 5, 6; \\ \infty & \text{for } k \ge 7. \end{cases} \quad (43) $$

595 This dater function is interpreted as follows: the first product available for transport from

596 factory 1 to factory 2 is ready at time instant 0. The second and third at time instant 5. The

597 4th, 5th, 6th and 7th at time instant 35. According to Eq. 41, the series $u \in M_{in}^{ax}$ [[γ, δ]]
corresponding to this dater function is $u = \gamma^0\delta^0 \oplus \gamma^1\delta^5 \oplus \gamma^3\delta^{35} \oplus \gamma^7\delta^*$. The output
$y \in \mathcal{M}_{in}^{ax}[[\gamma, \delta]]$ of the system is computed as
598
599

$$
\begin{align*}
y &= \Psi_{\omega} (h \otimes \text{Inj}(u)) \\
&= \Psi_{\omega} (\delta^{11} (\gamma^2 \delta^{20})^* \Delta_{20|20} \delta^{-1} \otimes (\gamma^0 \delta^0 \oplus \gamma^1 \delta^5 \oplus \gamma^3 \delta^{35} \oplus \gamma^7 \delta^*) \\
&= \Psi_{\omega} (\delta^{11} \Delta_{20|20} \delta^{-1} (\gamma^2 \delta^{20})^* \otimes (\gamma^0 \delta^0 \oplus \gamma^1 \delta^5 \oplus \gamma^3 \delta^{35} \oplus \gamma^7 \delta^*) \\
&= \Psi_{\omega} ((\delta^{11} \Delta_{20|20} \delta^{-1} \oplus \delta^{31} \Delta_{20|20} \delta^{-16} \gamma^1 \oplus \delta^{51} \Delta_{20|20} \delta^{-6} \gamma^3) (\gamma^2 \delta^{20})^* \\
&\qquad \oplus \delta^{11} \Delta_{20|20} \delta^{-1} \gamma^7 (\gamma^2 \delta^2)^* \delta^*) \\
&= \Psi_{\omega} ((\delta^{11} \Delta_{20|20} \delta^{-1} \oplus \delta^{31} \Delta_{20|20} \delta^{-16} \gamma^1 \oplus \delta^{51} \Delta_{20|20} \delta^{-6} \gamma^3) (\gamma^2 \delta^{20})^* \\
&\qquad \oplus \delta^{11} \Delta_{20|20} \delta^{-1} \gamma^7 \delta^*) \\
&= (\delta^{11} \oplus \delta^{31} \gamma^1 \oplus \delta^{51} \gamma^3) (\gamma^2 \delta^{20})^* \oplus \delta^{11} \delta^* \gamma^7 \\
&= (\delta^{11} \oplus \delta^{31} \gamma^1 \oplus \delta^{51} \gamma^3 \oplus \delta^{71} \gamma^5 \oplus \delta^{91} \gamma^7 \oplus \dots) \oplus \delta^{11} \delta^* \gamma^7 \\
&= \delta^{11} \oplus \delta^{31} \gamma^1 \oplus \delta^{51} \gamma^3 \oplus \delta^{71} \gamma^5 \oplus \delta^* \gamma^7,
\end{align*}
$$

with associated dater function $\bar{y}$
600

$$
\bar{y}(k) = \begin{cases} -\infty & \text{for } k < 0; \\ 11 & \text{for } k = 0; \\ 31 & \text{for } k = 1, 2; \\ 51 & \text{for } k = 3, 4; \\ 71 & \text{for } k = 5, 6; \\ \infty & \text{for } k \ge 7. \end{cases}
$$

Hence, this implies that the first product is available at factory 2 at time instant 11, the
second and third at time instant 31, the 4th and 5th at time instant 51, and the 6th and 7th at
time instant 71.
601
602
603

5.2 Optimal Output Reference Control 604

The optimal output reference control problem for a TEG under periodic PS with a transfer
function $h \in \mathcal{T}_{per}[[\gamma]]$ is to find the greatest input dater $\bar{u}$ such that, $\forall k \in \mathbb{Z}$
605
606

$$
\bar{z}(k) \geq (h\bar{u}) (k), \quad (44)
$$

where $\bar{z}$ is a given reference dater.
607

If, instead, we represent the unknown input and the reference as series in $\mathcal{M}_{in}^{ax}[[\gamma, \delta]]$,
Eq. 44 is rephrased as
608
609

$$
z \geq \Psi_{\omega}(h \otimes \text{Inj}(u)), \qquad (45)
$$

where the series $z, u \in \mathcal{M}_{in}^{ax}[[\gamma, \delta]]$ correspond to the dater functions $\bar{z}$ and $\bar{u}$.
610

**Theorem 3** Let $h \in \mathcal{T}_{per}[[\gamma]]$ be the transfer function of a single-input single-output (SISO) TEG under periodic PS and $z \in \mathcal{M}_{in}^{ax}[[\gamma, \delta]]$ a given output reference for the system, then the optimal input $u_{opt}$, i.e., the greatest solution of Eq. 45, is
611
612
613

$$
u_{opt} = \text{Inj}^{\sharp}(h \diamond \Psi_{\omega}^{\sharp}(z)). \qquad (46)
$$
614 Proof As $\Psi_{\omega}$ is a residuated mapping (see Proposition 18), Eq. 46 is equivalent to $h \otimes \text{Inj}(u) \preceq \Psi_{\omega}^{\sharp}(z)$. This, in turn, is equivalent to $\text{Inj}(u) \preceq h \wedge \Psi_{\omega}^{\sharp}(z)$ as left multiplication in $\mathcal{T}_{\text{per}}[\llbracket \gamma \rrbracket]$ is residuated. Finally as $\text{Inj}$ is residuated (Proposition 17), the greatest solution of the latter inequality is Eq. 46. $\square$

618 Equation 46 is often referred to as the just-in-time solution. Note that the notation of greatest is in the sense of the order $\geq$ in the dioid $M_{in}^{ax}[\llbracket \gamma, \delta \rrbracket]$.

620 Example 14 Recall the supply chain of Example 2, which is modelled by the TEG under periodic PS given in Fig. 2 and has transfer function

$$h = \delta^{11} \Delta_{20|20} \delta^{-1} (\gamma^2 \delta^{20})^* \in \mathcal{T}_{\text{per}}[\llbracket \gamma \rrbracket].$$

622 Let us consider the following dater function (see Fig. 10), which describes at which instants of time goods from factory 1 need to be available at factory 2 at the latest.

$$\bar{z}(k) = \begin{cases} -\infty & \text{for } k < 0, \\ 25 & \text{for } k = 0, 1, \\ 45 + 15j & \text{for } k = 2 + j \text{ with } j \in \mathbb{N}_0. \end{cases}$$

624 The control problem is now, to compute $\bar{u}$, i.e. the maximal time when goods from factory 1 are ready to be shipped to factory 2, such that Eq. 44 respectively Eq. 45, holds. To apply Eq. 46, the dater function $\bar{z}$ is expressed by the series $z = \delta^{25} \oplus \gamma^2 \delta^{45} (\gamma^1 \delta^{15})^* \in M_{in}^{ax}[\llbracket \gamma, \delta \rrbracket]$. Then according to 18, $\Psi_{20}^{\sharp}(z) = z \Delta_{20|20} = \delta^{25} \Delta_{20|20} \oplus (\gamma^1 \delta^{15})^* (\gamma^2 \delta^{45} \Delta_{20|20})$ and

$$u_{opt} = \text{Inj}^{\sharp}(h \wedge \Psi_{20}^{\sharp}(z)) = (\delta^{1} \oplus \gamma^{2} \delta^{21} \oplus \gamma^{3} \delta^{41})(\gamma^{4} \delta^{60})^{*}.$$

629 where the latter equality has been computed using ETVO toolbox (Cottenceau et al. 2019). The response $y$ of the TEGPS to the optimal input $u_{opt}$ is

$$y = \Psi_2(h \otimes \text{Inj}(u_{opt})) = (\delta^{11} \oplus \gamma^2 \delta^{31} \oplus \gamma^3 \delta^{51})(\gamma^4 \delta^{60})^*.$$

631 This series corresponds to the dater function,

$$\bar{y}(k) = \begin{cases} -\infty & \text{for } k < 0, \\ 11 + 60j & \text{for } k = 4j \text{ and } k = 1 + 4j \text{ with } j \in \mathbb{N}_0, \\ 31 + 60j & \text{for } k = 2 + 4j \text{ with } j \in \mathbb{N}_0, \\ 51 + 60j & \text{for } k = 3 + 4j \text{ with } j \in \mathbb{N}_0. \end{cases}$$

632 Figure 10 illustrates the output reference $\bar{z}$ and $\bar{y}$ resulting from the optimal input $\bar{u}_{opt}$. Clearly, as required, $\bar{z} \geq \bar{y}$. This means, the goods are shipped from factory 1 as late as possible, but arrive in factory 2 in time to meet the production deadlines there.

635 Remark 5 Output reference control can be readily extended to multiple-input multiple-output (MIMO) TEGs under periodic PS. In this case the earliest behaviour of a TEG under periodic PS is modeled by a transfer function matrix $H \in \mathcal{T}_{\text{per}}[\llbracket \gamma \rrbracket^{p \times g}]$. Then the optimal output reference control problem is, for all $j = 1, \dots, p$,

$$z_j \geq \Psi_{\omega} \left( \bigoplus_{i=1}^{g} (H)_{j,i} \text{Inj}(u_i) \right), \quad (47)$$
<figure><img src="image_15.png" /><figcaption>Fig. 10 Output reference $\bar{z}$ and system response $\bar{y}$ to optimal input $\bar{u}_{opt}$</figcaption></figure>

where $z_j \in \mathcal{M}_{in}^{ax} [[\gamma, \delta]]$ represents the reference for the $j^{th}$ output and $u_i \in \mathcal{M}_{in}^{ax} [[\gamma, \delta]]$ is $i^{th}$ input of the system. As $\Psi_{\omega}$ is a lower semi-continuous mapping we can write Eq. 47 as, for $j = 1, \dots, p,$

$$z_j \geq \bigoplus_{i=1}^{g} \Psi_{\omega}((H)_{j,i} \text{Inj}(u_i)), \quad (48)$$

The latter set of $p$ inequalities, can be written as a set of $p * q$ simpler inequalities, i.e.,
$\forall j \in \{1, \dots, p\}$ and $\forall i \in \{1, \dots, g\}$,

$$z_j \geq \Psi_{\omega}((H)_{j,i} \text{Inj}(u_i)). \quad (49)$$

Observe that each of these inequalities has the form of Eq. 45. Hence, the optimal $i^{th}$ input $u_{i, opt} \in \mathcal{M}_{in}^{ax} [[\gamma, \delta]]$, i.e., the greatest $u_i$ that satisfies Eq. 49 for $j = 1, \dots, p$, is

$$u_{i, opt} = \bigwedge_{j=1}^{p} \left( \text{Inj}^{\sharp}((H)_{j,i} \setminus \Psi_{\omega}^{\sharp}(z_j)) \right).$$

Hence, the only difference to the SISO case is an additional infimum operation between series in $\mathcal{M}_{in}^{ax} [[\gamma, \delta]]$.

## 6 Conclusion

In this paper, we have introduced algebraic tools to obtain transfer function matrices for a subclass of Timed Event Graphs under Partial Synchronization, namely the case where partial synchronization of transitions is characterized by periodic signals. We have introduced the dioid $T_{per}[[\gamma]]$, which is a quotient dioid of formal power series in $\gamma$ with coefficients that are periodic time-operators. We have shown that all relevant operations on ultimately cyclic series $s$ in this dioid can be reduced to operations on matrices in the subdioid $\mathcal{M}_{in}^{ax} [[\gamma, \delta]]$. An advantage of this approach is that existing software tools for

649

650

651

652

653

654

655

656
standard TEGs in the dioid $M_{in}^{ax}[[\gamma, \delta]]$, e.g. Hardouin et al. (2009) can be applied to the more general class of TEGsPS with periodic PS. The more recent toolbox (Cottenceau et al. 2019), based also on Hardouin et al. (2009), implements the "translation process" from $T_{per}[[\gamma]]$ to $M_{in}^{ax}[[\gamma, \delta]]$. Moreover, based on transfer functions for this class of TEGsPS we have solved the corresponding optimal output reference control problem. In particular, the proposed control method provides the optimal control input under the "just-in-time" criterion. One possible extension of this work is to modify the control strategy such that online updates of the reference trajectory can be considered. This would allow the system to react to a change in customer demands, and will be considered in future work.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

674 References

675 Baccelli F, Cohen G, Olsder G, Quadrat J (1992) Synchronization and linearity: An algebra for discrete event systems. Wiley, New York

676 Cohen G, Moller P, Quadrat JP, Viot M (1989) Algebraic tools for the performance evaluation of discrete event systems. Proc IEEE 77(1):39-58

677 Cohen G, Gaubert S, Nikoukhah R, Quadrat JP (1991) Second order theory of min-linear systems and its application to discrete event systems. In: Proceedings of the 30th IEEE conference on decision and control, pp 1511-1516 vol 2. https://doi.org/10.1109/CDC.1991.261654

678 Cottenceau B, Hardouin L, Boimond JL (2014) Modeling and control of weight-balanced timed event graphs in dioids. IEEE Trans Autom Control 59(5):1219-1231. https://doi.org/10.1109/TAC.2013.2294822

679 Cottenceau B, Hardouin L, Trunk J (2019) Event and time variant operators. http://perso-laris.univ-angers.fr/cottenceau/etvo.html

680 David-Henriet X, Raisch J, Hardouin L, Cottenceau B (2014) Modeling and control for max-plus systems with partial synchronization. In: Proceedings of the 12th IFAC-IEEE international workshop on discrete event systems (WODES). France, Paris, pp 105-110

681 David-Henriet X, Raisch J, Hardouin L, Cottenceau B (2015) Modeling and control for (max, +)-linear systems with set-based constraints. In: IEEE international conference on automation science and engineering (CASE), pp 1369-1374. https://doi.org/10.1109/CoASE.2015.7294289

682 David-Henriet X, Hardouin L, Raisch J, Cottenceau B (2016) Model predictive control for discrete event systems with partial synchronization. Automatica 70:9-13

683 De Schutter B, van den Boom TJJ (2003) MPC for discrete-event systems with soft and hard synchronization constraints. Int J Control 76(1):82-94. https://doi.org/10.1080/0020717021000049188

684 Gaubert S, Klimann C (1991) Rational computation in dioid algebra and its application to performance evaluation of discrete event systems. In: Algebraic computing in control, Springer, pp 241-252

685 Hamaci S, Boimond JL, Lahaye S (2006) On modeling and control of discrete timed event graphs with multipliers using (min,+)-algebra

686 Hardouin L, Le Corronc E, Cottenceau B (2009) Minmaxgd a software tools to handle series in (max, +) algebra. In: SIAM conference on computational science and engineering, Miami. USA

687 Hardouin L, Shang Y, Maia CA, Cottenceau B (2017) Observer-based controllers for max-plus linear systems. IEEE Trans Autom Control 62(5):2153-2165. https://doi.org/10.1109/TAC.2016.2604562

688 Hardouin L, Cottenceau B, Shang Y, Raisch J (2018) Control and state estimation for max-plus linear systems. Foundations Trends®Syst Control 6(1):1-116. https://doi.org/10.1561/2600000013

689 Heidergott B, Olsder G, van der Woude J (2005) Max plus at work: Modeling and analysis of synchronized systems: A course on max-plus algebra and its applications (Princeton series in applied mathematics). Princeton University Press, Princeton
<table><tr><td>Maia CA, Hardouin L, Santos-Mendes R, Cottenceau B (2003) Optimal closed-loop control of timed event graphs in dioids. IEEE Trans Autom Control 48(12):2284-2287</td><td>709</td></tr><tr><td>Menguy E, Boimond JL, Hardouin L (1998) Optimal control of discrete event systems in case of updated reference input. In: IFAC conference on system structure and control, pp 601-607</td><td>710</td></tr><tr><td>Menguy E, Boimond JL, Hardouin L, Ferrier JL (2000) Just-in-time control of timed event graphs: update of reference input, presence of uncontrollable input. IEEE Trans Autom Control 45(11):2155-2159. https://doi.org/10.1109/9.887652</td><td>711</td></tr><tr><td>Trunk J, Cottenceau B, Hardouin L, Raisch J (2017a) Model decomposition of weight-balanced timed event graphs in dioids: Application to control synthesis. In: 20th IFAC world congress 2017, Toulouse, pp 13995-14002</td><td>712</td></tr><tr><td>Trunk J, Cottenceau B, Hardouin L, Raisch J (2017b) Output reference control for weight-balanced timed event graphs. IEEE, 4839-4846. https://doi.org/10.1109/CDC.2017.8264374</td><td>713</td></tr><tr><td>Trunk J, Cottenceau B, Hardouin L, Raisch J (2018) Model Decomposition of Timed Event Graphs under Partial Synchronization. In: 14th Workshop on Discrete Event Systems, vol 2018. Sorrento Coast, Italy, pp 209-216</td><td>714</td></tr><tr><td>Publisher's note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.</td><td>715</td></tr><tr><td></td><td>716</td></tr><tr><td></td><td>717</td></tr><tr><td></td><td>718</td></tr><tr><td></td><td>719</td></tr><tr><td></td><td>720</td></tr><tr><td></td><td>721</td></tr><tr><td></td><td>722</td></tr><tr><td></td><td>723</td></tr></table>

<table><tr><td>Publisher's note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.</td><td>724</td></tr><tr><td></td><td>725</td></tr></table>

<figure><img src="image_16.png" /></figure>

Johannes Trunk was born in 1985. He received the Master degree in Electrical Engineering from the Technische Universität Berlin, Germany, in 2014. He is currently a PhD student at both the Technische Universität Berlin and the Universität d'Angers, France. His research interests are modeling and control of discrete event systems with applicationsto transportation networks, computer networks and manufacturing systems. His PhD is supported by the Universität d'Angers, France.

<figure><img src="image_17.png" /></figure>

Bertrand Cottenceau was born in 1973. He received the Ph.D. degree, in 1999, and the Habilitation'a Diriger des Recherches, in 2015, from the University of Angers, France. He is currently an Full Professor at the University of Angers. His research interests include modeling, simulation and control of timed discrete event systems with applications in manufacturing systems and computer networks.
<figure><img src="image_18.png" /></figure>

**Laurent Hardouin** was born in 1967. He received the Ph.D degree from the University of Poitiers, France, in 1993, and the Habilitation à Diriger des Recherches from the University of Angers, France, in 2004. He is currently a Full Professor of dynamic systems, computer engineering, computer networks at the University of Angers. He specializes in discrete-event systems, max-plus algebra, interval analysis, with applications to computer networks, manufacturing systems, transportation systems and robotics.

<figure><img src="image_19.png" /></figure>

**Joerg Raisch** received the Dipl.-Ing. degree in engineering cybernetics, the Ph.D. degree, and the "habilitation" from Stuttgart University, Stuttgart, Germany. Since 2006, he has held the Chair of Control Systems in the Department of Electrical Engineering and Computer Science, Technische Universität (TU), Berlin, Germany. His main research interests are hybrid and hierarchical control, and control of timed discrete-event systems in tropical algebras, with applications in chemical, medical, and power systems engineering.

## Affiliations

Johannes Trunk<fnref n="1" /> · Bertrand Cottenceau<fnref n="2" /> · Laurent Hardouin<fnref n="2" /> · Joerg Raisch<fnref n="1" />

Bertrand Cottenceau
bertrand.cottenceau@univ-angers.fr

Laurent Hardouin
laurent.hardouin@univ-angers.fr

Joerg Raisch
raisch@control.tu-berlin.de

<footnote n="1">1 Technische Universität Berlin, Fachgebiet Regelungssysteme, Einsteinufer 17, D-10587 Berlin, Germany</footnote>

<footnote n="2">2 Université d'Angers, 62 Avenue Notre Dame du Lac, 49000 Angers France</footnote>
AUTHOR QUERIES

AUTHOR PLEASE ANSWER ALL QUERIES:

Q1. Johannes Trunk has been set as the corresponding author. Please check and advise if correct.

Q2. Please check affiliations if captured and presented correctly.