# Output feedback control for partially observable linear Max-Plus systems under temporal constraints *

Romain Jacobª, Saïd Amariª

ª LURPA, ENS Cachan, Univ. Paris-Sud, Université Paris-Saclay, 94235 Cachan, France

## Abstract

Combined use of Timed Event Graphs (TEG) and Max-Plus algebra is a well-known approach for handling timed behavior of discrete event systems. It has been used to tackle control problems with temporal constraints on the system states. However, in the current literature, most of the control approaches assume that system models are fully observable, which is a strong limitation in practice. Hence, we propose in this paper an output feedback control approach aiming to preserve time and robustness performances. We demonstrate that we can derive an efficient control law satisfying a set of constraints given easy-to-check a priori sufficient conditions on the system model. We illustrate our approach on a small traffic light problem.

**Key words:** Output feedback control; Timed event graphs; Max-Plus algebra; Timed-Petri nets; Control of constrained systems; Discrete Event Systems in Manufacturing

## 1 Introduction

A control problem commonly involves some temporal constraints to satisfy. They can take diverse forms (e.g., deadline, time intervals, validity duration, synchronization...,), which are encountered in a wide range of applications (e.g., semiconductor industry [16], automotive industry [3], chemical treatments [17], rail transport [15], robotics [21], communication networks [1]...).

A Timed Event Graph (TEG) is a subclass of Timed Petri nets which is useful for modeling timed behavior. It turns non-linearity of timed dynamics into a linear system of equations over the Max-Plus algebra [4]. Combined use of TEG and Max-Plus is a well-known approach in the literature initiated back in the 1960's [6] and it is still a very active field of research. This framework has been successfully applied to solve diverse control problems, such as dynamic scheduling [5, 15, 18], synchronization of switching models [21, 22], the disturbance decoupling problem [27], or just-in-time control [12, 20]. Both open loop [19, 25] and feedback [23, 27] control have been considered in order to solve model matching problems.

In this paper, we focus on the feedback control of Max-Plus linear systems under temporal constraints defined as maximal time laps set on the system states (e.g., the stripping time of a piece by immersion in an acid bath is defined by a time interval, it requires a minimum soak time but must not exceed a maximum time). This kind of problem has been addressed either using a temporal approach based on daters like in [2, 7, 14, 16, 24, 26] or its transformed version based on power series [9, 13], which is similar to Z-transform for conventional linear system theory. Even though they do address the control of temporal constraints, these previous works suffer from a strong limitation: they consider the system to control as fully observable, which is never the case in practice. Hence, we aim to derive an output feedback controller which preserves as much as possible the performances of the system (i.e., the cycle time and the robustness again disturbances) while only output events are considered as observable.

Hardouin et al. presented an observer design for Max-Plus linear systems which could solve our observability problem [10, 11]. However, in the general case, this approach provides an under-estimation of the states (i.e., $\hat{x} \le x$). We will show later on that we would need instead an over-estimation of the state in order to solve our control problem (see Rem.16). Equality is only obtained under restrictive conditions. In [8], the authors suggested to observe an expression $W \cdot x$ instead of the full state $x$, which can lead to an exact estimate un-

<footnote>* This paper was not presented at any IFAC meeting. Corresponding author is M. Jacob.

Email addresses: rjacob@ens-cachan.fr (Romain Jacob), samari@ens-cachan.fr (Saïd Amari).</footnote>
der slightly less restrictive conditions than in [11] (even though still quite restrictive). Starting from a conventional state feedback control $u(k) = F \cdot x(k-1)$, it allows to perform output feedback control by observing directly the expression of interest (i.e., $F \cdot x(k-1)$). However, this approach neglects the preservation of the cycle time and lead to poor time performances. Moreover, approaches from [8, 24] assume full controllability over the system which is not necessary in general. Finally, there are no simple interpretation of the sufficient conditions suggested in [8, 11, 24]. In other words, one can compute and test the conditions, but it gives no insight on reconfiguration strategies to solve the control problem if the conditions do not hold.

In this paper, we present an approach to directly derive an output feedback controller which is an extension of the state feedback approach from [2] and [16]. Instead of using observers to cope with partially observable models, we formulate sufficient conditions for the control to enforce the constraints and then express it into a realizable output feedback control law (i.e., expressed by a causal function). In comparison with previous work, we only need the internal subgraph of our TEG (i.e., the subgraph obtained by deleting input and output transitions together with the arcs connecting them to other transitions) to be strongly connected. However, we will justify in Sect. 2.3 that this is not a strong restriction: an open-loop event graph can be made strongly connected without modifying its original cycle time. The advantage of our approach is that it does not rely on observers to perform output feedback, which straighten our guarantees in terms of controllability, time and robustness performances, while handling partially observable models. Plus it does not need full controllability over the system to control it, which is an improvement from [24] and [8]. We use a simple traffic light example to illustrate our approach and show that output feedback control can be achieved more efficiently than in previous works.

We introduce useful background on Max-Plus and TEG in Section 2. Section 3 starts with a summary of our modeling hypothesis and control problem and then details our control approach and the derivation of our output feedback control theorem. Finally, we present an illustrative example in Section 4, including discussions on control performances and comparisons with previous results.

# 2 Preliminaries

## 2.1 Max-Plus Algebra

A monoid is a set, say $\mathcal{D}$, endowed with an internal law, noted $\oplus$, which is associative and has a neutral element, denoted $\varepsilon$. A semiring is a commutative monoid endowed with a second internal law, denoted $\otimes$, which is associative, distributive with respect to the first law

$\oplus$, has a neutral element, denoted $e$, and admits $\varepsilon$ as absorbing element (i.e., $\forall a \in \mathcal{D}, a \otimes \varepsilon = \varepsilon \otimes a = \varepsilon$). A dioid is a semiring with an idempotent internal law (i.e., $\forall a \in \mathcal{D}, a \oplus a = a$). The dioid is said to be commutative if the second law $\otimes$ is commutative. Max-Plus algebra is defined as $(\mathbb{R} \cup \{-\infty\}, \max, +)$. This semiring, denoted $\mathbb{R}_{\max}$, is a commutative dioid, the law $\oplus$ is the operator max with neutral element $\varepsilon = -\infty$, and the second law $\otimes$ is the usual addition, with neutral element $e = 0$. $\otimes$ is abbreviated by $\cdot$ (dot). $(+, \times)$ refer to the usual addition and multiplication.

Given matrices of appropriate dimensions, $\oplus$ and $\otimes$ operations are defined as follow:

