Systems & Control Letters 35 (1998) 6978

On the boolean minimal realization problemin the max-plus algebra

Bart De Schutter
a;
, Vincent Blondel
b
, Remco de Vries
a
, Bart De Moor
a
a
ESAT-SISTA, K.U. Leuven, Kardinaal Mercierlaan 94, B-3001 Heverlee (Leuven), Belgium
b
Institute of Mathematics, University of Li ege, Sart Tilman B37, B-4000 Li ege, Belgium
Received 18 December 1997; received in revised form 5 March 1998; accepted 25 March 1998
Abstract
One of the open problems in the max-plus-algebraic system theory for discrete event systems is the minimal realization
problem. In this paper we present some results in connection with the minimal realization problem in the max-plus algebra.
First we characterize the minimal system order of a max-linear discrete event system. We also introduce a canonical
representation of the impulse response of a max-linear discrete event system. Next we consider a simplied version of
the general minimal realization problem: the boolean minimal realization problem, i.e., we consider models in which the
entries of the system matrices are either equal to the max-plus-algebraic zero element or to the max-plus-algebraic identity
element. We give a lower bound for the minimal system order of a max-plus-algebraic boolean discrete event system. We
show that the decision problem that corresponds to the boolean realization problem (i.e., deciding whether or not a boolean
realization of a given order exists) is decidable, and that the boolean minimal realization problem can be solved in a number
of elementary operations that is bounded from above by an exponential of the square of (any upper bound of) the minimal
system order. We also point out some open problems, the most important of which is whether or not the boolean minimal
realization problem can be solved in polynomial time. c 1998 Elsevier Science B.V. All rights reserved.
Keywords: Discrete event systems; Max-plus algebra; Minimal state space realization; Boolean max-plus algebra; Complexity
1. Introduction
The max-plus-algebra [1, 4], which has maximiza-
tion and addition as its basic operations, is one of the
frameworks that can be used to model a class of
discrete event systems (DESs). Typical examples of
DESs are exible manufacturing systems, telecom-
munication networks, parallel processing systems and
logistic systems. One of the characteristic features
of DESs, as opposed to continuous variable systems
(i.e., systems the behavior of which can be described
by dierence or dierential equations), is that their
dynamics are event-driven as opposed to time-driven.

Corresponding author. Tel.: +32-16-32.17.09; fax: +32-16-

32.19.70; e-mail: [email protected].
An event corresponds to the start or the end of an
activity. For a manufacturing system possible events
are: the completion of a part on a machine, a machine
breakdown, or a buer becoming empty.
In general, models that describe the behavior of a
DES are nonlinear, but there exists a class of DESs
the max-linear DESs for which the model be-
comes linear when formulated in the max-plus
algebra [1, 3, 4]. One of the open problems in the
max-plus-algebraic system theory for DESs is the
minimal realization problem, which can be stated as
follows: given the impulse response of a max-linear
DES, determine a model of smallest possible size the
impulse response of which coincides with the given
impulse response. The minimal realization problem in
the max-plus algebra is the central topic of this paper.
0167-6911/98/$ see front matter c 1998 Elsevier Science B.V. All rights reserved.
PII: S0167- 6911( 98) 00035- 8
70 B. De Schutter et al. / Systems & Control Letters 35 (1998) 6978
2. Preliminaries
2.1. Notation
Let A be an mn matrix. Then A
i; :
is the ith row of
A and A
:; j
is the jth column of A. Let {1; 2; : : : ; m}
and {1; 2; : : : ; n}. The submatrix of A obtained by
removing all rows of A that are not indexed by and
all columns that are not indexed by is denoted by
A

. The submatrix of A obtained by removing all rows

(columns) of A except for those indexed by () is
denoted by A
; :
(A
:;
).
If x R then x is the smallest integer that is
larger than or equal to x. Two real functions f
and g are asymptotically equivalent in the neigh-
borhood of , denoted by f(x) g(x); x , if
lim
x
f(x)=g(x) =1. The set of the nonnegative
(positive) integers is denoted by N (N
0
).
2.2. Max-plus algebra
Dene = and R

=R{}. The basic op-

erations of the max-plus algebra [1, 4] are the maxi-
mum (represented by ) and the addition (represented
by ):
x y = max(x; y); x y =x +y
with x; y R

. We call the max-plus-algebraic sum

and the max-plus-algebraic product. Note that and
0 are the identity elements for respectively and .
Remark 2.1. The analogy between and +, and be-
tween and is evidenced by the following equiv-
alences:
x y =z e
xs
+e
ys
c e
zs
; s ; (1)
x y =z e
xs
e
ys
=e
zs
for all s0 (2)
with x; y; z R

, and c =2 if x =y and c =1 oth-

erwise.
1
Using this transformation the structure
(R

; ; ) can be mapped to a structure consisting

