Corollary 1. When K = Qmax , Zmax , or Nmin , the existence of a realization of dimension n of a K-recognizable sequence is decidable. Indeed, when K = Qmax , the non-emptiness of a semi-polyhedral set is decidable, because the rst order theory of (Q, +, ) is decidable, or, to use a perhaps more elementary argument, because the non-emptiness of an ordinary polyhedron can be checked by linear programming (see e.g. [Sch86]). When K = Zmax or Nmin , the corollary follows from the decidability of Presburgers arithmetics (see e.g. [End72]). It follows from Corollary 1 that there is an algorithm to compute max-plus minimal realizations, a problem which arose from the beginning of the development of the max-plus modelling of discrete event systems [CMQV89], which was mentioned in the book [BCOQ92] and was stated by Olsder and De Schutter [ODS99] as one of the open problems of [BSVW99]. In fact, the algorithm is very expensive (see the discussion in 5), so our result only implies that we can solve the realization problem in small dimension. A Caml implementation by G. Melquiond and P. Philipps is available 3. It would be interesting to nd a less expensive algorithm. Before proving Theorem 1, it is instructive to show why classical arguments fail to prove these result. A natural idea, would be to show that if two sequences S and T have realizations of respective sizes N and M , there is an integer (N, M ) such that: (Sk = Tk , k (N, M )) = (Sk = Tk , k N). (1)
(Results of this kind are called equality theorems by Eilenberg, see [Eil74, Chap. 6, 8].) Indeed, if the semiring K satises property (1), then, the set of realizations of dimension N of a sequence T given by a realization of dimension M is the set dened by the nite system of equations cAk b = Tk , for k = 0,. , (N, M ). There are two classical cases where property (1) is true. First, if K is a nite semiring (like the Boolean semiring), (1) is trivially true since the set of realizations of a given dimension is nite (and, of course, the minimal realization problem is decidable). A second, more interesting case, is when K is a subsemiring of a commutative ring. Then, the Cayley-Hamilton theorem implies that (1) holds with (N, M ) = N + M 1, by a standard argument (see [Eil74, Chap. 6, proof of Th. 8.1]). An interesting feature of the max-plus semiring is that (1) does not hold. For instance, the realization of dimension 2 over Qmax , c= , A= 0 , 1 b= , 0
3 http://perso.ens-lyon.fr/natacha.portier/realisations-max-plus.tar.gz
where is an element of Qmax , recognizes the sequence S : Sk = max(, k). To distinguish between S and S , we need to consider values of k min(, ), and this contradicts (1). Our proof of Theorem 1 relies on a more general result, of independent interest. Let us rst briey recall some basic facts about rational series in one letter (see [BR88] for a detailed presentation). Let X denote an indeterminate. A sequence S0 , S1 ,. K can be identied to the formal series S = S0 S1 X S2 X 2 K[[X]] (in particular, the indeterminate X corresponds to the sequence , , , ,.). The set of formal series K[[X]], equipped with entrywise sum and Cauchy product, is a semiring. The Kleenes star of a series S, dened when S has a zero constant coecient, is S = S 0 S S 2 The k-th coecient of S will sometimes be denoted by S, X k instead of Sk. The Kleene-Schtzenberger theorem states that S is recognizable if, and only if, it u is rational, i.e., if it can be represented by a well formed expression involving sums, products, stars, and monomials. Consider now a nite set of commuting indeterminates, = {d1 ,. , dn }, and let K[] denote the semiring of polynomials in d1 ,. , dn. To a vector d = (d1 ,. , dn ) K n , we associate the evaluation morphism K[][[X]] K[[X]], which sends the series S K[][[X]] to the series [S]d obtained by replacing each indeterminate di by the value di. Borrowing the probabilist notation, we denote by {S = S} the set {d K n | [S]d = S}. More generally, for S, T K[][[X]], we shall write for instance {S T} as an abbreviation of {d K n | [S]d [T]d }.