$$ 
\begin{aligned}
(A \oplus B)(i, j) &= \max(A(i, j), B(i, j)) \\
(A \cdot B)(i, j) &= \bigoplus_{k=1}^{n} (A(i, k) \cdot B(k, j)) \\
&= \max_{k \in [1..n]} (A(i, k) + B(k, j))
\end{aligned}
$$

The unit matrix $I$ has diagonal entries equal to $e$ and $\varepsilon$ elsewhere. $M^p$ is the $p^{th}$ power of matrix $M$ in $\mathbb{R}_{\max}$ (e.g., $M^2 = M \cdot M$) and $M^0 = I$. The Kleene star of a square matrix $M$ is denoted by $M^*$ and defined as $M^* = \bigoplus_{i \in \mathbb{N}} M^i$. Refer to [4] for details.

**Definition 1 (Similar vectors)** Two vectors $u$ and $v$ are similar in $\mathbb{R}_{\max}$ if they share the same zero-elements regarding to the law $\otimes$. If they are of size $n$ then

$$ \forall r \in [1..n], (u(r) = \varepsilon \Leftrightarrow v(r) = \varepsilon) $$

**Proposition 2** Similarity is distributive over the law $\otimes$. Given three vectors $u, v, w \in \mathbb{R}_{\max}$,

$$ (u, v) \text{ similar} \Rightarrow (u \cdot w, v \cdot w) \text{ similar} $$

### Proof

$$ 
\begin{aligned}
u \cdot w = \varepsilon &\Leftrightarrow \bigoplus_{r=1}^{n} u(r) \cdot w(r) = \varepsilon \\
&\Leftrightarrow [\forall r \in [1..n], u(r) \neq \varepsilon \Rightarrow w(r) = \varepsilon]
\end{aligned}
$$

Since $(u, v)$ are similar,

$$ 
\begin{aligned}
&\Leftrightarrow [\forall r \in [1..n], v(r) \neq \varepsilon \Rightarrow w(r) = \varepsilon] \\
&\Leftrightarrow v \cdot w = \varepsilon
\end{aligned}
\quad \square
$$

## 2.2 TEG and Linear Max-Plus Models

An event graph is an ordinary Petri net where each place has exactly one upstream and one downstream transition. A timed event graph (TEG) is an event graph with delays associated to places (holding times) or transitions (firing times). Transitions without downstream places are outputs, those without upstream
places are **inputs**. Others are simply called **internal transitions**. We distinguish inputs that are controllable, the **controls**, from those which are not, the **disturbances**. Disturbances will not be explicitly modeled but can be implemented in simulations (see Sect. 4).

We further introduce the following notations and definitions

* $p_{ij}$ denotes the place linking $t_j$ to $t_i$ when it exists,

* A **path** is an oriented alternating sequence of transitions and places successively connected by an arc,

* The **token number** of a path is the sum of tokens in all places along the path,

* The **delay** of a path is the sum of holding and firing time of all places and transitions along the path,

* Given two transitions $t_i$ and $t_j$ and a token number $m_{ij}$, several $m_{ij}$-token paths connecting $t_j$ to $t_i$ can exist in general.

$t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ denotes the maximal of such paths (i.e., the $m_{ij}$-token path with maximum delay $\tau_{ij}$),

* A **primal path** contains exactly one token in the first place along the path,

* An **empty path** contains no token,

* A **circuit** around $t_i$ is a path connecting $t_i$ to itself,

* An **elementary path** does not contain any place or transition more than once,

* An **event** is the firing of a transition,

* A transition $t_j$ is **controllable** if it is linked directly from a control (i.e., a place $p_{jus}$ exists),

* A transition $t_i$ is **observable** if it is linked directly to an output, (i.e., a place $p_{yri}$ exists).

A Petri net is said to be **live** for an initial marking if all transitions can always be enabled by a future marking [4]. An autonomous event graph contains only internal transitions. A nonautonomous event graph is said to be live if its internal subgraph (or autonomous subgraph, that is pruned of input/output transitions) is live.

**Theorem 3 (from [4])** An autonomous event graph is live if and only if every circuit contains at least one token with respect to the initial marking.

**Definition 4 (Realizable output feedback)** An output feedback expression is said to be realizable if it depends linearly on controls and outputs events associated to non-negative delays. In other words, C is realizable if

$$C = \bigoplus_{m,r,t} (\delta_{m,r} \cdot y_r(k-m) \oplus \mu_{m,s} \cdot u_s(k-m))$$

where $\{\delta_{m,r}, \mu_{m,s}\}_{m,r,s} = \varepsilon$ or $\ge e$.

The dynamics of a TEG are described by the following Max-Plus equation

$$x(k) = \bigoplus_{m} (A_{m} \cdot x(k-m) \oplus B_{m} \cdot u(k-m)) \quad (1)$$

<figure><img src="image_1.png" /><figcaption>Figure 1. Graph interpretation of A and B matrices</figcaption></figure>

$$\text{where } A_m(i,j) = \begin{cases} \tau & \text{if } p_{ij} \text{ exists, contains } m \text{ tokens and has holding time } \tau \\ \varepsilon & \text{otherwise.} \end{cases}$$

and $B_m$ is defined likewise for places between controls and internal transitions.

It is shown that for a live TEG, after eventually extended the state vector, (1) can be rewritten under the following explicit form,

$$x(k) = A \cdot x(k-1) \oplus B \cdot u(k) \quad (2)$$

where $A = A_0^* \cdot A_1$ and $B = A_0^* \cdot B_0$. See [4] for details.

Finally, for any integer $\phi$ such that $1 \le \phi \le k$, by doing $\phi$ substitutions in (2), we obtain