of exponentials with conventional addition and mul-
tiplication as basic operations (see [16, 17]). Note
that the exponential transformation maps to 0, and
0 to 1. This mapping allows us to transform some
results from conventional algebra to the max-plus
algebra. However, since there does not exist an equiv-
alent of the minus operator in the max-plus algebra,
1
We assume that e
s
=0 for all s0 by denition.
many results and techniques of conventional alge-
bra and linear system theory cannot be translated in
a straightforward way to the max-plus algebra and
max-plus-algebraic system theory.
However, if we restrict ourselves to results in non-
negative linear algebra (i.e., results in which the mi-
nus and the subtraction operators do not appear), then
we can transformthese results to the max-plus algebra.
This makes that many results of, e.g., linear system
theory for nonnegative systems can be transformed to
max-plus-algebraic system theory and vice versa (see
also Section 3.2 and the paragraph before Proposi-
tion 3.4). As a consequence, the problems discussed
in this paper are not only relevant to the discrete event
systems domain but to other domains such as linear
system theory for nonnegative systems as well.
The operations and are extended to matrices
as follows. If A; BR
mn

then
(AB)
ij
=a
ij
b
ij
for all i; j. If AR
mp

and BR
pn

then
(AB)
ij
=
p

k=1
a
ik
b
kj
for all i; j. The matrix
mn
is the max-plus-algebraic
zero matrix: (
mn
)
ij
= for all i; j. If the dimensions
of the max-plus-algebraic zero matrix are not indi-
cated, they should be clear from the context. The ma-
trix E
n
is the max-plus-algebraic identity matrix: we
have (E
n
)
ii
=0 for all i and (E
n
)
ij
= for all i; j with
i =j. The kth max-plus-algebraic matrix power of a
matrix AR
nn

with k N is dened as follows:

A

0
=E
n
and A

k
=AA A
. .
k times
if k0:
Dene B={0; }. A matrix with entries in B is called
a max-plus-algebraic boolean matrix.
2.3. Graph theory
In order to dene some additional max-plus-
algebraic concepts and to prove some propositions
in the next sections, we also need some results from
graph theory, which will be presented in this section.
A graph G is dened as an ordered pair (V; E),
where V is a set of elements called vertices and E is
a set of (unordered) pairs of vertices. The elements of
E are called edges.
B. De Schutter et al. / Systems & Control Letters 35 (1998) 6978 71
If the vertices of a graph can be partitioned into two
disjunct sets X and Y such that all edges go from ver-
tices in X to vertices in Y, then the graph is called bi-
partite. Consider a bipartite graph G=(X Y; E) with
X ={x
1
; x
2
; : : : ; x
m
}; Y ={y
1
; y
2
; : : : ; y
n
}; X Y =
and such that every element of E can be written as
{x; y} with x X and y Y. With G we associate a
matrix AB
nm
by setting a
ji
=0 if there is an edge
between x
i
and y
j
and a
ji
= otherwise. We call A
the incidence matrix of G, and G the transition graph
of A. If for each x
i
X and each y
j
Y, there is an
edge between x
i
and y
j
then we say that the bipartite
graph is complete.
A directed graph G is dened as an ordered pair
(V; A), where V is a set of vertices and A is a
set of ordered pairs of vertices. The elements of A
are called arcs. Let G=(V; A) be a directed graph
with V ={v
1
; v
2
; : : : ; v
n
}. A path of length l (l N
0
)
is a sequence of vertices v
i
0
; v
i
1
; : : : ; v
i
l
such that
(v
i
k
; v
i
k+1
) A for k =0; 1; : : : ; l 1. We represent
this path by v
i
0
v
i
1
v
i
l
. Vertex v
i
0
is the ini-
tial vertex of the path and v
i
l
is the nal vertex of the
path. When the initial and the nal vertex of a path
coincide, we have a circuit. An elementary circuit is
a circuit in which no vertex appears more than once,
except for the initial vertex, which appears exactly
twice.
A directed graph G=(V; A) is called strongly con-
nected if for any two dierent vertices v
i
; v
j
V there
exists a path from v
i
to v
j
. A maximal strongly con-
nected subgraph (m.s.c.s.) G
sub
of a directed graph
G is a strongly connected subgraph that is maximal,
i.e., if we add any extra vertex (and the correspond-
ing arcs) of G to G
sub
then G
sub
is no longer strongly
connected.
The cyclicity
2
of an m.s.c.s. is the greatest com-
mon divisor of the lengths of all the circuits of the
given m.s.c.s. If an m.s.c.s. or a graph contains no cir-
cuits then its cyclicity is equal to 0 by denition. The
cyclicity c(G) of a graph G is the least common mul-
tiple of the nonzero cyclicities of its m.s.c.s.s.
If we have a directed graph G=(V; A) with
V ={1; 2; : : : ; n} and if we associate a real number
a
ij
with each arc (j; i) A, then we say that G is a
weighted directed graph. We call a
ij
the weight of
the arc (j; i). Note that the rst subscript of a
ij
corre-
sponds to the nal (and not the initial) vertex of the
arc (j; i).
2
This denition of cyclicity has been introduced in [2] (see
also [1]).
Consider AR
nn

. The precedence graph of A,

denoted by G(A), is a weighted directed graph with
set of vertices {1; 2; : : : ; n} and an arc (j; i) with
weight a
ij
for each a
ij
=. The weight of a path
i
1
i
2
i
l
in G(A) is dened as the sum
of the weights of the arcs that compose the path:
a
i
2
i
1
+a
i
3
i
2
+ +a
i
l
i
l1
. The average weight of a
circuit is dened as the weight of the circuit divided
by the length of the circuit. An elementary circuit
of G(A) is called critical if it has maximum average
weight among all circuits. The critical graph G
c
(A)
consists of those vertices and arcs of G(A) that belong
to a critical circuit of G(A).
The cyclicity of a matrix AR
nn

