INFORMATIQUE THÉORIQUE ET APPLICATIONSarchive.numdam.org/article/ITA_1994__28_3-4_277_0.pdf · 278 i. SIMON In 1987 H. Leung [4, 5] published an algorithm to décide the same problem

INFORMATIQUE THÉORIQUE ET APPLICATIONS

IMRE SIMONOn semigroups of matrices over the tropical semiringInformatique théorique et applications, tome 28, no 3-4 (1994),p. 277-294<http://www.numdam.org/item?id=ITA_1994__28_3-4_277_0>

© AFCET, 1994, tous droits réservés.

L’accès aux archives de la revue « Informatique théorique et applications » im-plique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/conditions). Toute utilisation commerciale ou impression systématique estconstitutive d’une infraction pénale. Toute copie ou impression de ce fichierdoit contenir la présente mention de copyright.

Article numérisé dans le cadre du programmeNumérisation de documents anciens mathématiques

http://www.numdam.org/

http://www.numdam.org/item?id=ITA_1994__28_3-4_277_0

http://www.numdam.org/conditions

http://www.numdam.org/conditions



Informatique théorique et Applications/Theoretical Informaties and Applications

(vol. 28, n° 3-4, 1994, p. 277 à 294)

ON SEMIGROUPS OF MATRICESOVER THE TROPICAL SEMIRING (*)

by IMRE SIMON (*)

Abstract. - The tropical semiring Ai consists ofthe set ofnatural numbers extended with infinity,equipped with the opérations of taking minimums (as semiring addition) and addition (as semiringmultiplication). We use factorizotion forests to prove finiteness results related to semigroups ofmatrices over Ai. Our method is used to recover results of Hashiguchi, Leung and the author ina unified combinatorial framework.

1. INTRODUCTION

In 1978 [6] we characterized finitely generated finite semigroups ofmatrices over the tropical semiring Ai. (Ai is N U {oo} equipped withthe opérations of minimum and addition.) The results obtained were appliedto solve a long standing open problem of John Brzozowski.

In 1982 K. Hashiguchi [2] proved the decidability of a more gêneraiproblem. Let us take a finitely generated semigroup of matrices over thetropical semiring. Is the set of ail coefficients in a given row and columnfinite or not?

Hashiguchi's method consisted in finding an upper bound for thecoefficients which holds whenever the set in question is finite. That upperbound can be used to synthetize an algorithm which décides the proposedproblem. Later on, in 1986, Hashiguchi improved both his results and hisupper bound but the resulting algorithm is still impractical.

(*) This work was supported by FAPESP, CNPq and CAPES/COFECUB. Major parts of thiswork were done while visiting the Universities of Paris-VI (1986), Rouen (1987) and Paris-VII(1988).

0) Instituto de Matemâtica e Estatfstica, Universidade de Sâo Paulo, 05508-900 Sâo Paulo, SP,Brasil.

Informatique théorique et Applications/Theoretical Informaties and Applications0988-3754/94/03-04/$ 4.00/© AFCET-Gauthier-Villars

278 i. SIMON

In 1987 H. Leung [4, 5] published an algorithm to décide the same problembased on an elaborate extension of our method in [6]. Leung used topologicalarguments and consequently, while giving a much better upper bound on thecomplexity of the problem, he lost the upper bound on the coefficients.

In 1986 the author discovered independently the same algorithm foundby Leung and began building a combinatorial framework for the study ofthe structure of finitely generated semigroups of matrices over the tropicalsemiring. This paper contains our ideas to solve the proposed problemusing factorization forests [8]. Our method gives simultaneously H. Leung'salgorithm and an upper bound on the coefficients.

For further motivation, applications and many remaining open problemswe refer the reader to our survey article [7].

Finally, we mention that using Lemmas 10 and 7 it is easy to recoverHashiguchi's Main Lemma of [3] with validity for any finitely generatedsemigroup of matrices over the tropical semiring. This solves an openproblem stated in [3].

2. SEMIRINGS AND IDEMPOTENT MATRICES

We introducé initially the semirings of our interest. The tropical semiring,denoted A4, has support jW = NU {oo} and opérations a@b = min {a, b}and a <8> 6 = a + 6. The opérations of N are extended to M in the usual wayand the identities of ffi and ® are, respectively, oo and 0. Notice that M isa complete positive commutative semiring [1].

We shall also need an extension of Ai obtained by introducing a newelement u for which a topological interprétation can be given. See [5] fordetails. This semiring shall be denoted by T, its support is T = N U {w, oo}totally ordered by the relation

We extend the opérations of M by defining, for x G T,

ui + x — x + u) = max {a;, x}.

Clearly, Ai is a subsemiring of T.

Our results for the semirings Ai and T are obtained through theconsidération of finite projections as follows. Let TZ be the semiring withsupport 1Z — {0, 1, a>, oo}, totally ordered by the relation 0 < 1 < u < oo,equipped with the opérations a © 6 = min {a, b} and a (g) b = max {a, 6}.


ON SEMIGROUPS OF MATRICES OVER THE TROPICAL SEMIRING 279

The semirings T and 1Z are related by the projection function \& : T —> 1Z,given by

x if x G 1Z

1 otherwise.

The subsemiring M # of 1Z is denoted by A/*; its support is J\f = {0, 1, oo}.We shall use a projection TT : TZ -^ J\f given by

if rrGAf

if x = ÙJ.