$$x(k) = A^{\phi} \cdot x(k-\phi) \oplus \left[ \bigoplus_{k'=0}^{\phi-1} A^{k'} \cdot B \cdot u(k-k') \right] \quad (3)$$

**Remark 5** Graphical interpretations of A and B are illustrated in Fig. 1. Matrices' coefficients represent the maximal delay along paths that depend on the matrix. For instance, $A(i,j) = (A_0^* \cdot A_1)(i,j)$, thus $A(i,j)$ is the maximal delay of paths connecting $t_j$ to $t_i$, primal (because of $A_1$) and then going through an arbitrary number of empty places (because of $A_0^*$). It equals $\varepsilon$ if no such path exists. $A^k$ contains delays of "longer" paths (i.e., with more tokens) as $k$ increases. Hence, $A^k$ will tend to "grow" with $k$. Note that these paths are not elementary (i.e., they can pass through the same transition several times).

**Definition 6 (Cycle time [4])** The cycle time $\lambda$ of a live TEG is the maximum of its cycle means over all circuits in the graph. If $S$ is the set of transitions included in a circuit then $\lambda$ computes

$$\lambda = \bigoplus_{j, t_j \in S} \frac{\tau_{jj}}{m_{jj}} \quad (4)$$
For the systems we control, we usually want to maximize the throughput (the inverse of the cycle time). Hence, a controller should delay the original system as few as possible while ensuring the constraints are meet.

**Definition 7 (Optimal control)** A control policy is said to be optimal if the controlled system respects all constraints and have the same cycle time as the autonomous system.

## 2.3 Model of cyclic processes

Many real life applications follow cyclic sequences of actions (e.g., a manufacturing assembly line). When we model these systems by means of a graph, the resulting graph is said to be strongly connected.

**Definition 8 (Strongly connected graph)** A graph is said to be strongly connected if for any pair of nodes i and j, there exists an oriented path from j to i.

Hence, a timed event graph is strongly connected if for any pair of internal transitions $(t_i, t_j)$, there exists $m_{ij} \in \mathbb{N}$ such that a path $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ exists, which yields $x_i(k) \ge \tau_{ij} \cdot x_i(k - m_{ij})$.

We mentioned in the introduction that a TEG could be made cyclic without modifying its original cycle time. The proof is similar to that of Th.6.55 from [4]. Assume we need to connect $t_i$ to $t_j$ in order to make a TEG strongly connected. To do so, one adds a new place $p_{ji}$ with $m_{ji}$-tokens and $\tau_{ji}$-delay (with $t_i$ observable and $t_j$ controllable). Hence, as it already exists a path $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$, we are creating a new circuit of $m_{ij} + m_{ji}$ tokens with $\tau_{ij} + \tau_{ji}$ delay, so having a cycle mean of $\lambda_{new} = \frac{\tau_{ij} + \tau_{ji}}{m_{ij} + m_{ji}}$ (see (4)). Therefore, we can choose $\tau_{ji} = 0$ and $m_{ji}$ as big as necessary for $\lambda_{new}$ to be smaller than the previous critical cycle means from the original graph. Hence, we cycle time is not modified. We illustrate this in Sect.4.

## 2.4 Temporal constraints

In a TEG, the holding time represents the minimal time a token has to sojourn in a place. If one wants to account for a maximal duration, a specific constraint has to be added. An approach to solve this modeling problem is presented in [2]. The sojourn time of tokens in place $p_{ij}$ is minimized by the holding time $\tau_{ij}$ and must not exceed a maximal delay, denoted $\tau_{ij}^{max}$. Hence, a time interval $[\tau_{ij}, \tau_{ij}^{max}]$ can be associated with the place $p_{ij}$ subject to a strict time constraint. This additional temporal constraint is expressed by the following Max-Plus inequality

$$x_i(k) \le \tau_{ij}^{max} \cdot x_j(k - m_{ij}) \quad (5)$$

It is illustrated in the example from Sect.4 (see Fig.2).

# 3 Output feedback control

## 3.1 Modeling hypothesis and control problem definition

In the remaining of this paper, we consider a single input single output (SISO) TEG containing $N$ internal transitions, live, without circuit of null delay, and such that its internal subgraph is strongly connected. The output is set as $y = x_j$ for a given $j \in [1..N]$ and the dynamics of the TEG are described by

$$(2) : x(k) = A \cdot x(k-1) \oplus B \cdot u(k)$$
It yields $A, B$ belong to $\mathbb{R}_{\max}^{N \times N}$ and $\mathbb{R}_{\max}^{N \times 1}$ respectively.

We are interested in modeling manufacturing systems. Holding time represents length of processes and thus are non-negative. We set firing times equal to 0 and we consider the earliest firing rule (i.e., transitions fire as soon as possible). Firing epochs with negative index are set to $\varepsilon$ ($\forall k < 0$, $x(k) = \varepsilon$). We further assume there is no token in the places under time constraint ($m_{ij} = 0$) and we will see in Sect.3.2 that we need an empty path from the control to the place under constraint ($B(j) \neq \varepsilon$) to ensure controllability. These modeling assumptions are not restrictive in general. For instance, in a production plant, it simply means that at initial state, there is no product in process. We control the system before than the production starts.

We consider that the firing sequence of the control $u(k)$ can be arbitrary defined. Our control problem consists in deriving a realizable output feedback for $u$ enforcing time constraints the type of (5) while preserving time and robustness performances.

A previous work already presented output feedback control derivation in similar settings [8] but without taking care of time performances of the controlled system, which resulted in poor time performances. To avoid the same pitfall, we start by giving tight sufficient conditions for the control, presented in Sect.3.2. However, these conditions are non realizable and thus non suitable to solve our control problem. In addition, we show in Sect.3.3 that a realizable upper-bound can always be derived for any expression. Hence, combining these two results, we obtain our control theorem, presented in Sect.3.4. This approach results in better time performances and equivalent robustness properties. This will be illustrated and discussed in Sect.4.

## 3.2 Sufficient conditions for constraints enforcement

Prop.9 provides tight sufficient conditions for the satisfaction of a constraint of type (5) where $m_{ij} = 0$ (see Sect.3.1 for motivations).
**Proposition 9** If there exists an empty path $t_u \xrightarrow{0,B(j)} t_j$, then ensuring

$$u(k) \geq C = (-B(j)) \cdot (-\tau_{ij}^{\max}) \cdot x_i(k) \quad (6)$$

is a sufficient condition for the control to enforce the constraint $x_i(k) \leq \tau_{ij}^{\max} \cdot x_j(k)$ for any $k > 0$.

**Proof** The time constraint to satisfy is expressed by $x_i(k) \leq \tau_{ij}^{\max} \cdot x_j(k)$ ((5) with $m_{ij} = 0$).

We can observe from Rem.5 that existence of an empty path $t_u \xrightarrow{0,B(j)} t_j$ is equivalent to $B(j) \neq \varepsilon$. Therefore, $C$ is well-defined in $\mathbb{R}_{\max}$ (otherwise $(-B(j))$ equals $+\infty$, which does not belong to $\mathbb{R}_{\max}$).

The state equation (2) applied to state $j$ gives $\forall k > 0$, $x_j(k) = A(j, :), x(k-1) \oplus B(j) \cdot u(k)$

$$\Rightarrow \quad x_j(k) \geq B(j) \cdot u(k)$$

Hence, if $u(k) \geq C$, one deduces

$$\Rightarrow \quad x_j(k) \geq B(j) \cdot (-B(j)) \cdot (-\tau_{ij}^{\max}) \cdot x_i(k)$$

$$\Rightarrow \quad x_j(k) \geq (-\tau_{ij}^{\max}) \cdot x_i(k)$$

$$\Rightarrow \quad x_i(k) \leq \tau_{ij}^{\max} \cdot x_j(k)$$

which concludes the proof. □

### 3.3 Derivation of realizable upper-bounds

This section presents Lemma 13 which is the core result of this paper. It demonstrates that under assumptions of Sect.3.1 we can always derive a realizable upper-bound for any expression using solely the control input and one other transition. Prop.10, 11 and 12 are useful results for the demonstration of the Lemma. All proofs are provided in Appendix A.

**Proposition 10** For any $(i, j) \in [1..N]^2$ such that there exists a path $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$,

$$\forall p \in \mathbb{N}^*, A^{p+m_{ij}}(i, :) \geq \tau_{ij} \cdot A^p(j, :$$

**Proposition 11** For any $(i, j) \in [1..N]^2$ such as there exist a path $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ and a circuit $t_i \xrightarrow{m_{ii}, \tau_{ii}} t_i$, and for any $\nu \in \mathbb{R}$, there exists $q_0 \in \mathbb{N}$,

$$\forall q \geq q_0, \forall p \in \mathbb{N}^*, \nu \cdot A^{p+m_{ij}+q \times m_{ii}}(i, :) \geq A^p(j, :$$

**Proposition 12** For any $(i, j) \in [1..N]^2$ such as there exist paths $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ and $t_i \xrightarrow{m_{ji}, \tau_{ji}} t_j$, there exists $p_0 \in \mathbb{N}^*$ such that,

12.1: $\forall p \geq p_0, \forall q \in \mathbb{N}$, $(A^{p+q \times m_{ii}}(i, :), A^p(i, :))$ similar,

12.2: $\forall p \geq p_0 + m_{ji}$, $(A^{p+m_{ij}}(i, :), A^p(j, :))$ similar,

12.3: $\forall p \geq p_0 + m_{ji}, \forall q \in \mathbb{N}$, $(A^{p+q \times m_{ii}+m_{ij}}(i, :), A^p(j, :))$ similar, where $m_{ii} = m_{ij} + m_{ji}$.

**Lemma 13** For any $(i, j) \in [1..N]^2$ such as there exist paths $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ and $t_i \xrightarrow{m_{ji}, \tau_{ji}} t_j$, and for any $\nu \in \mathbb{R}$, $\exists p \in \mathbb{N}^*, q \in \mathbb{N}$, $\delta \in \mathbb{R}^+$, $\forall k \geq (p+q)$,

$$\nu \cdot x_i(k) \leq \delta \cdot x_j(k-q) \oplus \left[ \bigoplus_{k'=0}^{p+q-1} (\mu_{k'} \cdot u(k-k')) \right]$$

where $\mu_{k'} = \nu \cdot (A^{k'} \cdot B)(i)$.

Hence, given any delay $\nu$ (even negative) and state $x_i$, we can always derive a realizable upper-bound depending solely on past control events $u(k)$ and past firings of one other transition events $x_j(k)$ associated with non-negative delay $\delta$. In the following section, we combine this result and the sufficient condition from Prop.9 to obtain our control theorem.

### 3.4 Output feedback control theorem

For a general TEG under assumptions of Sect.3.1, we now present our theorem for deriving a realizable output feedback control law enforcing any set of time constraints.

**Theorem 14** Any constraint of from (5) such that there exists an empty path $t_u \xrightarrow{0,B(j)} t_j$ and $B(i) \leq B(j) \cdot \tau_{ij}^{\max}$ can be enforced for any $k \geq (p+q)$ by setting $u(k)$ as

$$u(k) \geq \delta \cdot y(k-q) \oplus \left[ \bigoplus_{k'=1}^{p+q-1} (\mu_{k'}^{+} \cdot u(k-k')) \right] \quad (7)$$

which defines a realizable output feedback control where $p, q, \delta$ and $(\mu_{k'}^+)$ are returned by Algorithm 1 and $m_{yu}$ is the smallest token number of paths $t_u \rightarrow t_y$.

**Proof** The time constraint to satisfy is expressed by $x_i(k) \leq \tau_{ij}^{\max} \cdot x_j(k)$ ((5) with $m_{ij} = 0$).

Existence of an empty path $t_u \xrightarrow{0,B(j)} t_j$ is equivalent to $B(j) \neq \varepsilon$ (refer to Rem.5). According to Prop.9, it is sufficient to set $u(k) \geq C = (-B(j)) \cdot (-\tau_{ij}^{\max}) \cdot x_i(k)$ in order to satisfy the constraint.

Moreover, $u(k)$ must respect the state equations, hence $x_i(k) = A \cdot x(k) \oplus B(i) \cdot u(k)$

$$\Rightarrow \quad x_i(k) \geq (B(i) \cdot (-B(j) \cdot (-\tau_{ij}^{\max})) \cdot x_i(k)$$

$$\Rightarrow \quad (B(i) \cdot (-B(j) \cdot (-\tau_{ij}^{\max})) \leq 0$$

$$\Rightarrow \quad B(i) \leq B(j) \cdot \tau_{ij}^{\max}$$

Consider a "worst-case scenario" where only one transition is observable, say $x_l$ (i.e., $y(k) = x_l(k)$), the system has a single output). Assuming the internal subgraph of our TEG is strongly connected, we can apply Lemma 13 to expression $C$ (existence of paths $t_l \xrightarrow{m_{il}, \tau_{il}} t_i$ and
$t_i \xrightarrow{m_{li}, \tau_{li}} t_l$ is assured by strong connectiveness),

$\exists p \in \mathbb{N}^*, q \in \mathbb{N}, \delta \in \mathbb{R}^+, \forall k \geq (p+q),$

$$
\begin{align*}
C &= (-B(j)) \cdot (-\tau_{ij}^{max}) \cdot x_i(k) \\
  &\leq C' = \delta \cdot x_l(k-q) \oplus \left[ \bigoplus_{k'=0}^{p+q-1} (\mu_{k'} \cdot u(k-k')) \right]
\end{align*}
$$

$$
\text{where } \mu_{k'} = (-B(j)) \cdot (-\tau_{ij}^{\text{max}}) \cdot (A^{k'} \cdot B)(i)
$$

Furthermore, $B(i) \leq \tau_{ij}^{max} \cdot B(j)$ implies $\mu_0 = \varepsilon$, and we
have set $y(k) = x_l(k)$, therefore $C'$ rewrites

$$
C' = \delta \cdot y(k-q) \oplus \left[ \bigoplus_{k'=1}^{p+q-1} (\mu_{k'} \cdot u(k-k')) \right]
$$

Let set $\mu_{k'}^{+} = \begin{cases} \mu_{k'} & \text{if } \mu_{k'} > 0, \\ \varepsilon & \text{otherwise.} \end{cases}$ Thus $\mu_{k'}^{+} \geq \mu_{k'}$.

Sequence of firing epochs are non-decreasing, so for any $\mu \le 0$, $u(k) \ge \mu \cdot u(k-k')$ by definition. So if one defines $C'^+$ as $C'$ with $\mu_{k'}^+$ replacing $\mu_{k'}$, it is equivalent for $u(k)$ to be bigger than $C'^+$ or $C'$. Moreover, $C'^+$ is a realizable output feedback expression and

$$
u(k) \geq C'^{+} \Leftrightarrow u(k) \geq C'
$$

$\Rightarrow u(k) \geq C$ which is sufficient to prove that $u(k)$ en-
forces the constraint according to Prop.9. $\square$

**Remark 15** *Implementing this control creates new cycles in the controlled graph. In particular, we add a path* $t_y \xrightarrow{q, \delta} t_u$. *Hence if we call $m_{yu}$ the smallest token number of paths $t_u \to t_y$ then according to Thm.3 we need to satisfy: $m_{yu} + q \ge 1$ (or $q \ge 1 - m_{yu}$) for the controlled system to remain live. This is implemented in the initialization of $q$ (see line 5 in Alg.1).*

**Remark 16** In feedback control of Max-Plus models, conditions for the control are expressed as $u(k) \ge C$ where $C$ is a given expression (e.g., $F \cdot x(k-1)$ in usual state feedback, or given by Prop.9 in our case). If we use the observer from [11] on $C$, we obtain $\hat{C} \le C$. Hence, setting $u(k) \ge \hat{C}$ does not guarantee $u(k) \ge C$ and thus is not a proper solution for our control problem.

3.5 About sufficient conditions, extensions and model-
ing assumptions

We present here sufficient conditions for solving our con-
trol problem. We mentioned in the introduction (and il-
lustrate in Sect.4) that a model can be made strongly
connected altering its cycle time. Thus strong connec-
tiveness is not a strong limitation. The two other condi-
tions ($B(i) \le B(j) \cdot \tau_{ij}^{max}$ and empty path from $u$ to $t_j$)
are not necessary in general (counter-examples can be
found), but there are for our approach. In other words, if
we set $u(k) \ge C$ according to Prop.9 to enforce the con-
straint, no realizable control satisfying the state equa-
tion can be found if these conditions do not hold. How-
ever, these conditions depend on the system architecture
(strong connectiveness and $B(i) \le B(j) \cdot \tau_{ij}^{max}$) or on

initial conditions (empty path from $u$ to $t_j$), which are all
easy-to-check a priori on the uncontrolled model. This
is a real improvement from a design perspective com-
pared to previous work [8, 11, 24], in which conditions
have no such clear and simple interpretation on the sys-
tem model.

Our control approach easily handles multiple constraints
in the same fashion as in [2] and [16]. For each constraint,
one derives a suitable control $u_s(k)$. All constraints will
be enforced by $u(k) = \bigoplus u_s(k)$. This is further discussed
in Sect.4. These results can also be extended to models
with tokens in the constrained places like in [16].

Finally, one should note that the SISO assumption is
not a limitation. As previously mentioned in [16], we
have sufficient conditions relating one control transition
to one constraint ($B(i) \le B(j) \cdot \tau_{ij}^{max}$). In other words,
if one control cannot enforce a constraint by itself, no
combination of controls will do. Multiple controls can
however be useful to control multiple constraints if one
control does not satisfy sufficient conditions for all con-
straints simultaneously. Our approach is perfectly suit-
able to this setting. From this prospect, our approach
is more general than [24] and [8] which assume full con-
trollability over the system. Besides, a single output is a
"worst-case scenario" for a feedback controller. We have
information on one of the system state only.

3.6 Algorithmic procedure

Algorithm 1 computes the coefficients for the control defined by Th.14. It takes as input the system dynamics (matrices *A* and *B*), the definition of the system output (*y*), the upstream and downstream transitions of the constrained place (*i* and *j*), the constraint value ($\tau_{ij}^{max}$), and the smallest token number of paths $t_u \rightarrow t_y$ ($m_{yu}$). It returns all necessary coefficients to define a realizable output feedback control ($p, q, \delta$ and ($\mu_k^+$)) given that sufficient conditions are satisfied. Th.14 guarantees that the procedure terminates.

4 Illustrative example – Traffic lights

4.1 Model and control derivation

We illustrate our approach using a simple example
from the literature [7, 8, 24]. It describes a road sec-
tion with two traffic lights which is illustrated on Fig.2
(white area). Transitions {$x_i$}$_{i \in \{1,2\}}$ indicate events of
the semaphore *i* turning on green light and {$x_i$}$_{i \in \{3,4\}}$
events of turning on red light. Minimal timing of each
phase is indicated by the place. We assume that we
can increase the red time of the first light in order to
respect our specifications and that the only observable
event for the controller is the second light turning green.
Therefore, we have one input transition $t_u$ connected to
**Algorithm 1** deriveControlCoef

Require: A, B, y, i, j, $\tau_{ij}^{max}$, $m_{yu}$

procedure CONTROLDEFINITION

$$ \nu \leftarrow (-B(j)) \cdot (-\tau_{ij}^{max}) $$

$$ p \leftarrow 1 $$

5: $q \leftarrow \max(0, 1 - m_{yu})$
while majoration(A, i, y, v, p, q) is False do
  $q \leftarrow q + 1$

end while

while similarity(A, i, y, p, q) is False do

10: $p \leftarrow p + 1$

end while

$$ \delta \leftarrow \max_{r \in [1..N]} (\nu \cdot A^{p+q}(i, r) - A^p(y, r)) \\ A^p(y,r) \neq \delta $$

for $k' \in [1..p+q-1]$ do

$$ \mu_{k'} \leftarrow (A^{k'} \cdot B)(i) - B(j) - \tau_{ij}^{max} $$

15: $\mu_{k'}^{+} \leftarrow \max(\mu_{k'}, 0)$

end for

return $(p, q, \delta, (\mu_{k'}^{+}))$

end procedure

20: function MAJORIZATION(A, i, y, v, p, q)
  if $v \cdot A^{p+q}(i, :) \ge A^p(y, :)$ then return True
  else return False
end if

end if

end function

end function

25: function SIMILARITY(A, i, y, p, q)
  if $(A^{p+q}(i, :) , A^p(y, :))$ similar then return True
  else return False
end if

end if

end function

end function

$t_1$ and one output transition $t_y$ connected from $t_2$. For traffic regulation purposes, it is relevant to cap the time laps between the two lights turning green (C1) and the time duration of green lights (C2 and C3). Hence, we have 3 constraints of type (5), each of 15 time units, added on places $p_{21}$, $p_{31}$, and $p_{42}$. However, it is clear here that C2 and C3 will always be satisfied (without external disturbances). Indeed, there is nothing keeping $t_3$ or $t_4$ to fire once a token has completed its sojourn time in the upstream place. Hence we will focus on C1.

The internal subgraph of this model is not strongly connected, hence results from Sect.3 cannot be applied directly. However, as discussed in Sect.2.3, we can turn our model into strongly connected form without modifying the original cycle time. There are two circuits in the original model (one for each light) with respective cycle means $\lambda_1 = 9$ and $\lambda_2 = 12$ (use relation (4)). One can make this model strongly connected by linking $t_2$ to $t_1$ through a place $p_{12}$, with delay $\tau_{12}$ and $m_{12}$ tokens, which creates a new circuit of cycle mean $\lambda_{new} = \frac{\tau_{21} \cdot \tau_{12}}{m_{21} \cdot m_{12}} = \frac{10 \cdot \tau_{12}}{0 \cdot m_{12}}$. Hence, it suffices to set $\tau_{12} = 0$ and $m_{21} = 1$ to get $\lambda_{new} = 10 \le \max(\lambda_1, \lambda_2)$. The resulting addition to the nominal model is shown in

<figure><img src="image_2.png" /><figcaption>Figure 2. Model of the traffic lights – On the nominal model (white area) we show in grey the TEC section added to obtain a strongly connected graph; our output feedback controller is represented within the grey area.</figcaption></figure>

grey on Fig.2, in the white area. The system dynamics are then expressed by $x(k) = A \cdot x(k-1) \oplus B \cdot u(k)$ and $y(k) = x_2(k)$

$$ \text{where } A = \begin{pmatrix} \cdot & 0 & 5 & \cdot \\ \cdot & 10 & 15 & 7 \\ \cdot & 4 & 9 & \cdot \\ \cdot & 15 & 20 & 12 \end{pmatrix} \quad \text{and} \quad B = \begin{pmatrix} 0 \\ 10 \\ 4 \\ 15 \end{pmatrix} $$

with $\epsilon$ is replaced by a . for the sake of readability. More detailed examples of system dynamics derivations can be found in [4], [2] or [16].

Conditions of Th.14 are satisfied for constraint C1 (i.e., $B(1) = 0 \neq \epsilon$ and $B(2) = 10 \le 15 = B(1) \cdot \tau_{21}^{max}$). Hence, we can derive a realizable output feedback control using Alg.1, which returns

$$ u(k) \ge 9 \cdot y(k-2) \oplus 7 \cdot u(k-1) \oplus 19 \cdot u(k-2) $$

This feedback control is shown in the grey area on Fig.2.

**Remark 17** Th.14 can also be applied to C2 and C3. It results in strictly less restrictive conditions for the control law. This is not surprising as we already mentioned these constraints are nominally satisfied. If it were not the case, it would suffice to take the sum of the control obtained for each constraint, as explained at the end of Sect.3.4.

## 4.2 Discussions on control optimality and performance

The cycle time of the autonomous model is $\lambda = \max(\lambda_1, \lambda_2) = 12$ time units. Using relation (4), one quickly sees that our feedback control creates new circuits with cycle mean of $(10 \cdot 9)/2, 7/1$ and $19/2$ respectively. Therefore, our control does not increase the system cycle time. According to Th.14 and Def.7, this is an optimal control for this problem.

**Remark 18** Note that it is not always the case. The cycle time of the controlled system might increase depending on the system architecture, the constraints values, and the output definition. Moreover, our output feedback controller eventually delays the system more than a state feedback controller would. This is not surprising, as we have some extra restrictions on the information available.
<figure><img src="image_3.png" /><figcaption>Figure 3. Quantified violation of the C1 constraint for the different state (SFC) and output feedback controllers (OFC)</figcaption></figure>

Performing feedback control is usually interesting because of its robustness against disturbances. However, doing output feedback (instead of state feedback) weaken the robustness of the controlled system, so does preserving the cycle time. This is illustrated on Fig.3. We implemented two arbitrary disturbances on the controlled system from different approaches with initial conditions $x(0) = [0, 0, 0, 0]^T$:

* $k = 9$ Delay of 12 and 20 time units on $x_2$ and $x_4$,

* $k = 14$ Delay of 8 and 30 time units on $x_1$ and $x_2$.

We plot the error $e(k)$ which is the difference between the actual firing epochs of $t_2$ and the upper-bound of constraint C1 (i.e., $e(k) = \max(x_2(k)) - (x_1(k) + 15), 0$). In other words, it is a quantification of the violation of C1. The legend indicates the cycle time of the controlled system for each approach.

State feedback from [2] is of form $u(k) = F \cdot x(k-1)$ and guarantees to reject any disturbance in one step but increases the cycle time. To preserve $\lambda_{new} = 12$, [24] implements a feedback $u(k) = F \cdot x(k-2)$, but it can then take up to two steps to reject a disturbance, as we can see on that example. The output feedback approach from [8] does not give explicit guarantees on robustness nor on the cycle time preservation and loses on both aspects here. Finally, Th.14 guarantees that our output feedback control rejects any disturbance in $(p+q)$ time steps at most (here Alg.1 returns $(p+q) = 3$), although it might be faster (2 and 1 time steps for the first and second disturbance respectively). It also manages to preserve the cycle time, even though that might be always the case (see Rem.18) and does not require full controllability over the system (only $t_1$ needs to be controlled).

## 5 Conclusions

This paper presents an output feedback control approach handling temporal constraints on partially observable TEG. We propose an efficient control approach showing good time and robustness performances, under conditions that are comparably restrictive to previous works but are much more explicit and can be checked easily on

the system model. However, our control is not minimally restrictive. That is, the control law returned by Alg.1 might increase the system cycle time while it is sometimes possible to derive another output feedback control that does not. A systematic approach for the derivation of such minimally restrictive control would be a relevant perspective. It is also believed that robustness guarantees from Th.14 can be tightened to disturbance rejection in at most $(q)$ steps.

## References

[1] Boussad Addad, Saïd Amari, and Jean-Jacques Lesage. Analytic calculus of response time in networked automation systems. *Automation Science and Engineering, IEEE Transactions on*, 7(4):858–869, 2010.

[2] Saïd Amari, Isabel Demongodin, Jean Jacques Loiseau, and Claude Martinez. Max-plus control design for temporal constraints meeting in timed event graphs. *Automatic Control, IEEE Transactions on*, 57(2):462–467, 2012.

[3] Abdourrahmane M Atto, Claude Martinez, and Said Amari. Control of discrete event systems with respect to strict duration: Supervision of an industrial manufacturing plant. *Computers & Industrial Engineering*, 61(4):1149–1159, 2011.

[4] François Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. *Synchronization and linearity: an algebra for discrete event systems*. John Wiley & Sons Ltd, 1992.

[5] Patrice Bonhomme. Scheduling and control of real-time systems based on a token player approach. *Discrete Event Dynamic Systems*, 23(2):197–209, 2013.

[6] Raymond A Cuninghame-Green. Process synchronisation in a steelworks—a problem of feasibility. In *Proceedings of the 2nd international conference on operational research*, pages 323–328. English University Press, 1960.

[7] T Garcia, JEE Cury, W Kraus, and I Demongodin. Traffic light coordination of urban corridors using max-plus algebra. *Buenos Aires–Argentina*, pages 103–108, 2007.

[8] Vinicius Mariano Gonçalves, Carlos Andrey Maia, Laurent Hardouin, and Ying Shang. An observer for tropical linear event-invariant dynamical systems. In *Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on*, pages 5967–5972. IEEE, 2014.

[9] Laurent Hardouin, Olivier Boutin, Bertrand Cottenceau, Thomas Brunsch, and Jörg Raisch. Discrete-event systems in a dioid framework: Control theory. In *Control of Discrete-Event Systems*, pages 451–469. Springer, 2013.

[10] Laurent Hardouin, CA Maia, Bertrand Cottenceau, and R Santos-Mendes. Max-plus linear observer: application to manufacturing systems. In *10th International Workshop on Discrete Event Systems, WODES*, volume 10, 2010.

[11] Laurent Hardouin, Carlos-Andrei Maia, Bertrand Cottenceau, and Mehdi Lhommeau. Observer design for (max,+)-linear systems. *IEEE Transactions on Automatic Control*, 55(2):538–543, 2010.

[12] Laurent Houssin, Sébastien Lahaye, and Jean-Louis Boimond. Just in time control of constrained (max,+)-linear systems. *Discrete Event Dynamic Systems*, 17(2):159–178, 2007.

[13] Laurent Houssin, Sébastien Lahaye, and Jean-Louis Boimond. Control of (max,+)-linear systems minimizing delays. *Discrete Event Dynamic Systems*, 23(3):261–276, 2013.
This implies $\eta_{q+1}^i \le \eta_q^i$, hence $(\eta_q^i)_{q \in \mathbb{N}}$ is decreasing. Moreover, $(\eta_q^i)_{q \in \mathbb{N}}$ is obviously minimized by 0, so $(\eta_q^i)_{q \in \mathbb{N}}$ converges. Since it takes discrete values, the sequence reaches its limit at a given step $l \ge 0$. Thus $\exists l \in \mathbb{N}, \forall q \in \mathbb{N}, \eta_{l+q}^i = \eta_i^q$

Combined with (A.2), this yields

$$ [A^{(l+q) \times m_{ii}}(i,r) = \varepsilon \Leftrightarrow A^{l \times m_{ii}}(i,r) = \varepsilon] \\ \text{Finally, one can define } p_0 \leftarrow l \times m_{ii}, \text{ and rewrites} \\ \exists p_0 \in \mathbb{N}^*, \forall q \in \mathbb{N}, \\ [A^{p_0+q \times m_{ii}}(i,:)=\varepsilon \Leftrightarrow A^{p_0}(i,:)=\varepsilon] \quad (A.3) $$

Finally, taking Prop.2 into account, (A.3) holds true for any $p \ge p_0$, which concludes the proof of 12.1. $\square$

Similarly, applying Prop.10 to $t_i \xrightarrow{m_{ij}, \tau_{ij}} t_j$ and $t_j \xrightarrow{m_{ji}, \tau_{ji}} t_i$, one obtains

$$ \forall p \in \mathbb{N}^*, \left\{ \begin{array}{l} A^{p+m_{ij}}(i, :) \ge A^p(j, :) \\ A^{p+m_{ji}}(j, :) \ge A^p(i, :) \end{array} \right. \\ \Rightarrow \quad \forall p \in \mathbb{N}^*, A^{p+m_{ij}+m_{ji}}(i, :) \ge A^{p+m_{ji}}(j, :) \ge A^p(i, :) \\ \Rightarrow \quad \forall p \in \mathbb{N}^*, A^{p+m_{ii}}(i, :) \ge A^{p+m_{ji}}(j, :) \ge A^p(i, :) \\ \text{One can choose } p \leftarrow p_0 = l \times m_{ii} \text{ and rewrites} \end{array} \right. $$

$$ \begin{array}{l} A^{(l+1) \times m_{ii}}(i, :) \overset{\textcircled{1}}{\ge} A^{l \times m_{ii}+m_{ji}}(j, :) \overset{\textcircled{2}}{\ge} A^{l \times m_{ii}}(i, :) \\ \text{Thus, for any } r \in [1..N], \\ \overset{\textcircled{1}}{\Rightarrow} \left[ \begin{array}{l} A^{(l+1) \times m_{ii}}(i,r) = \varepsilon \Rightarrow A^{l \times m_{ii}+m_{ji}}(j,r) = \varepsilon \end{array} \right. \\ \overset{\textcircled{2}}{\Rightarrow} \left[ \begin{array}{l} A^{l \times m_{ii}+m_{ji}}(j,r) = \varepsilon \Rightarrow A^{l \times m_{ii}}(i,r) = \varepsilon \\ \phantom{A^{l \times m_{ii}+m_{ji}}(j,r) = \varepsilon} \Rightarrow A^{p_0}(i,r) = \varepsilon \\ \phantom{A^{l \times m_{ii}+m_{ji}}(j,r) = \varepsilon} \text{[(A.3) with } q=1 \text{]} \Rightarrow A^{m_{ii}+p_0}(i,r) = \varepsilon \\ \phantom{A^{l \times m_{ii}+m_{ji}}(j,r) = \varepsilon} \text{[}p_0 = l \times m_{ii}\text{]} \Rightarrow A^{(l+1) \times m_{ii}}(i,r) = \varepsilon \end{array} \right] \end{array} $$

One can combine these two implications to get the following equivalence

$$ \begin{array}{l} [A^{(l+1) \times m_{ii}}(i, :) = \varepsilon \Leftrightarrow A^{l \times m_{ii}+m_{ji}}(j, :) = \varepsilon] \\ \Leftrightarrow [A^{p_0+m_{ij}+m_{ji}}(i, :) = \varepsilon \Leftrightarrow A^{p_0+m_{ji}}(j, :) = \varepsilon] \\ \text{One can set } \tilde{p}_0 \leftarrow p_0 + m_{ji} \text{ and rewrites} \\ [A^{\tilde{p}_0+m_{ij}}(i, :) = \varepsilon \Leftrightarrow A^{\tilde{p}_0}(j, :) = \varepsilon] \end{array} \quad (A.4) $$

Taking Prop.2 into account, (A.4) holds true for any $p \ge \tilde{p}_0 = p_0 + m_{ji}$, which concludes the proof of 12.2. $\square$

Finally, 12.1 holds for all $p \ge p_0$, so it holds in particular for all $p \ge \tilde{p}_0$. Therefore, for all $q \in \mathbb{N}$ and $p \ge \tilde{p}_0$, $(A^{p+q \times m_{ii}}(i, :), A^p(i, :))$ similar,

$$ \begin{array}{l} \text{Prop.2} \\ \Rightarrow \quad (A^{p+q \times m_{ii}+m_{ij}}(i, :) , A^{p+m_{ij}}(i, :)) \text{ similar,} \\ \text{Prop.12.2} \\ \Rightarrow \quad (A^{p+q \times m_{ii}+m_{ij}}(i, :) , A^p(j, :)) \text{ similar,} \end{array} $$

which concludes the proof of 12.3. $\square$

**Proof** [Proof of Lemma.13]

If there exists $t_j \xrightarrow{m_{ij}, \tau_{ij}} t_i$ and $t_i \xrightarrow{m_{ji}, \tau_{ji}} t_j$ then there

exists at least one circuit $t_i \xrightarrow{m_{ii}, \tau_{ii}} t_i$ where $m_{ii} = m_{ij} + m_{ji}$. Hence, we can apply both Prop.11 and Prop.12.3 and the following relations hold:

$$ \forall \nu \in \mathbb{R}, \exists (p_0, q_0) \in \mathbb{N}^* \times \mathbb{N}, \quad \nu \cdot A^{p_0+m_{ij}+q_0 \times m_{ii}}(i, :) \ge A^{p_0}(j, :) \quad (A.5) $$

$$ (A^{p_0+m_{ij}+q_0 \times m_{ii}}(i, :) , A^{p_0}(j, :)) \text{ similar} \quad (A.6) $$

From (A.5), the right-hand side is contained in the left-hand side and there are both similar according to (A.6). These two terms are then comparable. The remaining of the proof consists in deriving an upper-bound for the left-hand side using the right-hand side.

Let set $p \leftarrow p_0$ and $q \leftarrow m_{ij} + q_0 \times m_{ii}$ for convenience and define,

$$ \delta \leftarrow \max_{\substack{r \in [1..N] \\ A^p(j,r) \neq \varepsilon}} (\nu \cdot A^{p+q}(i,r) - A^p(j,r)) $$

Note that we need to be careful here in the definition of $\delta$ because $(-\varepsilon) = +\infty$ does not belong to $\mathbb{R}_{\max}$.
From (A.5), we have $\delta \ge 0$ and it follows that

$$ \forall r \in [1..N], A^p(j,r) \neq \varepsilon, \quad \nu \cdot A^{p+q}(i,r) \le \delta \cdot A^p(j,r) $$

Taking (A.6) into account, this holds for any $r \in [1..N]$, hence we deduce,

$$ \nu \cdot A^{p+q}(i, :) \le \delta \cdot A^p(j, :) \quad (A.7) $$

Furthermore, the state equation of form (3) with $\phi = p$ gives, for any $k \ge p$,

$$ x_j(k) = A^p(j, :) \cdot x(k-p) \oplus \left[ \bigoplus_{k'=0}^{p-1} (A^{k'} \cdot B)(j) \cdot u(k-k') \right] $$

By neglecting the terms from the sum and shifting the index $k$ to $k-q$, one deduces the following inequalities

$$ \forall k \ge (p+q), x_j(k-q) \ge A^p(j, :) \cdot x(k-(p+q)) $$

$$ \Leftrightarrow A^p(j, :) \cdot x(k-(p+q)) \le x_j(k-q) $$

$$ \Leftrightarrow \delta \cdot A^p(j, :) \cdot x(k-(p+q)) \le \delta \cdot x_j(k-q) $$

Taking into account (A.7), one deduces

$$ \nu \cdot A^{p+q}(i, :) \cdot x(k-(p+q)) \le \delta \cdot x_j(k-q) \quad (A.8) $$

Finally, using again the state equation of form (3) but with $\phi = p+q$, we obtain that for any $\nu \in \mathbb{R}$ and any $k \ge (p+q)$,

$$ \nu \cdot x_i(k) = \nu \cdot A^{p+q}(i, :) \cdot x(k-(p+q)) $$

$$ \oplus \left[ \bigoplus_{k'=0}^{p+q-1} \nu \cdot (A^{k'} \cdot B)(i) \cdot u(k-k') \right] $$

Using relation (A.8), one obtains

$$ \nu \cdot x_i(k) \le \delta \cdot x_j(k-q) $$

$$ \oplus \left[ \bigoplus_{k'=0}^{p+q-1} \nu \cdot (A^{k'} \cdot B)(i) \cdot u(k-k') \right] $$

One can then set $\mu_{k'} \leftarrow \nu \cdot (A^{k'} \cdot B)(i)$ for all $k \in [0..p+q-1]$ and conclude the proof of the lemma. $\square$