is denoted by
c(A) and is equal to the cyclicity of the critical graph of
the precedence graph of A. So c(A) =c(G
c
(A)). Note
that if AB
nn
then every circuit in G(A) is critical,
which implies that c(A) =c(G
c
(A)) =c(G(A)).
2.4. Some extra denitions and propositions
Denition 2.2 (Irreducibility). The matrix AR
nn

with n2 is called irreducible if G(A) is strongly

connected, i.e., if (AA

2
A

n1
)
ij
= for all
i; j with i =j. By denition a 1 1 matrix is always
irreducible.
Denition 2.3 (Max-plus-algebraic eigenvalue and
eigenvector). Let AR
nn

. If there exist R

and
v R
n

with v =
n1
such that Av = v then we
say that is a max-plus-algebraic eigenvalue of A and
that v is a corresponding max-plus-algebraic eigen-
vector of A.
It can be shown that every matrix AR
nn

has at
least 1 and at most n max-plus-algebraic eigenvalues
(see, e.g. [1]). In particular, irreducible matrices have
only one max-plus-algebraic eigenvalue (see, e.g. [3]).
For algorithms to determine max-plus-algebraic eigen-
values and eigenvectors the interested reader is re-
ferred to [1, 3, 15] and the references cited therein.
Theorem 2.4. If AR
nn

is irreducible, then
k
0
N such that kk
0
: A

k+c
=

c
A

k
(3)
where is the (unique) max-plus-algebraic eigen-
value of A and c is the cyclicity of A.
Proof. See, e.g. [1, 3, 12].
72 B. De Schutter et al. / Systems & Control Letters 35 (1998) 6978
Now we give some extra propositions in connection
with the cyclicity of a general matrix and with the
integer k
0
that appears in Theorem 2.4 for a boolean
matrix. We shall need these propositions in Section 4.
The proofs of these (and related) propositions appear
in [8, 9].
For the cyclicity of a general matrix we have the
following upper bound:
Lemma 2.5. If AR
nn

then we have c(A)6

exp(n=e) =
n
with =e
1=e
.
For general (possibly not irreducible) boolean ma-
trices we can improve the result of Theorem 2.4 by
giving an upper bound for the integer k
0
:
Theorem 2.6. Let AB
nn
and let c be the cyclicity
of A. We have
A

k+c
=A

k
for all k2n
2
3n +2:
If A is irreducible then
A

k+c
=A

k
for all kn
2
2n +2:
It is easy to verify that the max-plus-algebraic
eigenvalue of a max-plus-algebraic boolean matrix
is either 0 or . That is why does not appear in
Theorem 2.6. The extension of Theorem 2.6 to gen-
eral matrices with entries in R

is a topic of current
research. The following example shows that in con-
trast to boolean matrices, where the upper bound for
the integer k
0
of Theorem 2.4 only depends on the
size of the matrix for a general matrix A with entries
in R

an upper bound for k

0
also depends on the range
and resolution (i.e., on the size of the representation)
of the non- entries of A.
Example 2.7. Let N N and consider
A(N) =
_
1 N
0 0
_
:
The matrix A(N) is irreducible and has cyclicity 1 and
max-plus-algebraic eigenvalue 0. We have
(A(N))

k
=
_
max(k; N) N
0 0
_
for each k N
0
. This implies that the smallest integer
k
0
for which Eq. (3) holds, is given by k
0
=N, i.e., k
0
depends on the range of the non- entries of A(N).
A similar example can be found in ([1], p. 152).
This example shows that in general k
0
depends on the
resolution of the non- entries of the matrix A.
3. Max-plus-algebraic system theory
3.1. State space models and impulse responses
In [1, 3, 4] it has been shown that there is a class
of discrete event systems (DESs) that can be modeled
by a max-plus-algebraic model of the following form:
x(k +1) =Ax(k) Bu(k); (4)
y(k) =C x(k): (5)
The vector x represents the state, u is the input vector
and y the output vector of the system. For a manufac-
turing system, u(k) would typically represent the time
instants at which raw material is fed to the system for
the (k 1)th time, x(k) the time instants at which the
machines start processing the kth batch of intermedi-
ate products, and y(k) the time instants at which the
kth batch of nished products leaves the system. A
DES that can be modeled by Eqs. (4) and (5) will be
called a max-linear time-invariant DES.
The number of components of the state vector x will
be called the order of the state space model. We shall
characterize a model of the form (4) and (5) by the
triple (A; B; C) of system matrices. A system with one
input and one output is called a single-input single-
output (SISO) system. A system with more than one
input and more than one output is called a multi-input
multi-output (MIMO) system.
Let i {1; 2; : : : ; m}. A max-plus-algebraic unit im-
pulse is a sequence {e
k
}

k=0
dened by
e
k
=
_
0 if k =0;
if k =1; 2; : : : :
If we apply a max-plus-algebraic unit impulse to the
ith input of the system, and if we assume x(0) =
n1
,
then we get
y(k) =C A