For a semiring ÜT we dénote by Mn K the multiplicative monoid ofn x n matrices with coefficients in K, For x G Mn K and z, j G [1, n] thecoefficient of x in row i and column j is denoted by (i, x, j"). The pair(i, j ) shall be called a position; we shall say that (i, x, j) is the coefficientof x in position (i, j ) .

In the case of our semirings the functions ^ and ?r are extended to thecorresponding matrix monoids in the natural way.

Now we characterize idempotent matrices in Mn 1Z.

LEMMA 1 : For every matrix e in Mn TZ the following statements areequivalent,

(i) e is idempotent;

(iï) for every p > 1 and for every feo, fei,..., kp G [1, n], (feo, e, kp) ^max{(feç_i, e, fe^) |q G [1, p]} and for every i, j G [1, n], töere ^xtó5 ak G [1, n] such that (fe, e, fe) ^ (z, e, jf) = max{(i , e, fe), (fe, e, j)};

(in) for every i, j , fe G [1, n], (i, e, j ) < max{(z, e, fe), (fe, e, j ) }/or every i, j G [1, n], (i, e, j ) = max{( i , e, fe), (fe, e, j)} fork G [1, n].

Proof: (i) implies (ii). Assume that e is idempotent and let i, j G[1, n]. Then (i, e, j ) = (i, e2 , j ) = min{max{(z, e, fe), (fe, e, j)} \ k G[1, n]}9 hence, for every fe G [1, n], (i, e, j) < max{( i , e, fe), (fe, e, j ) } .By induction on p, for every feo, fei, • • . , fep G [1, n], (feo, e, fcp) <max{(feg_i, e, feg) | ç G [1, p]}. On the other hand, since e — e2 impliesthat e = e71, there exist i = feo, fei,..., kn = j such that (i, e, j ) =max{(feg_i, e, fe^) | g G [1, n]}. Since fe^ G [1, n] for each one of then -h 1 g's, there exist 0 ^ r < r ' < n, such that fer = fcr' = fe.Using what we just proved, for any 0 ^ 5 < t ^ n, (kSy e, fet) £

vol. 28, n° 3-4, 1994

2 8 0 I. SIMON

max{(A;9_i, e, kq)\q G [5+ 1, t]} ^ max{(fcg_i, e, fcg) | q G [1, n]} =(i, e, j ) , hence, (fcS} e, A*) ^ (i, e, j). Thus,

0 , e> fc) ^ (^ e> J') ^ max{( i , e, fe), (A;, e, j)} < (i, e, j ) ;

where the second inequality follows from the first part of statement (ii).

Hence, (fe, e, A;) ^ (i, e, j ) = max{(i , e, fc), (A;, e, j ) } , as required.

(ii) implies (iii). This is clear.

(iii) implies (i). Choose i, j G [1, n]. The two conditions in (iii) areequivalent to saying that (i, e, j ) — min{max{(ï , e, A;), (A;, e, j ) } | A: G[1, n]}. Hence, (i, e, j ) = (i, e2, j ) and e is idempotent. •

Condition (ii) above suggests the following définition. Let e G Mn 1Z beidempotent. We say that position (i, j ) is anchored in e if there exists aA: G [1, n] such that 0 = (A;, e, A;) £ (i, e, j ) = max{(z, e, A;), (A;, e, j ) } .

LEMMA 2: Le? e G Mn 1Z be idempotent. If (i, e, j ) = 0 then (i, j )ij anchored. Let ko, ki,...y kp G [1, n] te swc/z f/uzf (A;g_i, e, kq) ^(fco, e, A;p) for every q. Then, if (A;r_i, kr) is anchored for some r thenso is (ko, kp).

Proof: The first assertion is an immédiate conséquence of (ii) inLemma 1. To see the second one let l G [1, n] be such that 0 =(/, e, I) ^ (Ar-iï e, A;r) = max{(A; r_i, e, Z), (Z, e, Av)}. Successivelyusing Lemma 1 (ii) and the facts that (Av-1, e, l) ^ (A;r-i, e, kr) andthat (A;9-i, e, kq) ^ (A;o, e, A;p), for every q, we have that

(A;o, e, Z) < max{(A;o, e, fci),..., (A;r-2, e, A;r-i), (A;r_i, e, Z)}

^ max{(/co, e, A;i) , . . . , (A;r_2, e, Av-i), (A;r-i, e, fcr)}

£ (A;o, e, A;p),

f. e. (A;o, e, Z) < (A;o, e, A;p). Similarly, (Z, e, AÎP) < (fco, e, A;p); hence,max{(fco, e, Z), (Z, e, fcp)} < (A;o, e, kp). Then applying Lemma 1 in thethird inequality we have that 0 = (Z, e, Z) ^ (Av-i, e, kr) < (A;o, e, A;p) ^max{(A:o, e, Z), (Z, e, A;p)} £ (A;o, e, A^). This implies that (A;o, kp) isanchored in e. •

The next définitions and Lemma are essential in the sequel. Let e G Mn 1Zbe idempotent. Assume that (i, e, j ) = 1. Position (i, j) is stable in e if itis anchored, otherwise it is unstable. Thus, (i, j ) is unstable if and only if(A;, e, A;) = 1 whenever k G [1, n] and max{(z, e, k), (fc, e, j ) } = 1. Thestabilization of e is the matrix e' G Mn 11 with coefficients



) if (i, e, j ) = 1 and (i, j ) is unstable

z, e, j) otnerwise.

If e — e' then e is stable, otherwise e is unstable. A set X Ç Mn 7£ is stableif the stabilization e" of any idempotent e in X also belongs to X.

For a, b e MnH we define a j) = (h &J i)* It is easy to see that this partial order is compatiblewith matrix multiplication, L e., if a ^ 6 and c < d then ac ^ bd.

LEMMA 3: Le? e G M^ 7£ &£ idempotent. Then é1 is a stable idempotent forwhich ee' = e' = e e. Further, if e is unstable then e$ < J e, where < Jdénotes the usual ordering of the J-classes of Mn 11.