Theorem 2. (Rational series synthesis) Let K denote an idempotent linearly ordered archimedian cancellative commutative semiring. For all rational series S K[][[X]] and for all rational series S K[[X]], the set {S = S} is semipolyhedral. This theorem will be proved in Section 3. An intuitive way to state this result is to say that the set of values of the coecients of a rational expression which yield a given rational series is semi-polyhedral. Theorem 1 is an immediate corollary of Theorem 2. Indeed, consider the set = N whose elements are the 2N + N 2 indeterminates ci , Aij , bj , where 1 i, j N. Let c = (ci ) (K[N ])1N , A = (Aij ) (K[N ])N N , b = (bj ) (K[N ])N 1 , and consider the universal series SN = c(AX) b = cb cAbX K[N ][[X]], which, by construction, is recognizable (or equivalently, rational). Since the set of realizations of dimension n of a rational series S K[[X]] is exactly {SN = S}, Theorem 2 implies Theorem 1. We warn the reader that some apparently minor variants of {S = S} need not be semi-polyhedral. For instance, since {S S} = {S S = S}, by Theorem 2, {S S} is semi-polyhedral, but we shall see in 4 that {S S} need not be semi-polyhedral.
In Section 5, we bound the complexity of the algorithm which is contained in the proof of Theorems 1 and 2. The details of this complexity analysis are lengthy, but its principle is simple: we need rst to compute a star height one representation of the universal series SN = c(AX) b. We give an explicit representation, which turns out to be of double exponential size. Then, we compute the semi-polyhedral set arising from this expression, which yields a simply exponential blow up, leading to a nal triple exponential bound. This high complexity implies that Theorem 1 is only of theoretical interest. However, it should be noted that Theorem 2 allows us to solve more generally the structured realization problem, in which some coecients of the realizations are constrained to be zero. Consider for instance the problem of computing all N dimensional realizations (c, A, b) of a linear sequence S, subject to the constraint that A is diagonal. The set of realizations becomes { 1iN ci (Aii X) bi = S}, and Theorem 2 shows that this set is semi-polyhedral. For such structured problems in which the universal series SN is replaced by a polynomial size rational expression, the present approach leads only to a simply exponential complexity. The algorithmic diculties encountered here are consistent with the observation that algorithmic issues concerning linear systems over rings (and a fortiori over semirings) are generally harder than in the case over elds. In particular, the powerful geometric approach based on the computations of invariant spaces does carry over to the ring case [BM91], and even to the maxplus case [CGQ99a, Kat07, LGKL09], but then, the analogues of the classical xed point algorithms do not always terminate (due to the lack of Artinian or Noetherian properties). The present algebraic approach, via rational series, yields alternative tools to the geometric approach: no termination issue arises, but the algorithms are subject to a curse of complexity. It is also instructive to look at Theorem 2 in the light of the recent developments of tropical geometry [IMS07, RGST05]. The latter studies in particular the tropical analogues of algebraic sets. The tropical analogues of semi-algebraic sets could be considered as well: it seems reasonable to dene them precisely as the special semi-polyhedral sets introduced here (recall that the exponents appearing in the monomials are required to be nonnegative integers). Then, Theorem 1 may be thought of as the max-plus analogue of a known result, that the set of nonnegative realizations of a given dimension of a linear sequence over the real numbers (equipped with the usual addition and multiplication) is semi-algebraic (this follows readily from the equality theorem mentioned above). Then, a comparison with the complexity of existing semi-algebraic algorithms [BPR96] suggests that the present triple exponential bound is probably suboptimal. To improve it, we would need to further exploit the tropical semialgebraic structure. This raises further issues which are beyond the scope of this paper.

Let us complete this long introduction by pointing out a few relevant references about the minimal realization problem. First, there are two not so well known theorems, which hold in arbitrary semirings. A result of Fliess [Fli75] characterizes the minimal dimension of realization as the minimal dimension of a semimodule stable by shift and containing the semimodule of rows of the Hankel matrix. (The result is stated there for the semiring (R+ , +, ), but, as observed by Jacob [Jac75], the proof is valid in an arbitrary semiring.) Maeda and Kodama found independently closely related results [MK80]. As observed by Duchamp and Reutenauer (see Theorem 2 in [DR97]), Fliesss characterization is a third fundamental statement to add to the Kleene-Schtzenberger theorem. The classical realization theorems u over elds are immediate corollaries of this result. The results of Anderson, Deistler, Farina and Bevenuti [ADFB96] and Benvenuti and Farina [BF99] for nice applications of these ideas. We also refer the reader to the book [BR10] for a general discussion of minimization issues concerning noncommutative rational series. A second fundamental result, due to Eilenberg [Eil74, Ch. 16] (inspired by Kalman), extends the notion of recognizability and shows the existence of a minimal module which recognizes a sequence. The diculty is that this module need not be free. (Eilenbergs theorem is stated for modules over rings, but, as noted in [CGQ99b], it can be extended to semimodules over semirings). The max-plus minimal realization problem was raised by Cohen, Moller, Quadrat and Viot [CMQV85], and by Olsder [Ols86] (see also [BCOQ92]). There are relatively few general results about this (hard) problem. Olsder [Ols86] showed some connections between max-plus realizations, and conventional realizations, via exponential asymptotics. Cuninghame-Green [CG91] gave a realization procedure, which yields, when it can be applied, an upper bound for the minimal dimension of realization. Some lower and upper bounds involving various notions of rank over the max-plus semiring were given in [Gau92, Chap. 6]. In particular, the cardinality of a minimal generating family of the row or column space of the Hankel matrix, which characterizes the minimal dimension of realization in the case of elds, is only a (possibly coarse) upper bound in the max-plus semiring. The lower bound of [Gau92, Chap. 6] (which involves maxplus determinants) also appears in [GBCG98], where it is used to extend to the convex case a theorem proved by Butkovi and Cuninghame-Green [CGB95] in c the strictly convex case. De Schutter and De Moor [DSDM95] observed that the (much simpler) partial max-plus realization problem can be interpreted as an extended linear complementarity problem. This work was pursued by De Schutter in [DS96]. 2. Max-plus Rational Expressions In this section, we recall some basic results about max-plus rational expressions, which will be needed in the proof of Theorem 2. 6