k1
B
:; i
for k =1; 2; 3; : : :
as the output of the DES. Note that y(k) corresponds
to the ith column of the matrix G
k1
def
= C A

k1
B
for k =1; 2; 3; : : : The sequence {G
k
}

k=0
is called the
impulse response of the DES, and the G
k
s are called
the impulse response matrices.
B. De Schutter et al. / Systems & Control Letters 35 (1998) 6978 73
The impulse response of a max-linear time-invariant
DES can be characterized by the following theorem:
Theorem 3.1. If {G
k
}

k=0
is the impulse response of
a max-linear time-invariant DES with m inputs and
l outputs then
i {1; 2; : : : ; l}; j {1; 2; : : : ; m}; c N
0
;

1
;
2
; : : : ;
c
R

; k
0
N such that k N:
(G
k
0
+kc +c +s 1
)
ij
=

c
s
(G
k
0
+kc +s 1
)
ij
for s =1; 2; : : : ; c: (6)
Proof. This is a direct consequence of, e.g.,
Corollary 1.1.9 of ([11], p. 166) or of Proposi-
tion 1.2.2 of [12].
If a sequence G ={G
k
}

k=0
exhibits a behavior of
the form (6) then we say that the sequence G is ulti-
mately periodic. If G ={G
k
}

k=0
is an ultimately pe-
riodic sequence then the smallest possible c for which
(6) holds is called the period of G.
Proposition 3.2. A sequence G ={G
k
}

k=0
with
G
k
R
lm

for all k is the impulse response of a

max-linear time-invariant DES if and only if it is an
ultimately periodic sequence.
Proof. A proof of this proposition for SISO systems
can be found in [1, 11, 12]. For MIMO systems the
only if part corresponds to Theorem 3.1. To prove
the if part for MIMO systems we consider each se-
quence {(G
k
)
ij
}

k=0
separately; since such a sequence
corresponds to a SISO system, we can apply the rst
part of this proof and afterwards merge all SISO sys-
tems into one large MIMO system (see also [5]).
Based on Theorem 3.1 we now introduce a new
concept, the so-called canonical representation of
the impulse response of a max-linear time-invariant
DES or which is equivalent of an ultimately
periodic sequence. We shall only do this for im-
pulse responses of SISO systems. The extension to
MIMO systems is straightforward. The goal of in-
troducing this canonical representation is to get a
concise, unique representation of an ultimately pe-
riodic sequence. Consider an ultimately periodic
sequence of real numbers g ={g
k
}

k=0
. First we de-
termine the smallest possible c N
0
for which (6)
holds. The
s
s are then dened uniquely
3
(up to
a circular permutation of the indices). Next, we
determine the smallest possible k
0
N such that
(6) holds for all k0. Now we can uniquely rep-
resent the sequence g by the (k
0
+2c +1)-tuple
(c;
1
;
2
; : : : ;
c
; g
0
; g
1
; : : : ; g
k
0
+c1
). The subsequence
g
0
; g
1
; : : : ; g
k
0
1
will be called the transient part of g.
Example 3.3. Consider the sequence g =0; 0; 0; 0; 0;
1; 0; 2; 0; 3; 0; 4; 0; 5; : : : : This is an ultimately peri-
odic sequence with period c =2;
1
=0;
2
=1 and
k
0
=2. The transient part of g is the subsequence
g
0
; g
1
=0; 0. The canonical representation of the se-
quence g is given by (2; 0; 1; 0; 0; 0; 0).
3.2. The minimal state space realization problem
If G ={G
k
}

k=0
is an ultimately periodic sequence
with G
k
R
lm

for all k, then it follows from Proposi-

tion 3.2 that G is the impulse response of a max-linear
time-invariant DES with m inputs and l outputs. Now
consider the following problem:
Given an ultimately periodic sequence G =
{G
k
}

k=0
with G
k
R
lm

for all k and an integer

r, nd, if possible, matrices AR
rr

; BR
rm

and C R
lr

such that (A; B; C) is a realization

of G, i.e., G
k
=C A

k
B for all k N.
This problem is called the state space realization
problem. If we make r as small as possible, then the
problem is called the minimal state space realization
problem and the resulting value of r is called the min-
imal system order.
The minimal state space realization problem for
max-linear time-invariant DESs has been studied by
many authors and for some very specic cases the
problem has been solved (see [7, 13, 16, 17]). How-
ever, at present it is still an open problem whether
there exist tractable methods to solve the general min-
imal state space realization problem.
3.3. The minimal system order
If G ={G
k
}

k=0
is a sequence with G
k
R
lr

for
all k, then we dene the (semi-innite) block Hankel
3
Provided that for a subsequence of the form ; ; ; : : : ; we
take
s
equal to .
74 B. De Schutter et al. / Systems & Control Letters 35 (1998) 6978
matrix
H(G)
def
=
_

_
G
0
G
1
G
2
: : :
G
1
G
2
G
3
: : :
G
2
G
3
G
4
: : :
.
.
.
.
.
.
.
.
.
.
.
.
_

_
:
The following proposition is a generalization to the
MIMO case of Proposition 2.3.1 of ([11], p. 175).
It is also an adaptation to max-linear systems of
a similar theorem for nonnegative linear systems
([19], Theorem 5.4.10).
4
Proposition 3.4. Let G ={G}