Proof: Let i, j and k be in [1, n]. Observe initially that (i, e, j ) <(i, e0, j). Also, (i, e, j) ^ (i, e8, j ) implies that (i, e, j ) = 1, (ï, eö, j ) =a; and that position (i, j) is not anchored in e. Finally, if 0 —(/c, e, k) < (i, e, j ) = max{(z, e, fc), (/c, e, j )} , then we also have that0 = (fc, eö, fe) < (i, e^ j ) = max{(i, e", fe),(fe, e", j ) } . Indeed, theassumption implies that (fc, fc), (i, jf), (i, fc) and (fe, j) are ail anchored;hence, the respective coefficients in e and e are the same.

To prove that e is idempotent we first claim that, for every i, j , fc E [1, n],(i, e , j) ^ max{(i5 e', fe), (k, e**, j )} . Indeed, if we assume the contrarythen, by Lemma 1,

(i, e, j) < max{(i, e, fc), (fc, e, j )}

We can conclude that (i, e, j) = 1, max{(i, e", A;), (fc, e*, j)} = 1 and(^ e', j) = ui. If (i, e', fc) = 1 then (i, fc) is anchored in e; hence, byLemma 2, (i, j ) is anchored in e, a contradiction. Analogous conclusionholds if (fc, e', j ) = 1 and this proves the claim.

Next we claim that for every i, j G [1, n] there exists a k € [1, n], suchthat (i, e*, j) = max{z, e*, fc), (fc, e*1, j )} . Indeed, choose a k for which(i, e, j) = max{(z, e, fc), (fc, e, j )} and (fc, e, fc) is minimum. Then, usingwhat we already proved.

max{(i, e, Ar), (A;, e, j)} = (i, e, j )

vol. 28, n° 3-4, 1994

282 i. SIMON

If the last inequality is an equality then we are done, otherwise we canconclude that (z, e, j) = (i, e", j) = 1 while max{(i, e', k), (fc, e', j)} =u>. Then, («, j ) is anchored in e and the choice of k implies that(A;, e, fc) = 0. Thus, from the initial observations, 0 = (k} e', A;) ^(h eK j) = max{(z, e', A;), (A;, e**, j )} ; a contradiction which establishesthe claim. Thus, e** is indeed idempotent by Lemma 1.

Now we prove that (e**)" = e'. To see this assume that (i, e", j) = 1.Then, (i, e, j ) = 1 and (i, j ) is stable in e. Let k G [1, n] be suchthat 0 = (fc, e, fc) < (i, e, j) = max{(i, e, fc), (fc, e, j )} . From the initialobservations, 0 = (fc, e", fc) ^ (i, e', j) = max{(i, e", A;), (A:, e', j )} ;hence, (i, j) is stable in e* and (z, (e*)', j ) = (i, e", j ) .

8 Q tl li 11

±,w, rrw wx««xx Mi«v ^> e = e0 which implies that eeR = e3 e = eö. Indeed,e £ e and the idempotence of e and e imply that e < ee' e ^ e . Assume,for a contradiction, that (i, ee^ e, j ) 7 (z, e , j ) for some i, j G [1, n]. Then,(i, ee^ e, j) = (i, e, j ) = 1 and (i, e', j) = w. Let fc, / G [1, n] be such that1 = (i, eeB e, / ) = max{(i, e, fc), (fc, e», i)» (h ^ î)}- T h e n ' (fc

; e^ l ^ ^

hence (fc, Z) is anchored in e. By Lemma 2 (i, j) is anchored in e implyingthat (i, e', j ) — 1, a contradiction which establishes the claim.

Finally assume that e is unstable. From ee$ e = e$ we conclude thatett ^ JTe. Assume that eJeK Since S = MnTlis finite, we have ePe ' = eeKThen, e 7?- ee^ = e . By a dual argument, e £ e'; hence, eTieK Being both eand e idempotents, we conclude that e — e', a contradiction of the stabilityof e. This concludes the proof of Lemma 3. •

3. BOUNDING THE COEFFICIENTS

In this section we dérive some bounds on the size of coefficients ofmatrices over the tropical semiring. Initially we introducé measures of thissize. Let Y Ç Mn T, z G Mn 11 and r G H. We define

s r (F, z) = min {(i, y,j)\y€Y and (i, z, i ) = r} ,

S r (Y, z) = max {(i, y, j ) | y G y and (i, z, j) = r} ,

assuming that the min and max of an empty set are, respectively, 00 and 0.Thus, s r (y, z) (Sr (y, z)) is the least (greatest) coefficient in Y in positionswhose coefficient in z is r.

Let y G Mn M, Y Ç Mn M and z G Mn 71. We say that y agrées withz if yty — zit. Also, y agrées with z if every matrix in Y agrées with z.Note that if yi agrées with z%, for i = 1, 2, then 2/12/2 agrées with z\ 22-Also, if JZ is idempotent then y agrées with z if and only if it agrées with



zK since ZTÇ = z$ 7i\ The définitions above on the size will be used mainlywhen Y agrées with z,

Finally recall that if Y is a subset of a semigroup S then Y + dénotes thesubsemigroup of S generated by Y.

LEMMA 4: Let yi G Mn M agrée with z% G Mn TZ,fori-\, 2. Then, Si (yi y2, z\ z<i) < Si (y\ , z\) + Si (y2, zi) andminjsa; (yi, z\), sw (2/2, 22)} ^ sw (yi y2, *l 22).

Proof: Assume that (i, zi 2:2, j ) = 1 and let fc G [1, n] be suchthat (i, 2fi^2) j ) = max{(z, s i , fc), (fc, 22, j ) } = 1. If (i, ^ i , fe) = 0then (z, y\,k) = 0, since yi agrées with ^ i . Thus, (i, y\,k) £Si (yi, 21). Similarly, (fe, y2) j ) ^ Si (j/2, 2:2). Itfollows that (i, yi 2/2, j ) ^(i, 2/1, fe) + (fe, 2/2, j ) ^ Si (?/i, 21) + S i (2/2, 22). T h u s > s i (2/12/2, ^1^2) =max{(i , yi y2, i ) | ( ^ z\ *2, j) = 1} ^ Si (2/1, zx) + Si (2/2, ^2).

Assume that (i,z\Z2,j) = o; and let fe G [1, n] be such that(*\ y\ V2> j) = (i, yi , fe) + (fe, y2, i ) . Then, LU = (i, zi z2 ) j ) ^max{(i , z i , fe), (fe, z2, i ) } - If (i, 21, fc) = 00 then (i, 2/1, fe) = 00, since 2/1agrées with z\\ thus (i, yi y2, j) = 00 and, since yi y2 agrées with ^1 22, weconclude that (z, z\ Z2, j) = 00: a contradiction. It follows that (i, 21, fc) <00 and similarly (fe, Z2<> j) < 00. Thus, max{(z, 21, fe), (fe, #2, j ) } < 00and we conclude that u) = (z, #i ^2, i ) = max{(z, z\, fe), (fe, ^2, j ) } . If(i, jsi, fe) - u; then sw (yi, zi) £ sw (yi, zi) + (fe, y2, j) ^ (i, yi , fe) +(*, 2/2, j ) = (i, 2/1 2, j ) . Similarly, if (fe, z2) j ) = a; then sw (y2, z2) <(h y\ V2, j ) - Altogether, min {s^ (yi, z\), s^ (y2, z2)} < (i, yi yi, i ) .Thus, min{s w (y i , ^ i ) , s w (y 2 , ^2)} ^ min {(i, yi y2 , j ) | (i, ^l ^2, i ) =a;} = s w ( y i y 2 ï ^1^2). •

LEMMA 5: Lef e G Mn % be idempotent and asuume that Y Ç Mn A4agrées with e. Then, Si ( Y + , e8) < 2 Si (Y, e) and min{sa ,(Y, e), q} <sw(Y<3, e8), for every q > 1.

Proof: Assume that (i, e", j) = 1. Let yi , y 2 î . . . , yq be in Y, for q ^ 1.If g = 1 we have nothing to prove, so assume that q > 2. Now, (i, e ' , j ) = 1implies that (i, e, j ) = 1 and that (i, j ) is anchored in e. Let fc G [1, n]be such that 0 == (fe, e, fe) < (i, e, j) = max{(2> e, fe), (fe, e, j ) } = 1. If(i, e, fe) — 0 then (i, yi , fe) = 0 since yi agrées with e. Thus, (i, yi , fc) <Si (Y, e). Similarly, (fe, y^, j) < Si (Y, e). On the other hand, since eachyr agrées with e, (fe, e, fc) = 0 implies that (fc, y r , fc) = 0 for everyre [1, g]. Thus, (z, y i . . . y 5 , j ) < (z, yi, fc) + (fc, y2,

vol. 28, n° 3-4, 1994

284 i. SIMON

2Si (Y, e). It follows that SiCy+.e*) = max{(i, y, j) \y e Y+ and(i,e*,j) = 1} < 2Si(y,e).

Let now q ^ 1 and assume that (i, e' , j) = cv. Let yi, y2, • • •, Vq € Vand let z = &o, fei, fe2, • • • > fe^ = j in [1, w] be such that (i, y i . . . yq, j) —(feo, 2/1, fei) + • • • + (fe<?-i, yg, fe<?). Since yi--yq agrées with e9 weconclude that 0 < (i, y\-*yq, j) < oo, and, consequently, for each r,(fcr_i, y r , fcr) < ce. Since each yr agrées with e we conclude that for eachr, (À;r_i, e, Av) < a;; hence, max{(fc r_i, e, A;r) | r G [1, q]} ^ a;. Assumeinitially that (fe r-i, e, fer) = a; for some r E [1, q]. Then,

(1) Sa, (Y", e) ^ (fer_i, y r , A;r) < ^ ( f e r _ i , 2/r, fcr) = (i, yi--yq,j)-r = l

Assume now that (fer_i, e, fer) < CJ for every r G [1, q]. From (i, e', j) = u;we conclude that 1 ^ (i, e, j ) . Using Lemma 1 we have:

(2) 1 ^ (ï, e, i ) 1 max{(fcr_i, e, fer) | r G [1, q}} % 1.

Now, we claim that (fer-i, e, fcr) = 1 for every r. Indeed, assume that(fcr-i, e, fcr) = 0 for some r. Then, by Lemma 2, (fcr_i, A;r) is anchoredin e and so is (fco, ^g) = (^ i)* Since (2) implies that (i, e, j ) — 1 itfollows that (i, e', j ) — 1: a contradiction which establishes the claim. Now,since each yT agrées with e we can conclude that 1 ^ (fer-i) î/r, fer) forevery r; hence,

q

( 3 ) g ^ ^ ( f e r _ l , y r , fer) = ( i , y i •••%, j ) .

Since either (1) or (3) holds, it follows that minls^ (y, e), q} <(h yi'" Vq> j)\ hence, min {sw (y, e), q} ^ min {(i, y, j ) | y G y ? and(i, e9, j ) = u} — sw (y^, e'). This concludes the proof of Lemma 5. •

4. BASIC OBJECTS AND THEIR PROPERTIES

In this section we set up the notations and the major définitions neededto prove the main resuit. Let A be a nonempty finite alphabet and letif : A+ —> MnT be a morphism such that Aip Ç MnÀ4. In otherwords, A+ y? is just a finitely generated subsemigroup of Mn M. We shalldénote by A the maximum of the nonnull finite coefficients in Atp, i. e.



A = max {Si (a (p, a (p *) | a G A}. Note that, even though we shall not doit, there is no loss of generality if we assume that A = 1.

Let 5 be the least stable subsemigroup of MnH which contains Aipty.In order to précise a generating set for S we define an alphabet B given by

B = A U {be | e is an unstable idempotent in 5} ,

where the union is disjoint. Let ƒ : B+ —• Mn 1Z be the morphism definedby a f — aipty, for a G A, and be ƒ = e , for every unstable idempotente in S. Clearly, B+ f = S.

Now we defined the principal object used in our proof. A tropicaltree T consists of a rooted plane tree with vertex set V and a labelingA : V —> £ + x S which satisfies:

• no vertex in V has outdegree one;

• every vertex of outdegree 0 has label (6, bf), for some b G B\

• every vertex v of outdegree two has label (x\ X2, z\ 22), where (x\, z\)and (#2, 2:2) are, respectively, the labels of the direct left and rightdescendants of v;

• for every vertex v of outdegree p > 2 the labels of the direct descendantsof v are (ar*, e), for i E [1, p], and the label of v is (#i #2 • • * xP, e"), wheree is some idempotent in 5 which will be called the idempotent of vertex v.The label of the tropical tree T is the label of the root of T.

It will be convenient to classify the vertices of a tropical tree as continuousor discontinuous. Continuity hère will be meant with respect to the product inS. More precisely, we say that vertex v is discontinuous if it has outdegreep > 2 and its idempotent is unstable. A vertex is continuous if it is notdiscontinuous.

Ail paths considered in T will be directed away from the root. A pathc in T is continuous if every internai vertex of c is continuous. Note thatwe allow for discontinuous vertices at the extremities of c. The span of atropical tree T is the length of a longest continuous path in T.

LEMMA 6: Let T be a tropical tree of height h and span s. Let q be thecardinality of a maximum chain of principal ideals generated by unstableidempotents of S. Then, h ^ (1 + q) s < \S\s.

Proof: Let c = (vo, î, • • •, vr) be a continuous path beginning andending on discontinuous vertices VQ and vr. Let vr+i be a descendant of vT\the existence of such a vertex is guaranteed by the descontinuity of vT. Let

vol. 28, n° 3-4, 1994

286 i. SIMON

(XJ, Zi) be the label of vertex v{. Then, z\ and zr+i are unstable idempotentssuch that zo = z\ and zr = zl+i- Since c is continuous, z\ G S1 zr S1. Onthe other hand, from Lemma 3, S1 zr S

1 is properly contained in S1 zr+\ S1,Thus, z\ and zr+\ are unstable idempotents such that S1 z\ S1 C S1 zr+\ S1.

If follows that if c has p unstable vertices then 5 has a chain of p principalideals generated by unstable idempotents. From the définition of span andthe choice of q it follows that h ^ (1 + q) s. Clearly, 1 + q £ \S\ and thiscomplètes the proof. •

A multiplicative rational expression over A is a rational expression whichuses only the opérations of concaténation and star. To such an expressionR we associate a fonction R : N —» A*, where kR is the word obtainedby substituting by k each occurrence of * in R. For example, the wordsassociated to c(ba*)* c are ce, ebac, c(ba2)2 c, c(ba?)3 c...

The connection between tropical trees and multiplicative rationalexpressions is given by the next Lemma. Let T be a tropical tree labeledby (x, z)j with x G A+ and let R be a multiplicative rational expressionover A. We say that R is a witness for T if Oi? = x, NRtp agrées with2, Si (Ni?<^, 2) is finite and, for every k > 0, sw (kR(p) z) ^ fc. We alertthe reader that the définition of a witness, as well as the next Lemma, referexclusively to tropical trees with label in A"*" x 5.

LEMMA 7: For every tropical tree T labeled by (x, z), with x G A~^\ thereexists a multiplicative rational expression R over A which is a witness for Tand such that Si (NR<p, z) ^ 2h A, where h is the height ofT.

Proof: We proceed by induction on the height h of T. If h — 0 then theonly vertex of T is its root and the label of T is (a, af) for some a £ A,Let R — a; since k R = a for every A: and a / — a (p * , we have that

Si(Ni2<p, a/) = Si(a</>, a/) = Si(a<p, a y?*) ^ A.

Assume now that the root v of T has outdegree 2 and that the tropicaltrees associated to the direct descendants of v are T{ with label (x^, 2j), fori = 1, 2. Then, the label of T is (x, 2), with x — x\X2 and z = 21 22- By theinduction hypothesis T{ has witness Ri such that Si (N Ri tp, z%) ^ 2h-1 A.We claim that the multiplicative rational expression R = R\ R2 satisfiesthe Lemma for T. Indeed, 0 # = (ORi) (0R2) = xi x2 = x. Also,agrées with 21 22 = 2 . Now, for each k ^ 0, we have, by Lemma 4,

Si (fc J ïp , z) = Si ((fc#1 y?) (kR2 if), zi z2)



Hence,

Si (NRip, z) = max{Si (kR<p, z) \ k G N}

< max {Si (kRi cp, z\)

^ m a x { S i (kRnp, zi)\k G N }

+ m a x { S i ( A ; i Î 2 0, using Lemma 4 and the induction hypothesis wehave that

s^ (kR(p, z) = sw ((A;.Ri <p) {kR2 y?), ^1 2)

^ min{sw (fcJîi (/?, zi), s^ (fc i?2 ¥?, ^2)} ^ fe.

This concludes the proof when the root of T has outdegree 2.

Assume finally that the root v of T has outdegree p > 2. LetTi, T2 , . . . , Tp be the tropical trees associated to the direct descendants of v\let e = e2 E MnU and x% E A+ be such that (x*, e) is the label of T{. Then,x = x\x2---xp and z — e", where (x, z) is the label of T. By the inductionhypothesis Ti has a witness i?; such that Si (N Ri <p, e) ^ 2h~1 A, We claimthat R\ — - Rp (Ri * • • Rp)* satisfies the Lemma for T. Initially we note thatOR = 0i?i*--0iîp = xix2' — xp = x. Also, for every k > 0, kRipagrées with z. Indeed, kR •-kRp)

k)<p; hence,since kRqtp agrées with e and e = e2 we have that k R tp agrées with e.

pThen fc R(f agrées with z = e", since e 7r = e' ir. Let now Y = (J NRq<p.

Then y agrées with e and, for every k 0, kR 0. Let y = {kRq(p\q G [l ,p]} . Again,y agrées with e and for every k > 0, kRy> G Yp+kp, since

k R k R ( k - -kRp)k\ thus, s^ (feiï<p, e») ^ s (P+*P ö)

vol. 28, n° 3-4, 1994

288 i. SIMON

Also, since $u(kRq(p, e) > k, for every q, we have that s^ (Y, e) =min {sw (y, e) \ y G Y} > fe. Thus, by Lemma 5,

sw (fcfl y», e») ^ sw (y*+**, e») > min {sw (y, e), p + fcp}

^ min {&, p + fcp} = fc,

since p > 3. This concludes the proof of Lemma 7. •We close this section with a simple property.

LEMMA 8: If a tropical tree is labeled by (x, z) then xf -K — zir.

Proof: This is proved by a straighforward induction on the height ofthe tree, after observing that ƒ and -K are morphisms and that for everyidempotent e G Mn 7Z, en = e$ TT, since 1 TT = un = 1. •

5. CONSTRUCTION OF TROPICAL TREES

In this section we construct tropical trees needed to show the main resuit.We shall need some définitions and results from [8]. For an alphabet A

we dénote the free semigroup generated by A either by A+, as usual, orby A J7. In the second notation, the éléments of A T will be represented as(ai, a 2 , . . . , ap), where a% G A.

A factorïzation forest F = (X, d) over A consists of a subset Xof A+ together with a function d : X —> T X such that, for everyx G X, xd = (xi, #2) . . . , Xp) implies that x = xi X2 • • • ^p', i. e. xd isa factorization of x whose factors belong to X. The external set of F isthe set {x e X\ \xd\ = 1}.

Given F we associate to each x G X a rooted ordered plane tree a;Fwhose vertices are labeled by éléments of X. If \xd\ = 1 then x F consistsjust of the root labeled x. If xd = (xi, X2,.. . , xp), with p > 1, then theroot of x F has outdegree p and a copy of x% F is associated to the i-thdirect descendant of the root. This allows us to speak of the outdegree ofvertices of x F, and of paths in x F . The height of x F is denoted xh andthe height of F is h = sup{x/i |x G X}.

Let ƒ : B+ —> S be a semigroup morphism, with 5 finite. Factorizationforest F is Ramseyan mod ƒ if for every x of outdegree p > 3,xrf = (xi, X2,. . . , xp) implies that there exists an idempotent e G S suchthat e = x ƒ — xi ƒ = • • * = xp ƒ. We say that ƒ admits a Ramseyanfactorization forest if there exists a factorization forest F = ( S + , d) over JBwith external set B which is Ramseyan mod ƒ.



We recall the main resuit of [8].

THEOREM 9: Every morphism ƒ : B+ —• S, from a f ree semigroup to afinite one, admits a Ramseyan facîorization forest ofheight at most 9 |5 | .

In what follows we consider the data defined in Section 4 and fix afactorization forest F — ( 5 + , d) with the properties asserted by Theorem 9.We call H the height of F and note, for future use that

H<9\S\.

The following Lemma is the main resuit of this section.

LEMMA 10: For every x G B+ there exists a tropical tree of span at mostH labeled by (x, z), for some z G S.

Proof: Based on the factorization forest F , Ramseyan mod ƒ, we defineP Ç B+ as follows. Let P be the least subset of J3+ which satisfies thefollowing properties:

• B is contained in P;

• if x G £+ , xd^PT and \xd\ = 2 then x G P ;

• if a; G B+, xd G P J7, |xd| > 2 and x ƒ is stable then x G P .

The set P enjoys the following properties.

ASSERTION 1: For every x E P there exists a tropical tree ofheight at mostH labeled by (x, xf) whose vertices are ail continuons,

Proof: Using the factorization forest F we have associated a tree x F tox. Vertices of this tree are labeled by certain factors of x\ since x e P, thedéfinition of P implies that all these labels belong to P . Let f be a vertexof the tree x F and let y G B+ be its label. We extend the labeling of v to(y, yf). Note that, F being Ramseyan mod ƒ, x G P implies that wheneverthe outdegree of v is at least 3 the matrix y f is a stable idempotent Thus,the tree xF becomes a tropical tree of label (x, xf) with no discontinuousvertices. This tree has height at most H which is the height of P . •

ASSERTION 2: Let x G 5 + \ P be such that xd G P T. There exists atropical tree ofheight at most H labeled by (x, xft) whose root is its uniquediscontinuous vertex.

Proof: The hypothesis imply that \xd\ > 2, and that xf is an unstableidempotent. We proceed exactly as in Assertion 1 with the exception thatwe substitute the label of the root by (x, xfl), which is necessary now toget a tropical tree. •

vol. 28, n° 3-4, 1994

290 I. SIMON

ASSERTION 3: Every x E B+\P has a factorization x — yxfyf such thatxl E 5 + \ P and x'd e P T.

Proof: Let x1 be a shortest segment of x which is not in P; then, x = yxfyf

for appropriate y, y1 E I?*. Let x'd = {x\,..., xp). Note that the choice ofx1 guarantees that every proper nonempty segment of x1 is in P; in particular,x'fd E P T. From the définition of P we conclude that \x'\ > 1. I

The construction of our tropical trees will be done by a séquence ofsubstitutions. One instance of this opération is given by the foliowingAssertion.

ASSERTION 4: Let x — yby', with b E B\A and y, y1 E B*. Let T\ be atropical tree with label (x, z) and span s\. Let T<i be a tropical tree withlabel (z', bf) and span S2 whose root is discontinuons. Then there exists atropical tree T with label (yxfyf, z) and span s = max{si, $2}-

Proof: Let v\ be the (external) vertex of tree T\ whose label is (&> bf)and which corresponds to the factorization ybyf of x. Tree T is constructedby substituting vertex v\ in T\ by the tree T2. We maintain the labeling ofthe vertices in T2. As for Ti, we consider the path in T\ from the root tovi. Vertices of T\ not on this path maintain their labels . Let (a?j, zf) bethe label in T\ of vertex v% on this path. The vertex î, which lies on thetree with root v*, détermines a factorization yiby\ of x%. The label of v% inT will be (y,V^, Zi).

Noting that the lebel of T2 is (rr', bf), the reader will verify withoutdifficulty that T is a tropical tree with label (yxfy\ z). Since the root of T%is discontinuous, the span of T is the maximum of the spans of T\ and T2.This complètes the proof of the Assertion. •

We are ready to prove Lemma 10 by induction on \x\. For x E P thetropical tree given by Assertion 1 satisfies the Lemma with z — xf. Letthen x E B+\P and let us apply Assertion 3. Since xf E B + \ P butxfd E P T the définition of P implies that \x*d\ > 2 and that x1 f is anunstable idempotent. Let e = x' f and let b be the letter in B\A for whichbf = eK By the induction hypothesis there exists a tropical tree T\ withlabel (ybyf, z)9 for some 2 E 5, with span 51 at most H. By Assertion 2there exists a tropical tree T2 with label (x', e') and height (hence span52) at most H whose root is discontinuous. The tropical tree T given byAssertion 4 has label (yxfyf, z) = (ar, ) and span 5 = max {s\, 52} iï".This complètes the proof. •



LEMMA 11: For every z E S there exisîs an x E A+ and a tropical treelabeled by (x, z).

Proof: Initially we need a closer look at the génération of S, LetBo = A. Given Bk Ç B, k > 0, let S* = (£*ƒ)+. Given Sk, k ^ 0,let Bk+i = A U {be\e = e2 e Sk and e ^ e0}. By construction,#A; Q Bk+\ Ç S, and £& Ç Sfc+1 Ç 5. Since S is finite, there existsl ^ |S|, such that 5/ = S/+1 C 5. Since S is the least stable subsemigroupof Mn H which contains A, we conclude that Si = S and Bi+\ — B.

Now, for every z e S there exists a least k such that z e Sk. Weshall proceed by induction on such a fc. Initially we observe that forz E BQ ƒ = A ƒ we have a E A such that af — z\ hence it is sufficient toconsider the one vertex tropical tree with label (a, af).

Consider now k > 0 and assume that for every z E Bk ƒ there existsa tropical tree Tz labeled by (xz, z), with xz E A+. Let z E Sfc. Byconstruction, there exists y E JB j" such that y f = z. Our tropical tree isobtained by induction on \y\ by repeating the following construction. LetTi be a tropical tree labeled by (XÎ, z%)9 with Xi E A+ and Zi e Sk, fori = 1, 2. Let T be the tree whose root has outdegree two and T\ and T<i arethe tropical trees of the direct left and right descendants of the root. Thenthe label of T is (xi X2, z\ z<i).

Finally, assume that for every z E S& we have a tropical tree Tz labeledby (xZl z), with xz E A+. We claim that the same is true for z E Bk+i ƒ.Indeed, if z E Bk f the claim follows at once from the induction hypothesis;otherwise there exists e — e2 E Sk such that 6e ƒ = e = ^. By theinduction hypothesis, there exists a tropical tree Te labeled by (xe, e) forsome xe E A+. Consider now the tree whose root has outdegree three andevery one of the direct descendants of the root have tropical trees identicalto Te. Then, T is a tropical tree labeled by (xg, e ) and consequently itjustifies our claim. This concludes the proof of Lemma 11. •

6. MAIN RESULT

In order to précise our problem we need some définitions. Let X C Mn K,for some semiring K. For I E Klxn and J E Knxl the (J, J)-section ofX is the subset of K given by {I x J \ x E X} . The case when I and Jhave exactly one coefficient which is 1% ail others being 0K is particularlyinteresting. In this case, assuming that the nonnull coefficients are (1, I, i)and (j, J, 1), the (ƒ, J)-section of X is the set of all coefficients of matricesin X in row i and column j \ this set is usually called the (i, j)-section of X.

vol. 28, n° 3-4, 1994

292 i. SIMON

Next we prove the main theorem which we announced in [9]. Note thatthe équivalence of (i) and (iii) has been proved by K. Hashiguchi in [3] andthe équivalence of (i) and (ii) has been proved by H. Leung in [5]. All theseproofs were obtained pairwise independently but our présentation certainlywas influenced by the work of both K. Hashiguchi and H. Leung.

THEOREM 12: Let tp : A+ —> Mn M be a morphism with A finite; letS be the least stable subsemigroup of Mn 1Z which contains A ;

(iii) there exists a multiplicative rational expression R over A such that,for every k > 0, k < I(kRtp) J < oo.

Proof: (i) implies (ii). Assume, for a contradiction, that the (I, J)-sectionof S does not contain ou. Let Z Ç M be the (/, J)-section of A+ ip.Let F be a factorization forest with the properties asserted in Theorem 9;let H be the height of F. Let q be the cardinality of a maximum chain ofprincipal ideals generated by unstable idempotents of S. Let u = 2(1 +^ H A,where A = max{Si (aip, acp^)\a e A}. Then, H £ 9|5| , q < \S\ andu < 29I5I2 A. We shall show that Z Ç [0, u] U {oo}. This implies that Zis finite, a contradiction that establishes the resuit.

To see the claim, let x G A+ . By Lemma 10 there exist a tropical treeT of span at most H labeled by (a;, z), for some z G S, By Lemma 6 theheight h of T satisfies h ^ (1 + q) H. By Lemma 7 T has a witness R suchthat Si (NRipy z) ^ uf since 2h A < 2^^)H A = u.

Let m = I (x (p) J . If m G {0, oo} then we have nothing to prove,otherwise, 0 < m < oo. Taking projections by $?r we have thatm * 7T = 7 (xfn) J = 1, since I = Iîr, J = J^n and, x belonging toA + , x (p * = xf. By Lemma 8, J (z TT) J = 1. Now, from the définition of 7r,Iz J G {1, u;}; the assumption that the (ƒ, J)-section of S does not containu) implies that I z J = 1. Hence, there exist i, j G [1, n] such that (1, 7, i) =0 = (j, J, 1) and (ï, 2, j ) = 1. Now, # being a witness for T, we have thatOR = x\ hence, from Si (NRcp, z) < u we conclude that (i, xip, j) ^ u.Consequently, m — I (x <p) J < (1, / , i) + (i, x <p} j) + (j, J, 1) < u andthis proves the claim.

(ii) implies (iii). Let z G 5 be such that / z J = u;. By Lemma 11 thereexists an a: G A+ and a tropical tree T labeled by (x, z). By Lemma 7



T has a witness R. Let us fix k > 0 and let m = I (k R ip) J. SincekRip e MnM, since it agrées with z and since Iz J = a>, we concludethat 0 < m < (jj < oo.

Since m = I(kRip) J, there exist i, j G [1, n] such that (1, J, i) = 0 =(j, J, 1) and (i, kRip, j) = m. Since fciîy? agrées with z and / 2 J = UJ itfollows that (z, 2, jf) = a;. Thus, since R is a witness for T we have thatk ^ Soj^kRip, z) ^ (i, kR<p, j) — m. Altogether, k ^ / (k R ip) J < 00,as required.

(iii) implies (i). This is clear. H

Since Mn TZ is a finite semigroup it follows that S is effectivelycomputable. Hence, a direct conséquence of Theorem 12 is a resuit provedby K. Hashiguchi in [2],

COROLLARY 13: It is decidable whether or not a given section of afinitelygenerated subsemigroup of Mn M, is finite,

The following resuit, proved in [6], is also easily deduced fromTheorem 12.

COROLLARY 14: Let (p : A*~ —* Mn Ai be a morphism with A finite. ThenA+ ip is finite if and only if every idempotent in A+ ip * is stable.

ACKNOWLEDGEMENTS

This work was done all over the world mainly between the years 1986 and 1989 during whichperiod many people helped me in one way or another. But it certainly would not exist if it were notfor the hospitality and enthusiasm of Christian Choffrut, Dominique Perrin and Jacques Sakarovitch.

REFERENCES

1. S. EILENBERG, Automata, Languages, and Machines, Volume A, Academie Press, NewYork, 1974.

2. K. HASHIGUCHI, Limitedness theorem on finite automata with distance functions,X Comput Syst. Sel, 1982, 24, pp. 233-244.

3. K. HASHIGUCHI, Improved limitedness theorems on finite automata with distancefunctions, Theoretical Comput Sri., 1990, 72.

4. H. LEUNG, An Algebraic Method for Solving Décision Problems in Finite AutomataTheory, PhD thesis, Department of Computer Science, The Pennsylvania StateUniversity, 1987.

5. H. LEUNG, On the topological structure of a finitely generated semigroup of matrices,Semigroup Forum, 1988, 57, pp. 273-287.

vol. 28, n° 3-4, 1994

294 i. SIMON

6. I. SIMON, Limited subsets of a free monoid, In Proc. 19th Annual Symposium onFoundations of Computer Science, Piscataway, N. J., 1978, Institute of Electrical andElectronics Engineers, pp. 143-150.

7. I. SIMON, Recognizable sets with multiplicities in the tropical semiring. In M. P. Chytil,L. Janiga, and V. Koubek, Eds., Mathematical Foundations of Computer Science,Berlin, 1988. Springer-Verlag, Lectures Notes in Computer Science, 324, pp. 107-120.

8. I. SIMON, Factorization forests of finite height, Theoretical Comput ScL, 1990, 72,pp. 65-94.

9. I. SIMON, The nondeterministic complexity of a finite automaton, In M. Lothaire, Ed,Mots - mélanges offerts à M. P. Schu'tzenberger, Hermès, Paris, 1990, pp. 384-400.

Documents

INFORMATIQUE THÉORIQUE ET APPLICATIONSarchive.numdam.org/article/ITA_1994__28_3-4_277_0.pdf · 278 i. SIMON In 1987 H. Leung [4, 5] published an algorithm to décide the same problem