The rst step of the proof of Theorem 2 is the following well known star height one representation (some variants of which already appeared in particular in works of Moller [Mol88], of Bonnier-Rigny and Krob [BRK94], and in [Gau92, Gau94a]). All these results can be thought of as specializations, or renements, of general results on commutative rational expressions [ES69, Con71]. In the sequel, K denotes a generic semiring (which may or may not coincide with the semiring K of Theorem 2). Lemma 1. Let K be an idempotent commutative semiring. A rational series S K[[X]] can be written as S=

Pi (qi X c ) ,

where P1 ,. , Pr K[X], q1 ,. , qr K, and c is a positive integer. Proof. It suces to check that the set of series of the form (2) is closed by sum, Cauchy product, and Kleenes star. This follows easily from the following classical commutative rational identities (see e.g. [Con71]), which are valid for all U, V K[[X]] (with zero constant coecient) and k 1, (U V) (VU ) U
V(U V) , ( U Uk1 )(Uk )

(4) (5)

(only in (3) we used the idempotency and commutativity of the semiring). The representation (2) of s is far from being unique. In particular, thanks to the rational identity U = U Uk1 Uk U , which holds for all k 1, we can always rewrite the series (2) as S = P X c

ui X i (qi X c )

where 0 i c 1, ui K, and P K[X] has degree less than c. The interest of (7), by comparison with (2), is that the asymptotics of S, X k can be read directly from the rational expression. Indeed, for all 0 j c 1 and k 0, ui qk. (8) S, X (k+)c+j = i
When K is the max-plus semiring, the representations (7) and (8) can be simplied thanks to the archimedian property. We say that a series S K[[X]] 7
is ultimately geometric if there is an integer and a scalar K such that S, X k+1 = S, X k , for all k . The merge of c series S (0) ,. , S (c1) is the series S (0) (X c ) XS (1) (X c ) X c1 S (c1) (X c ), whose coecient sequence is obtained by merging the coecient sequences of S (0) ,. , S (c1). E.g., the merge of S (0) = X = 0 0X 0X 2 and S (1) = 1(1X) = 1 2X 3X 2 (9) is T = (X 2 ) 1X(1X 2) = 0 1X 0X 2 2X 3 0X 4 3X 5 (10)
The following elementary but useful consequence of Lemma 1 and of the archimedian condition characterizes the rational series over max-plus like semirings. This theorem, which is a series analogue of the max-plus cyclicity theorem for powers of max-plus matrices of Cohen, Dubois, Quadrat and Viot [CDQV83] (see also [CDQV85, BCOQ92, GP97, AGW05, HOvdW06]), was anticipated by Cohen, Moller, Quadrat and Viot in [CMQV89], where a result similar to Theorem 3 is proved in the special case of series with nondecreasing coecient sequence. Moller [Mol88], and Bonnier-Rigny and Krob [BRK94], proved results which are essentially equivalent to Theorem 3, which is taken from [Gau92, Gau94a, Gau94b] (slightly more general assumptions are made on the semiring, in the last two references). Theorem 3 is in fact a max-plus analogue of a deeper result, Soittolas theorem [Soi76], which characterizes nonnegative rational series as merges of series with a dominant root (see also Perrin [Per92]). Theorem 3. Let K denote an idempotent linearly ordered archimedian commutative semiring. A series S K[[X]] is rational if, and only if, it is a merge of ultimately geometric series. Proof. We have to show that a rational series S K[[X]] satises S, X (k+)c+j = uq k , k 0, 0 j c 1 , (11)

for some u, q K, and for some integers 0, c 1. But S has a representation k of the form (8), i.e. S, X (k+1 )c+j = iIj ui qi , where ui , qi K, Ij is a nite set, and 1 0, c 1 are integers. Let q = iIj qi. Since K is linearly ordered and coincides with the least upper bound, we can nd an index such that q = q, and u um for all m such that qm = q. Then, k k S, X (k+1 )c+j = iIj , qi <q ui qi u q. Using the archimedian property, k we get S, X (k+1 )c+j = u q , for k large enough, say for k k2. Setting k = 1 + k2 , q = q , and u = u q 2 c , we get (11).
Equivalently, S can be written as S = P X c
where P K[X] has degree less than c, and ui , qi K. Finally, we shall need the inverse operation of merging, that we call undersampling. For each integer 0 j c 1 and for all series T K[[X]], we dene the undersampled series: T (j,c) =