k=0
be the impulse re-
sponse of a max-linear time-invariant DES with m
inputs and l outputs. Let n be the smallest integer
for which there exist matrices AR
nn

; U R
n

and V R
n

such that
H(G) =U V and U A=U;
where U is the matrix obtained by removing the rst
l rows of U. Then n is equal to the minimal system
order.
Proof. Let n
min
be the minimal system order of the
given system and let the triple (A
min
; B
min
; C
min
) be a
minimal state space realization of G. If we dene
U
min
=
_

_
C
min
C
min
A
min
C
min
A

2
min
.
.
.
_

_
and
V
min
= [
B
min
A
min
B
min
A

2
min
B
min

];
then it is easy to verify that U
min
V
min
=H(G) and
U
min
A
min
=U
min
. This implies that n6n
min
.
Dene
k
={kl +1; kl +2; : : : ; kl +l} and
k
=
{km+1; km+2; : : : ; km+m} for k =0; 1; 2; : : : Dene
C =U

0
; :
and B=V
:;
0
. Now we prove by induction
that U

k
; :
=C A

k
for k =0; 1; 2; : : : :
For k =0 we have U

0
; :
=C =C A

0
. Now we
assume that U

k
; :
=CA

k
and we prove that U

k+1
; :
=
C A

k+1
. Since U A=U, we have U

k+1
; :
=U

k
; :

A=C A

k
A=C A

k+1
. Since U V =H(G)
we have C A

k
B=U

k
; :
V
:;
0
=(H(G))

k
;
0
=
4
Recall that in Remark 2.1 the relation between max-plus al-
gebra and (nonnegative) conventional algebra has been shown.
Based on this relation some results from system theory for non-
negative systems can be translated to max-plus-algebraic system
theory and vice versa.
G
k
. Hence, the triple (A; B; C) is a state space realiza-
tion of G. This implies that nn
min
. Since n6n
min
and nn
min
, we have n =n
min
.
Denition 3.5 (Max-plus-algebraic Schein rank
[11]). Let AR
mn

with A=
mn
. The smallest
integer r for which there exist matrices U R
mr

and V R
rn

such that A=U V is called the

max-plus-algebraic Schein rank of A and it is de-
noted by rank
; Schein
(A). By denition we have
rank
; Schein
() =0.
Proposition 3.4 implies that the max-plus-algebraic
Schein rank of H(G) is a lower bound for the min-
imal system order. However, the following theorem
shows that, unless P =NP, this lower bound cannot
be computed in a number of operations that increases
polynomially with the size of H(G). This remains so
even when H(G) is a boolean matrix. (For basic de-
nitions and more information on NP-completeness the
reader is referred to [10].)
Theorem 3.6. Determining the max-plus-algebraic
Schein rank of a max-plus-algebraic boolean matrix
is an NP-hard problem.
Proof. This proof is based on [14]. If A is a boolean
matrix then the transition graph of A will be denoted
by G
A
. From ([18], Remark 6.7) it follows that the
max-plus-algebraic Schein rank of A is equal to the
minimum number of complete bipartite subgraphs of
G
A
the union of which includes all edges of G
A
. In-
deed, if we consider the incidence matrix of a com-
plete bipartite subgraph, then all the entries of this
matrix are equal to 0. On the other hand, the equation
U V =A can be rewritten as
r

i=1
U
:; i
V
i; :
=A: (7)
It is easy to verify that if u; v B
r
, then the 0 entries of
the matrix u v
T
forma submatrix of u v
T
. This sub-
matrix corresponds to a complete bipartite subgraph
of the transition graph of u v
T
. So determining the
minimal integer r for which Eq. (7) holds, is equiva-
lent to determining the minimal number of complete
bipartite subgraphs of G
A
the union of which includes
all edges of G
A
.
Now consider the decision problem that corre-
sponds to the problem of covering a bipartite graph by
B. De Schutter et al. / Systems & Control Letters 35 (1998) 6978 75
complete bipartite subgraphs (problem GT18 of [10]):
Instance: Bipartite graph G with a set of vertices
V and a set of edges E, and a positive integer
K6#E.
Question: Are there k6K subsets V
1
; V
2
; : : : ; V
k
of V such that each V
i
induces a complete bipar-
tite subgraph of G and such that for each edge
{u; v} E there is some V
i
that contains both u
and v?
Since this decision problem is NP-complete [10, 18],
the problem of determining the minimum number of
complete bipartite subgraphs whose union includes all
of the edges of a bipartite graph is NP-hard. As a con-
sequence the problem of determining the max-plus-
algebraic Schein rank of a max-plus-algebraic boolean
matrix is an NP-hard problem.
An upper bound for the minimal system order is
given in [11, 12] (see also [6]). Note that at present
there do not exist ecient (i.e., polynomial time) al-
gorithms to compute a non-trivial lower bound for the
minimal system order for a given ultimately periodic
sequence.
Since the general minimal realization problem is
still an open problem, we consider a simplied version
of this problem in the next section.
4. The boolean minimal realization problem
A max-linear time-invariant DES for which all the
entries of all the impulse response matrices belong
to B={0; } is called a boolean max-linear time-
invariant DES. It is easy to verify that if we have an
rth order state space realization (A; B; C) of a boolean
max-linear time-invariant DES where the entries of
A; B; C belong to R