T, X kc+j X k.

For instance, when T is as in (10), T (0,2) and T (1,2) respectively coincide with the series S (0) and S (1) of (9). Trivially, testing the equality of two series amounts to testing the equality of undersampled series: Lemma 2. Let c 1. Two series T, T K[[X]] coincide if, and only if, (j,c) T(j,c) = T for all 0 j c 1. A last, trivial, remark will allow us to split the test that S = S into transient and ultimate parts. Recall that X m S denotes the series T such that T, X k = S, X m+k. Lemma 3. Let m 0. Two series T, T K[[X]] coincide if, and only if, T, X k = T , X k for k m 1, and X m T = X m T. 3. Proof of Theorem 2 In the sequel, K denotes a semiring that satises the assumptions of Theorem 2 and = {d1 ,. , dn } is a nite set of commuting indeterminates. We rst prove a simple lemma. Lemma 4. For all p K[] and p K, the sets {p p}, {p p}, and {p = p}, are semi-polyhedral. Proof. Since in an idempotent semiring u v u v = v, it suces to prove more generally that when p, q K[], {p = q} is semi-polyhedral. When p or q = , {p = q} is trivially semi-polyhedral. Otherwise, we can write p and q as nite sums of monomials, p = iI pi , and q = jJ qj , with I, J =. For all (i, j) I J, consider the polyhedron Uij = kI {pi pk } lJ {qj ql } {pi = qj }. Since K is linearly ordered, and since the sum is the least upper bound for , {p = q} = iI,jJ Uij is a semi-polyhedral set.
The fact that {p = p} is semi-polyhedral was already noticed by De Schutter [DS96] (who derived this result by modelling p = p as an extended linear complementarity problem). We now prove Theorem 2 (the proof will be illustrated by the examples in 4). The discussion following the proof of Lemma 1 shows that the rational series S K[][[X]] can be represented as (7). Let F (S) denote the set of couples of integers (, c) for which S has such a representation. The rational identities (5),(6) imply that (, c) F (S) = (, ck) F (S) for all k 1. Similarly, the rational identity (6) shows that (, c) F (S) = (k, c) F (S), for all k . The same argument can be applied to the set F (S) of couples of integers (, c) for which the rational series S K[[X]] has a representation of the form (12). Hence, F (S) F (S) = , which allows us to assume that S and S are given by (7) and (12), where and c are the same in both formul. By Lemma 2, {S = S} = 0jc1 {S(j,c) = S (j,c) }. Since the intersection of semi-polyhedral sets is semi-polyhedral, and since the series S(j,c) and S (j,c) have expressions of the form (7) and (12), respectively, but with c = 1, it suces to show Theorem 2 when c = 1. Moreover, thanks to Lemma 3, {S = S} = 0k1 { S, X k = S, X k } {X S = X S}. By Lemma 4, the sets { S, X k = S, X k } are semi-polyhedral, hence, using again the closure of semi-polyhedral sets by intersection, it suces to show that {X S = X S} is semi-polyhedral. The series X S and X S again have expressions of the form (7) and (12), respectively, but with = 0, i.e. with p = and p =. Summarizing, it remains to prove Theorem 2 when S =

The set A is depicted by the grey region on Figure 1. Note that the border of this region contains an innite number of vertices lying on the hyperbola u1 v2 = 1. It is geometrically obvious that A is not semi-polyhedral, but we can
4 We say, as usual, that two representations (c, A, b) and (c , A , b ) are similar if c = cP, A = P 1 AP, b = P 1 b, for some invertible matrix P. In the max-plus semiring, an invertible matrix is the product of a diagonal matrix by a permutation matrix (see e.g. [BCOQ92] for this standard result). Unlike in conventional algebra, max-plus minimal realizations are in general not similar. 5 We recall that x stands for the integer part of x and x is equal to x and is the rounding to the smallest bigger than x integer
Figure 1: The set of realizations (c, A, b) of dimension 2 such that cAk b 0 for all k is not semi-polyhedral. A two dimensional section of this set is represented.
check it without appealing to the gure, as follows. For any integer n the point (n, 1/n) belongs to the set A. If A was a nite union of polyhedra, then there would be a polyhedron P A with an innite number of points of (n, 1/n) in P , and the low borderline of P would be the line {v2 = 0}. This is not possible, because for v2 > 0, the point (u1 , v2 ) is not in A, as soon as v2 < 1/(u1 + 2). 5. Universal Commutative Rational Expressions and Complexity Analysis In this section, we bound the complexity of the algorithm of the proofs of Theorem 1 and 2. Suppose we are looking for a realization of size N of the series S given as in (12): S = P X 0 c 0

0ic0 1

where c0 1, 0 0, P K[X] has degree less than 0 c0 , and ui , qi K. A critical step of our algorithm is to build, like we did in (19), a star height one representation of the form (7) for the universal series S = SN : S = P X 1 c 1

ui X i (qi X c1 )

where 0 i c1 1, ui K, and P K[X] has degree less than 1 c1. In section 5.1, we shall give an explicit star height one representation for SN which is of independent interest. This expression has a double exponential size. In 5.2, we shall bound the size of an expression of {S = S} as a union of 14

intersection of half-spaces, when S and S are given by (21) and (22), and show that the subproblem of computing {S = S} has a simply exponential complexity. Finally, in section 5.3, we shall combine the results of 5.1 and 5.2 to show that the method of Theorem 1 yields a triply exponential algorithm to compute the set of realizations of a max-plus rational series. This triply exponential bound is a coarse one: trying examples by hand suggests that the naive version of the algorithm that we analyse here could be made much more practicable by using linear programming and constraint programming techniques. 5.1. Universal Commutative Rational Expressions Let us associate to the triple c K1N , A KN N , b KN 1 a digraph GN composed of the nodes 1,. , N , together with an input node in and an output node out, arcs j i with weights Aij X, for 1 i, j N , input arcs in i with weights bi , and output arcs i out with weights ci. The weight of a path , denoted by w(), is dened as the product of the weight of its arcs. We say that two circuits and are cyclic conjugates if one is obtained from the other by a circular permutation. When K is commutative, w() = w( ). We denote by CN the set of conjugacy classes of elementary circuits of GN. Let C CN , and let denote a path of GN. We say that C is accessible from if the union of the circuits of C and of the path is a connected subgraph (we use here the undirected notion of connectedness, not to be confused with strong connectedness). An accessible set C for a path looks typically as follows: c1 c2 We denote by A () the set of C CN accessible from. We set S + = SS , for all series s such that S is well dened. We denote by PN the set of elementary paths from in to out. The following result is Lemma 6.2.3 from [Gau92, Chap. VII]. Proposition 1. Let K denote a commutative idempotent semiring, A KN N , b KN 1 , c K1N , and SN = c(AX) b. We have SN =
(By convention, A () for all paths , and the products in (23) corresponding to C = are equal to.) 15

CA () C

w()+ .
Before proving Proposition 1, it is instructive to consider the case when N = 2. Then, there are four paths in the sum (23), 1 = in 1 out, 2 = in 2 out, 3 = in out, 4 = in out, with respective weights c1 b1 , c2 b2 , cb1 , and cb2. We have for instance A (1 ) = {{1 1}, {1}, {1, 1 1}, {1, 2 2}, {1, 1 1, 2 2}}. Thus, the contribution of 1 in (23) is

+ c1 b1 ( + ()+ + ()+ ()+ + 11 ()+ + ) 22 22
and, considering the similar contributions of 2 , 3 , 4 , it is easy to see that (23) coincides with (19). Proof of Proposition 1. Let B denote the right hand side of (23). We shall prove by induction on k the following property: (Hk ) for all (possibly non elementary) paths from in to out, for all sets of k circuits C = {1 ,. , k } A (), and for all n1 ,. , nk 1, w()w(1 )n1. w(k )nk is the weight of a path from in to out. If k = 1, since the graph induced by 1 is connected, 1 must have a common node with , say node r. Possibly after replacing 1 by a cyclic conjugate, we may assume that r is the initial (and nal) node of. We can write = out,r r,in (here, and in the sequel, composition of paths is denoted by concatenation), where r,in is a path from in to r, and out,r is a n path from r to out. Thus w()w(1 )n1 = w(out,r r,in ) is the weight of the n1 path = out,r 1 r,in from in to out, which proves (H1 ). We now assume that k 2. By denition of A (), at least one of the circuits 1 ,. , k , say 1 , has a node in common with. Arguing as in the proof of (H1 ), we see that w()w()n1 is the weight of a path from in to out, which is such that {2 ,. , k } A ( ). Applying (Hk1 ) to , we get (Hk ). Since (Hk ) holds for all k, all the terms of the sum B can be interpreted as weights of paths from in to out, but we know that SN is the sum of the weights of all paths from in to out. Hence, B SN. Conversely, if is a path n n from in to out, we can write = 1 2. k k k+1 , where 1 2. k+1 is an elementary path from in to out, and 1 ,. , k are elementary circuits which form an accessible set for. This implies that w() B, and since this holds for all , SN B. We tabulate the size of the sets determining the size of the expression (23), for further use. We denote by #X the cardinality of a set X. It is easy to check that