, then there also exists an rth

order state space realization (

A;

B;

C) such that the
entries of

A;

B and

C belong to B.
4.1. Comparing boolean impulse responses
The following corollaries are direct consequences
of Theorem 2.6.
Corollary 4.1. Consider a boolean max-linear time-
invariant DES with minimal system order n and im-
pulse response G ={G
k
}

k=0
. Let c be the period of
G. Then we have
G
k+c
=G
k
for all k2n
2
3n +2:
Corollary 4.2. Let G ={G
k
}

k=0
and F ={F
k
}

k=0
be impulse responses of boolean max-linear time-
invariant DESs with minimal system order less
than or equal to n. Let c be the maximum of the
period of G and the period of F. If G
k
=F
k
for
k =0; 1; : : : ; 2n
2
3n +1 +c then G
k
=F
k
for all
k N.
The last corollary gives an explicit upper bound on
the number of terms that two impulse responses of
boolean max-linear time-invariant DESs should have
in common in order to coincide completely.
4.2. A lower bound for the minimal system order
Let G ={G
k
}

k=0
be the impulse response of a
boolean max-linear time-invariant DES. From Propo-
sition 3.4 it follows that the max-plus-algebraic Schein
of the matrix H(G) is a lower bound for the mini-
mal system order. From Theorem 3.6 it follows that,
unless P =NP, this lower bound cannot be computed
eciently. However, for a boolean impulse response
the following lemma provides an easily computable
lower bound for the minimal system order:
Lemma 4.3. Consider a boolean max-linear time-
invariant DES with minimal system order n and im-
pulse response G ={G
k
}

k=0
. Let c be the period of
G. Let L be the length of the transient part of the
impulse response, i.e., L is equal to the smallest inte-
ger K for which we have G
k+c
=G
k
for all kK. If
L2 then
n
3 +

8L 7
4
:
Proof. From Corollary 4.1 it follows that
L62n
2
3n +2: (8)
If is easy to verify that this condition holds for every
n N if L =0 or if L =1. So from now on we assume
that L2. The zeros of the function f dened by
f(n) =2n
2
3n +2 L are n
1
=
1
4
(3 +

8L 7) and
n
2
=
1
4
(3

8L 7). Since n
2
60 if L2 and since n
is always positive, the function f will be nonnegative
if nn
1
. Hence, condition (8) will only be satised if
nn
1
.
76 B. De Schutter et al. / Systems & Control Letters 35 (1998) 6978
4.3. The complexity of the boolean minimal realiza-
tion problem
In this section we consider the following two prob-
lems:
the boolean realization decision problem (BRDP):
Given an ultimately periodic sequence G={G
k
}

k=0
with G
k
B
lm
in its canonical representation and
an integer r, does there exist an rth order boolean
state space realization of G? This problem will be
denoted by BRDP(G; r).
the boolean minimal realization problem (BMRP):
Given an ultimately periodic sequence G={G
k
}

k=0
with G
k
B
lm
in its canonical representation,
compute a minimal state space realization of G.
This problem will be denoted by BMRP(G).
Proposition 4.4. Let G ={G
k
}

k=0
be an ultimately
periodic sequence with G
k
B
lm
and let r N.
The problem BRDP(G; r) is decidable using a nite
number of elementary operations (such as addition;
subtraction; multiplication; division; maximum; min-
imum and comparison).
Proof. Since G is an ultimately periodic sequence, it
corresponds to the impulse response of a boolean max-
linear time-invariant DES. Let n be the minimal sys-
tem order of this system. From ([6], Proposition A.6)
it follows that an upper bound n
u
for n can be com-
puted in a nite number of steps. If rn
u
then there
exists an rth order state space realization of G and
then the answer to the BRDP(G; r) is armative.
From now on we assume that r6n
u
. Let c be the
period of G. Dene K =2n
2
u
3n
u
+1 +c. If we
have an rth order state space realization character-
ized by the triple of system matrices (A; B; C) and if
C A

k
B=G
k
for all k6K then it follows from
Corollary 4.2 that (A; B; C) is an rth order state space
realization of G.
This implies that the BRDP(G; r) is equivalent to
checking whether or not the following system of equa-
tions has a solution:
C A

k
B=G
k
for k =0; 1; : : : ; K; (9)
with AB
rr
; BB
rm
and C B
lr
. Since
(A

k
)
pq
=
r

i
1
=1
r

i
2
=1

r

i
k1
=1
a
pi
1
a
i
1
i
2
a
i
k1
q
;
Eq. (9) can be rewritten as
r

p=1
r

q=1
r
k1

s=1
c
ip

u=1
r

v=1
a
uv

kpqsuv
b
qj
=(G
k
)
ij
(10)
for i =1; 2; : : : ; l; j =1; 2; : : : ; m and k =0; 1; : : : ; K,
where
kpqsuv
is the number of times that a
uv
appears in
the sth termof (A

k
)
pq
. Note that if a
uv
does not appear
in that term we have
kpqsuv
=0 since a