N! eN ! = O(N !) , i!

and that #CN =

N!. (N i)!i!

The CN are called logarithmic numbers, their exponential generating function, 1 CN z N , is equal to log(1 z) exp(z). Using for instance a singuN 1 (N !) larity analysis [FO90, Th. 2], we get #CN = O((N 1)! log N ). (25)
We have of course #C #CN , and #A () 2#CN , for all C CN and PN. 5.2. Computing {S = S} We now embark in the complexity analysis of the algorithm contained in the proof of Theorem 1. This analysis involves a tedious but conceptually simple bookeeping: we bound the number of polyhedral sets appearing when expressing that the star-height one rational expression (23) evaluates to a given rational series. If p K[], we denote by |p| the number of monomials which appear in p (for instance, if K = Qmax , = {a, b}, p = 2a2 ab 7b, |p| = 4). We consider the series S and S given by (7) and (12), respectively, with K = K[], and we set m = max( max | p, X i |, max max(|ui |, |qi |))

0i<c 1i

and i = #{1 j | j = i}. Proposition 2. Let S and S be given by (7) and (12), respectively. The set {S = S} can be expressed as the union of at most mc+2c ( 0i<c i )2c intersections of at most (m + 1)c + 2c + 2m half-spaces. To show Proposition 2, we need to introduce some adapted notation. We say that a couple of positive integers [n, k] is a symbol of a subset S of K , and we write S [n, k], if S can be written as the union of n sets, S = 1in Si , where each Si is the intersection of at most k half-spaces. Of course, S [n, k] = S [n , k ], for all n n, k k. For instance, taking p = iI pi K[] and p K as in Lemma 4, and specializing the proof of Lemma 4, we have {p = p} =

({pi p} {pi p}

jI j=i

{pj p}).

Since, by denition, |p| = #I we get from (26): {p = p} [|p|, |p| + 1]. Similarly, since {p p} = iI {pi p}, {p p} [1, |p|]. 17 (28) (27)
It will be convenient to equip symbols with the binary laws and , dened by: [n, k] [n , k ] = [n + n , max(k, k )], [n, k] [n , k ] = [nn , k + k ].
This notation is motivated by the following rule, which holds for all subsets S , S K : (S [n, k] and S [n , k ]) = (S S [n, k] [n , k ] and S S [n, k] [n , k ]).(29)
Proof of Proposition 2. As a preliminary step, we compute symbols for the more elementary sets involved in the proof of Theorem 2. First, if u, q K[] and u, q K, we get from Lemma 5, {u(qX) u(qX) } = {u = } ({u u} {q q}), hence
{u(qX) u(qX) } [1, |u|] ([1, |u|] [1, |q|]) = [2, |u| + |q|].
Moreover, Lemma 5 shows that {u(qX) = u(qX) } = {u = u} {q = q}, if u =. When u = , {u(qX) = u(qX) } = {u = } = {u }. Hence, using (27), (28), we get {u(qX) = u(qX) } [1, |u|] if u = [|u|, |u| + 1] [|q|, |q| + 1] = [|u||q|, |u| + |q| + 2] else (31)
Let us now take u1 ,. , ur , q1 ,. , qr K[], u, q K, Ti = ui (qi X) , S = u(qX). Lemma 7 shows that Ti = S

{Ti = S}

1jr j=i

{Tj S} ,

hence, using (30) and (31) Ti = S
[|ui ||qi |, |ui | + |qi | + 2] [2, |uj | + |qj |]

|ui ||qi |2r1 , 2 +

(|ui | + |qi |))
The proof of Theorem 2, together with (33), (26), shows that {S = S} =

0i<c

{pi = pi }

1j j =i

uj (qj X) = ui (qi X)
[m, m + 1] [i m2 2i 1 , 2 + 2i m]

, (m + 1)c + 2c + 2m] ,

which concludes the proof. 5.3. Final Complexity Analysis Let K = K[] and E be a formal expression of a polynomial P K[X]. We denote by m(E) the maximum number of monomials of K[] arising as a coecient of a power of X in some polynomial expression of E. By abuse of notation we will write m(P) instead of m(E). For instance, with = {a, b} and K = Qmax , if S = 7aX 3abX X 2 ( 8a2bX)(3X 2 ) , m(S) = 2(= | P, X | = |7a 3ab|). If the expression is (7): m(S) = max( max | P, X i |, max max(|ui |, |qi |))
Corollary 2. Let K = K[], A KN N , b KN 1 , c K1N , and SN = c(AX) b. Then SN can be written as in 7: SN = P X 1 c1
where c1 = N !, 1 = O(N !), = 2O(N !), 0 i c1 1, ui K, m(SN ) = 2O(N !) and P K[X] has degree smaller than 1 c1. Proof. We have: SN =

PN ,CA ()

w()w()
For every (and also) the monomial P = w() has degree at most N and is equal to qX where q K is a monomial (i.e. m(q = 1) and N. Let be the integer such that = N !. Using the identity (5) we get: P(qX ) = = P( qX . q 1 X ( 1) )(q X N ! ) P (q X N ! )
where the polynomial P has degree N + N ! = O(N !) and m(P ) = m(q ) = 1. Using the identity (3) we have immediately: SN =

Pj (qj X N ! )

where P1 ,. , Pr K[X], q1 ,. , qr K, m(qj ) #CN and m(Pj ) = (N + N ! )#CN 1. To evaluate r and the degrees of these polynomials, results from 5.1 are useful: the degree of each Pj is O((N !)2 ), r = 2O(N !) , m(qj ) = O(N !) and m(Pj ) = 2O(N !). 19
Next step is to obtain an expression like (7) using the identity (6). Here is an example: s = (0 X 3 )(2X 2 ) (2 X 4 )(3X 2 ) = (2X 2 ) XX 2 (2X 2 ) 2(3X 2 ) X 2 X 2 (3X 2 ) = (0 2X 2 4X 4 (2X 2 ) ) XX 2 (0 2X 2 (2X 2 ) ) 2(0 3X 2 6X 4 (3X 2 ) ) X 2 X 2 (0 3X 2 (3X 2 ) ) = (2 5X 2 X 3 X 4 ) X 4 (4(2X 2 ) 2X(2X 2 ) 8(3X 2) 3X 2 (3X 2 ) ) Let c1 = N ! and 1 be the smaller integer such that c+ cis larger than the degrees of Pj. Then 1 = O(N !) and there are some polynomials Pj,0 ,. , Pj,1 of degrees at most csuch that: Pj = Pj,0 + X c1 Pj,1 + X 2c1 Pj,2 +. + X 1 c1 Pj,1 Using (6) we have: Pj (Qj X c1 ) = Pj,0 ( Qj X c1 . Qj X (1 1)c1 (Qk )1 X 1 c1 (Qj X c1 ) ) j c1 c1 Pj,1 X ( Qj X . QX (1 2)c1 Qj X (1 1)c1 (Qj X c1 ) ) j. Pj,1 X 1 c1 (Qj X c1 ) and thus Pj (Qj X c1 ) = Rj X 1 c1

[BM91] G. Basile and G. Marro. Controlled and Conditioned Invariants in Linear System Theory. Prentice Hall, 1991. [BP02] V. Blondel and N. Portier. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and its Applications, 351-352:9198, june 2002. [BPR96] S. Basu, R. Pollack, and M.-F. Roy. On the combinatorial and algebraic complexity of quantier elimination. J. ACM, 43(6):1002 1045, 1996. [BR88] J. Berstel and C. Reutenauer. Rational Series and their Languages. Springer, 1988.
[BR10] J. Berstel and C. Reutenauer. Noncommutative Rational Series With Applications. 2010. New edition of [BR88], available on the rst authors web page, to be published by CUP. [BRK94] A. Bonnier-Rigny and D. Krob. A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring. Theoret. Comput. Sci., 134(1):2750, 1994. Second International Colloquium on Words, Languages and Combinatorics (Kyoto, 1992). [BSVW99] V. D. Blondel, E. D. Sontag, M. Vidyasagar, and J. C. Willems, editors. Open Problems in Mathematical Systems and Control Theory. Springer, 1999. [CDQV83] G. Cohen, D. Dubois, J. Quadrat, and M. Viot. Analyse du comportement priodique des syst`mes de production par la thorie des e e e dio des. Rapport de recherche 191, INRIA, Le Chesnay, France, 1983. [CDQV85] G. Cohen, D. Dubois, J. Quadrat, and M. Viot. A linear system theoretic view of discrete event processes and its use for performance evaluation in manufacturing. IEEE Trans. on Automatic Control, AC30:210220, 1985. [CG91] R. Cuninghame-Green. Algebraic realization of discrete dynamic systems. In Proceedings of the 1991 IFAC Workshop on Discrete Event System Theory and applications in manufacturing and social phenonmena, Shenyang, China, June 1991. [CGB95] R. A. Cuninghame-Green and P. Butkovi. Discrete-event dynamic c systems: the strictly convex case. Ann. Oper. Res., 57:4563, 1995.
[CGQ99a] G. Cohen, S. Gaubert, and J. P. Quadrat. Max-plus algebra and system theory: where we are and where to go now. Annual Reviews in Control, 23:207219, 1999. [CGQ99b] G. Cohen, S. Gaubert, and J. Quadrat. Max-plus algebra and system theory : where we are and where to go now. Annual Reviews in Control, 23:207219, 1999. [CMQV85] G. Cohen, P. Moller, J. Quadrat, and M. Viot. Une thorie linaire e e des syst`mes a vnements discrets. Rapport de recherche 362, e ` e e INRIA, Le Chesnay, France, 1985. [CMQV89] G. Cohen, P. Moller, J. Quadrat, and M. Viot. Algebraic tools for the performance evaluation of discrete event systems. IEEE Proceedings: Special issue on Discrete Event Systems, 77(1), Jan. 1989. [Con71] J. Conway. Regular algebra and nite machines. Chapman and Hall, 1971. [DR97] G. Duchamp and C. Reutenauer. Un crit`re de rationalit e e provenant de la gomtrie non commutative. Invent. Math., e e 128:613622, 1997. [DS96] B. De Schutter. Max-algebraic system theory for discrete-event systems. Ph. d. thesis, KU Leuven, Feb. 1996. [DSDM95] B. De Schutter and B. De Moor. Minimal realization in the max algebra is an extended linear complementarity problem. Systems Control Lett., 25(2):103111, 1995. [Eil74] S. Eilenberg. Automata, Languages and Machines, volume A. Acad. Press, 1974. [End72] H. Enderton. An introduction to mathematical logic. Academic Press, 1972. [ES69] S. Eilenberg and M. Schtzenberger. Rational sets in commutative u monoids. J. Algebra, 13:173191, 1969. [Fli75] M. Fliess. Sries rationnelles positives et processus stochastiques. e Ann. Inst. Henri Poincar, XI(1):121, 1975. e [FO90] P. Flajolet and A. M. Odlyzko. Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics, 3(2):216240, 1990.

[Gau92] S. Gaubert. Thorie des syst`mes linaires dans les diodes. Th`se, e e e e Ecole des Mines de Paris, July 1992. [Gau94a] S. Gaubert. On rational series in one variable over certain dioids. Rapport de recherche 2162, INRIA, Jan. 1994. [Gau94b] S. Gaubert. Rational series over dioids and discrete event systems. In Proc. of the 11th Conf. on Anal. and Opt. of Systems: Discrete Event Systems, number 199 in Lect. Notes. in Control and Inf. Sci, Sophia Antipolis, June 1994. Springer. [GBCG98] S. Gaubert, P. Butkovi, and R. Cuninghame-Green. Minimal c (max, +) realization of convex sequences. SIAM J. Control Optim., 36(1):137147 (electronic), 1998.
[GP97] S. Gaubert and M. Plus. Methods and applications of (max,+) linear algebra. In R. Reischuk and M. Morvan, editors, STACS97, number 1200 in LNCS, Lbeck, March 1997. Springer. u [HOvdW06] B. Heidergott, G. J. Olsder, and J. van der Woude. Max Plus at Work: Modeling and Analysis of Synchronized Systems, A Course on Max-Plus Algebra and Its Applications. Princeton, 2006. [HU79] J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979. [IMS07] I. Itenberg, G. Mikhalkin, and E. Shustin. Tropical algebraic geometry. Oberwolfach seminars. Birkhuser, 2007. a [Jac75] G. Jacob. Reprsentations et Substitutions Matricielles dans la e thorie matricielle des semigroupes. Th`se, Universit de Paris, e e e 1975. [Kat07] R. D. Katz. Max-plus (A,B)-invariant spaces and control of timed discrete event systems. IEEE Trans. Automat. Control, 52(2):229 241, 2007. Also eprint arxiv:math.OC/0503448. [LGKL09] M. D. Loreto, S. Gaubert, R. D. Katz, and J. J. Loiseau. Duality between invariant spaces for max-plus linear discrete event systems. E-print arXiv:0901.2915, 2009. [MK80] H. Maeda and S. Kodama. Reachability, observability and realizability of linear systems with possitivity constraints. IECE Trans., 63-A:688694, 1980. In Japanese. [Mol88] P. Moller. Thorie algbrique des Syst`mes ` Evnements Discrets. e e e a e Th`se, Ecole des Mines de Paris, 1988. e 25
[ODS99] G. Olsder and B. De Schutter. The minimal realization problem in the max-plus algebra. 1999. Appears in [BSVW99], pages 157162. [Ols86] G. Olsder. On the characteristic equation and minimal realizations for discrete-event dynamic systems. In Analysis and Optimizaton of Systems, number 83 in Lecture notes in Control and Information Sciences, pages 189201. Springer, 1986. [Per92] D. Perrin. On positive matrices. Theor. Comp. Sci., 94:357366, 1992. [Pin98] J.-E. Pin. Tropical semirings. In J. Gunawardena, editor, Idempotency. Cambridge University Press, 1998.