0
=0 a =0.
If we put the entries of A; B and C in one large col-
umn vector x of length L =(r +m+l)r, if we put the
entries of the (G
k
)
ij
s in one large column vector d of
length M =lm(K +1) and if we reformulate every-
thing in conventional algebra, Eq. (10) is an equation
of the form
max
i
(
ki1
x
1
+
ki2
x
2
+ +
kiL
x
L
) =d
k
: (11)
The system of equation (11) with k =0; 1; : : : ; M can
be solved using an exhaustive search method: First we
select for the rst equation a term for which the maxi-
mum is reached, and we eliminate a variable if possi-
ble. Then we select for the second equation a term for
which the maximum is reached, and so on, until we
either nd a solution or reach an inconsistent system
of equations. In the latter case we backtrack and se-
lect another candidate for the maximizing term in the
equation where a last choice was made. This contin-
ues until we either nd a solution (which yields an rth
order state space realization of G), or have exhausted
all possible choices, in which case the system cannot
be solved (which implies that no rth order state space
realization of G exists). Hence, we can give an answer
to BRDP(G; r) using a nite number of elementary
operations.
Remark 4.5. A similar reasoning can be used to show
that the general realization decision problem is also
decidable provided that we can give an a priori upper
bound for the number of terms K in the system (9).
In the formulation of Proposition 4.4 we have used
the concept decidability in a rather loose and infor-
mal way. However, it can be veried that our use of
decidability corresponds to the formal concept of de-
cidability in the Turing machine sense.
Proposition 4.6. Let G ={G
k
}

k=0
be an ultimately
periodic sequence with G
k
B
lm
for all k. Let n
u
be
B. De Schutter et al. / Systems & Control Letters 35 (1998) 6978 77
an upper bound
5
for the minimal system order of the
max-linear time-invariant DES the impulse response
of which coincides with G. Then BMRP(G) can be
solved in a number of elementary operations that is
bounded from above by the function f dened by
f(n
u
; l; m) = 2m
_
2n
2
u
3n
u
+2 + exp
_
n
u
e
__

n
u

r=1
r (l +r) 2
r
2
+r(m+l)
: (12)
Furthermore, f(n
u
; l; m)6
n
2
u
with =3
m+l+3
.
Proof. Since G is ultimately periodic it corresponds
to the impulse response of a max-linear time-invariant
DES. Furthermore, since all the entries of the G
k
s are
in B; G also corresponds to the impulse response of
a boolean max-linear time-invariant DES.
Assume that the minimal system order of the
boolean max-linear time-invariant DES we are look-
ing for is equal to n. Let n
l
be a lower bound for the
minimal system order (that is, e.g., obtained by using
Lemma 4.3).
If c is the period of G, then c6exp(n=e) by
Lemma 2.5. Hence, c6exp(n
u
=e). Dene K =
2n
2
u
3n
u
+2 + exp(n
u
=e). If we have a sequence
F ={F
k
}

k=0
that is the impulse response of an rth
order boolean max-linear time-invariant DES with
r6n
u
, then by Corollary 4.2 it suces to check
whether the rst K terms of F and G are equal in
order to decide whether F and G coincide.
Now we can apply the following procedure which
is combination of an incremental search procedure
6
(for the system order) combined with an enumera-
tive procedure (for the entries of the system matri-
ces). We start with a guess r for the minimal system
order that is equal to n
l
. Then we consider all pos-
sible triples (A; B; C) with AB
rr
; BB
rm
and
C B
lr
. For each triple we consider the nite se-
quence F ={C A

k
B}
K1
k=0
. If the terms of this
sequence are equal to the rst K terms of G, then the
triple (A; B; C) is a minimal state space realization of
G and r is the minimal system order. Otherwise, we
consider the next triple (A; B; C). Note that the num-
ber of triples that should be considered is less than or
equal to 2
r
2
+r(m+l)
. For each triple (A; B; C) we have
to compute at most K terms of the sequence F and
5
See [6, 11, 12] for a nite upper bound for the minimal system
order that can be computed eciently.
6
We could also have used a binary search procedure.
compare them with the corresponding term of G. It is
easy to verify that this can be done using a number of
additions or comparisons that is less than or equal to
Klm(2r 1) +(K 1)rm(2r 1) +Klm
=Klm(2r) +(K 1)rm(2r 1)
6Klm2r +Krm2r
62Kmr(r +l):
If all rth order triples have been considered and no
state space realization of G has been found yet, we
augment r and repeat the procedure described above.
Since n
u
is an upper bound for the minimal system
order, this procedure will ultimately lead to a minimal
state space realization of G. Note that in the worst
case r ranges from 1 to n
u
.
Hence, the number of elementary operations that is
needed to solve BMRP(G) in bounded from above by
the function f dened by Eq. (12).
Furthermore, it can be veried that f(n
u
; l; m)6
n
2
u
for all n
u
; l; mN
0
.
It is still an open problem whether there exist poly-
nomial time algorithms to solve the BRDP and the
BMRP.
5. Conclusions
In this paper we have considered the minimal
state space realization problem for max-linear time-
invariant discrete event systems (DESs). We have
derived a lower bound for the minimal system order
and discussed the computational complexity of com-
puting this lower bound. We have also introduced a
canonical representation of the impulse response of a
max-linear time-invariant DES. Next we have directed
our attention to the boolean minimal realization prob-
lem. We have shown that this problem can be solved
in a number of operations that is bounded from above
by an exponential of the square of the minimal system
order. We have also derived an eciently computable
lower bound for the minimal system order.
In our future research we hope to extend some of
the results of this paper to general max-linear time-
invariant DESs.
78 B. De Schutter et al. / Systems & Control Letters 35 (1998) 6978
Acknowledgements
The algorithm used in the proof of Proposition 4.4
was suggested to the rst author by S. Gaubert. The
algorithm can be thought of as a Tarski-Seidenberg
elimination method for the max-plus algebra.
Bart De Schutter is a senior research assistant with
the F.W.O. (Fund for Scientic Research-Flanders).
Bart De Moor is a research associate with the F.W.O.
This research was sponsored by the Concerted Action
Project of the Flemish Community, entitled Model-
based Information Processing Systems (GOA-
MIPS), by the Belgian program on interuniversity
attraction poles (IUAP P4-02 and IUAP P4-24), by
the ALAPEDES project of the European Community
Training and Mobility of Researchers Program, and
by the European Commission Human Capital and
Mobility Network SIMONET (System Identication
and Modelling Network).
References
[1] F. Baccelli, G. Cohen, G.J. Olsder, J.P. Quadrat, Syn-
chronization and Linearity, Wiley, New York, 1992.
[2] G. Cohen, D. Dubois, J.P. Quadrat, M. Viot, Analyse du
comportement p eriodique de syst emes de production par la
th eorie des diodes, Tech. Rep. 191, INRIA, Le Chesnay,
France, February 1983.
[3] G. Cohen, D. Dubois, J.P. Quadrat, M. Viot, A linear-
system-theoretic view of discrete-event processes and its use
for performance evaluation in manufacturing, IEEE Trans.
Automat. Control 30 (3) (1985) 210220.
[4] R.A. Cuninghame-Green, Minimax Algebra, Lecture Notes
in Economics and Mathematical Systems, vol. 166, Springer,
Berlin, 1979.
[5] B. De Schutter, Max-algebraic system theory for discrete
event systems, Ph.D. Thesis, Faculty of Applied Sciences,
K.U. Leuven, Leuven, Belgium, 1996.
[6] B. De Schutter, V. Blondel, R. de Vries, B. De Moor, On the
boolean minimal realization problem in the max-plus algebra:
Addendum, Tech. Rep. 97-68a, ESAT-SISTA, K.U. Leuven,
Leuven, Belgium, December 1997.
[7] B. De Schutter, B. De Moor, Minimal realization in the
max algebra is an extended linear complementarity problem,
Systems Control Lett. 25 (2) (1995) 103111.
[8] B. De Schutter, B. De Moor, On the sequence of consecutive
powers of a matrix in a boolean algebra, Tech. Rep. 97-67,
ESAT-SISTA, K.U. Leuven, Leuven, Belgium, April 1998,
revised version, submitted for publication.
[9] B. De Schutter, B. De Moor, On the ultimate behavior of
the sequence of consecutive powers of a matrix in the max-
plus algebra, Tech. Rep. 98-32, ESAT-SISTA, K.U. Leuven,
Leuven, Belgium, May 1998.
[10] M.R. Garey, D.S. Johnson, Computers and Intractability:
A Guide to the Theory of NP-Completeness, Freeman,
San Francisco, 1979.
[11] S. Gaubert, Th eorie des syst emes lin eaires dans les diodes,
Ph.D. thesis, Ecole Nationale Sup erieure des Mines de Paris,
France, July 1992.
[12] S. Gaubert, On rational series in one variable over certain
dioids, Tech. Rep. 2162, INRIA, Le Chesnay, France, January
1994.
[13] S. Gaubert, P. Butkovi c, R. Cuninghame-Green, Minimal
(max; +) realization of convex sequences, SIAM J. Control
Optim. 36 (1) (1998) 137147.
[14] D.A. Gregory, N.J. Pullman, Semiring rank: Boolean rank and
nonnegative rank factorizations, J. Combin. Inform. System
Sci. 8 (3) (1983) 223233.
[15] R.M. Karp, A characterization of the minimum cycle mean
in a digraph, Discrete Math. 23 (1978) 309311.
[16] G.J. Olsder, Some results on the minimal realization of
discrete-event dynamic systems, Tech. Rep. 85-35, Delft
University of Technology, Faculty of Technical Mathematics
and Informatics, Delft, The Netherlands, 1985.
[17] G.J. Olsder, On the characteristic equation and minimal
realizations for discrete-event dynamic systems, in: Proc. 7th
Internat. Conf. on Analysis and Optimization of Systems,
Antibes, France, Lecture Notes in Control and Information
Sciences, vol. 83, Springer, Berlin, 1986, pp. 189201.
[18] J. Orlin, Contentment in graph theory: covering graphs
with cliques, Proc. Koninklijke Nederlandse Akademie van
Wetenschappen: Series A: Mathematical Sciences, vol. 80,
1977, pp. 406424.
[19] J.M. van den Hof, System theory and system identication of
compartmental systems, Ph.D. thesis, Faculty of Mathematics
and Natural Sciences, University of Groningen, Groningen,
The Netherlands, November 1996.