Acta Informatica 11,233 - 240 (1979)

mrmaaCa �9 by Springer-Verlag 1979

Intersections de langages alg briques born s

Michel Latteux

Universit6 de Lille I, U.E.R.I.E.E.A., Service Informatique, Bgtt. M3-B.P. 36 F-59650 Villeneuve d'Ascq, France

Intersections of Bounded Algebraic Languages

Summary. We study the family SLB of morphic images of the intersection of two bounded Context-free languages. In particular, we prove the equality between this family and the family of finite intersection of bounded Context- free languages.

Introduction

Une propri6t6 importante des langages alg6briques est la propri6t6 de semi- lin6arit6; c'est-/t-dire que pour tout langage alg6brique L d6fini sur un alphabet T, l'image de L par la fonction de Parikh (homomorphisme canonique de T* dans le monoide commutatif libre engendr6 par T) est un ensemble semilin6aire. Nous dirons, alors, que L est un PSL-langage (en anglais, slip-language). Cepen- dant, cette propri6t6 ne caract6rise pas les langages alg6briques et d'autres c6nes rationnels ne contiennent que des PSL-langages (voir par exemple [71 [-9]) et on peut 6tendre it ces families certains rdsultats d6j/t obtenus pour les langages alg6briques. Les langages born6s (inclus dans w* ... w*, off Wl, ..., w, sont des mots quelconques) ont fait l'objet de nombreuses 6tudes et sont d'un grand int6r6t en th6orie des langages. Dans le cas o~ les mots w 1 . . . . . w, sont, en fait, des lettres routes distinctes, l'6tude de L_~w* ... w* se r6duit /t l'6tude de son image par la fonction de Parikh. Par contre, dans le cas g6n6ral, il se pose un

�9 i n probl6me de codage, puisque la fonction fw ddfinie sur N" par fw( i l . . . . , i,) = w] ' . . , w , n'est pas n6cessairement injective. En particulier, il existe des PSL-langages born6s qui sont rationnellement 6quivalent ~ des langages qui ne v6rifient pas la propridt6 de semilin6arit6 (cf. [8]). Nous allons nous int6resser, dans ce papier, aux langages born6s L appartenant / tun PSL-c6ne rationnel et qui sont carac- t6ris6s par le fair que pour toute application s6quentielle g, g-I(L) est un PSL- langage [-8]: Ces langages appartiennent /t la famille S L B = { f ~ , ( S ) / w est un n-uple de mots et S est un semilindaire inclus dans N"} que nous montrons identique/t la plus petite famille de langages contenant les langages alg6briques born6s et close par intersection, identique, aussi, ~ la famille des images homo- morphes de l'intersection de deux langages alg6briques born6s.

0001-5903/79/0011/0233/$01.60

234 M. Latteux

I. D~finitions

Soit N, l 'ensemble des entiers naturels. Pour tout n e N , N" est 6gal ~ {(i~ . . . . , i,)/ i jeN, Vje {1 . . . . . n}}. Un sous-ensemble S de N" est linkaire s'il existe, v0, Vl, ..., vpeN" tels que S = { v o + k a v l + . . . + k p v S k i e N , Vie{1 . . . . . p}}, ensemble que nous noterons L(v0; {v I . . . . . %}). Cet ensemble est un linkaire stratifiO si l 'ensemble des p6riodes P = { v I . . . . . vfl vdrifie les deux conditions suivantes:

i) Chaque 616ment de P a au plus deux coordonndes non nulles. ii) I1 n'existe pas d'entiers i, j, k, m, tels que l < i < j < k < m < n et tels que

(x 1 . . . . . Xn) , ( X ' 1 . . . . . X'n) soient dans P avec x i xj x k x'~:O. Un semilinOaire (stratifiO) de N" est une union finie de lin6aires (stratifi6s)

inclus dans N". Soit T = {a 1 . . . . . a,}, un alphabet ordonn6. La fonction de Parikh, ~ de T*

dans N" est d6finie par 0(x)=(u~ . . . . . u,) o6 Vie {1 . . . . . n}, u iest 6gal au nombre d 'occurrences de la lettre ai dans le mot xe T*.

Un h o m o m o r p h i s m e h de T* dans T'* est alphabOtique, continu, strictement alphab~tique si h(T) est inclus respectivement, dans T ' w {1} (1 d6signe le mot vide), T'*\{1}, T'. Une famille de langages L est un c6ne rationnel (fidOle) si elle est close par homomorph i sme inverse, intersection avec les langages ration- nels et h o m o m o r p h i s m e (continu).

Une machine sOquentielle est un 6-uple G = (K, X, A, 6, 2, qo) off K est l 'ensemble fini non vide des 6tats, Z et A sont des alphabets, 6 et 2 sont des fonctions de K x Z dans respectivement K et A*, q 0 e K est l'6tat initial. Les fonctions 3 et 2 sont 6tendues par induction/~ K x Z* en ddfinissant pour tout q e K, x e Z*, y e 2;:

a) cS(q, 1 ) = q et 2(q, 1 ) = l . b) 6(q, x y) = 6(6(q, x), y) et 2(q, x y) = 2(q, x) 2(3(q, x), y). La fonction g ddfinie par g(x)=2(qo,X ) est une application sOquentielle et

g-~ ddfinie par g - l ( L ) = { x / g ( x ) e L } , VL~_A* est une application sOquentielle inverse.

Pour tout n-uple de mots w = ( w l , ..., w,), fw est une application qui est d6finie sur N ~ par:

�9 i n fw(il . . . . . i,)=w~ ~ ... w, .

Enfin, la famille SLB d6signera l 'ensemble {fw(S)/w est un n-uple de mots et S_~N" est un semilin6aire}.

II. R~suitats

Mont rons d ' abord que tout langage L inclus dans w* ... w*, tel que fwl(L)= {(il ' ... , ~,)/wl. i , . . . w~e L} est un semilin6aire, est une intersection finie de langages alg6briques. Dans le cas off wl, ..., w, sont des lettres toutes distinctes, ce rdsultat d6coule imm6diatement des deux proposi t ions suivantes:

Proposition 1 [5]. Soient L_c wa* ... w n* et w le n-uple (w~ . . . . . w,). Le langage L est algdbrique si et seulement si fw ~(L) est un semilin6aire stratifi6.

Intersections de langages alg6briques born6s 235

Proposit ion 2 [10]. Tou t ensemble semilin6aire est une intersect ion finie de semi- lin6aires stratifi6s.

Dans le cas off wl, . . . , w, sont des mots quelconques que l 'on peut toujours supposer diff6rents du m o t vide, nous util iserons une autre propri6t6, qui n 'est qu 'un cas part iculier du th6or6me de cross-section [4].

L e m m e 3 [5]. Soient un a lphabet A = {al, . . . , a,} et un h o m o m o r p h i s m e h d6fini sur A par h(ai)=wi, ViE{l , . . . . ,n}. I1 existe un langage rat ionnel Rca~* ... a,* qui est en bijection par h avec w* ... w,.

Nous pouvons alors 6tablir:

c * * tel que f~7 ~(L) est un semilin6aire. Alors L e s t une L e m m e 4. Soit L _ w 1 ... w, intersection finie de langages alg6briques.

Dkmonstration. D'apr6s la p ropos i t i on2 , il existe des semilin6aires stratifi6s P

S 1, . . . ,Sp, tels que S=f~X(L)= ~ S i. Consid6rons l ' a lphabet A={al , . . . ,a,}. i = l

L'appl ica t ion f , d6finie sur N" par fa(i~ . . . . . i,)=a]l...a~ 6tablit une bijection

entre N" et a* ... a*. D o n c f , ( S ) = f , Si = ~fa(Si) off, Vie{ l , . . . ,p} , fo(Si) i / i = 1

est un langage alg6briqu e [5]. Consid6rons le langage rat ionnel R et l ' homo- m o r p h i s m e h d6finis au l emme 3. Posons, pour tout iE {1, . . . , p}, E'i=f ,(Si)nR. C o m m e f~(S)=h-l(L)c~a * ... a* et que R ~ * * h- l (L)c~R _ a 1 ... a , , nous avons =

P

f , (S)c~R= (~ E' i. L'inclusion de L dans h(R)=w* ... w* implique L = L n h ( R ) = i = 1

h ( h - i ( L ) n R ) et c o m m e h est injectif sur R qui contient E'i, Vie{1 . . . . ,p}, nous

en d~duisons que L = h = ~ h(L'~) est une intersection finie de langages alg6briques. [ ] , i = 1 ; i = 1

Pour tout langage L~_w 1. ... w,,* si fw l (L ) est un semilin6aire L=fw(f(~-l(L)) appar t ien t ~t la classe SLB. Par contre, on a pas en g6n6ral l'6galit6 entre S e t f ~ 1 (fw(S)) pour tout S _c N". Cependant , mon t rons :

L e m m e 5. Pour tout semilin6aire S _ N" et tout n-uple de mots w = (w~ . . . . . w,) , fwl(f~,(S)) est un semilin6aire.

Ddmonstration. Pour tout semilin6aire S_cN", il existe un langage rat ionnel Rc_{al, ..., a,}* tel que 0 ( R ) = S ( O est la fonct ion de Parikh). La cl6ture com- muta t ive de R, c(R)=O-~(O(R)) appar t ien t ~t L~,, le plus petit c6ne rat ionnel c o m m u t a t i v e m e n t clos qui ne cont ient que des PSL-langages ([7], [9]).

Consid6rons l ' h o m o m o r p h i s m e h d6fini par: h(ai)=w~, Vie{1 . . . . . n}. Les langages L = f w ( S ) = h ( c ( R ) n a ~ ... a*) et L ' = h - l ( L ) ~ a * ... a* appar t i ennen t ii L o. Doric f~ i ( fw(S))=f ,~l (L)=O(L' ) est un semilin6aire. [ ]

Pour toute famille de langages L, H(L) d6signera la plus peti te famille de langages, con tenan t L e t close par h o m o m o r p h i s m e .

Pour tout entier posit if i, nous noterons"

ABe= {L~ c~ ... c~ LJVse {1, . . . , i}, L~ est un langage alg6brique born6}.

236 M. Latteux

Liu et Weiner ont d6montr6 [11] que, pour tout entier k > 2 , le langage L k = { W W / w c a T . . . a * } appart ient ~ ABk\ABk_I , d'ot~ la hi6rarchie infinie ABI ~ AB2 ~ . .. ~ ABk -1 �9 ABk ~ . . . . Nous allons 6tablir que A B 1 = H (AB1) H(AB2) = H(AB3) . . . . . Mont rons d ' abord :

Lemme 6. Soient S u n semilin6aire de ]hi" et w = (w 1 . . . . . w,) un n-uple de mots. Alors fw ( S) = { w~ 1 ... w~ /( il , . . . , i,)~ S} appart ient ~ H ( A B 2) , la famille des images homomorphes de l ' intersection de deux langages alg6briques born6s.

D~monstration. C o m m e ABe, la famille des langages alg6briques born6s est close par union. H(ABz) est aussi clos par union. On peut, donc, supposer que S est un ensemble lin6aire 6gal ~ L(uo; {ul, ..., Uk} ). On supposera, de plus, que n e s t pair (n=2t ) . Consid~rons, alors, les langages alg6briques born6s L={wv~R/ w e b a * ... a~} (~R d6signe l ' image miroir de w off chaque lettre est remplac6e par la lettre barr6e) et L' = {w ~R/w~a* ... a k b} et pour i~ {1 . . . . . t } , j~ {1 . . . . , t - 1}, d6finissons les homomorph i smes gi et hj par:

g~(b)=b2i_~, gi(f))=b2i, hj(b)=b2j, hj(b)=b2j+l et Vse{1 . . . . . k},

gi(as)=as, z i -1, gi(a,) =a~, 2i, hj(a~)=a~, 22, hj(a~)=a~, 2j+1. t - - * Les langages L~ = g~ (L) ... gt (L) et L 2 = g~ (b a* . . . a*) h I (E) ... hi_ ~ (L) gk (ak "" ~* [;)

sont des langages alg6briques born6s dont l 'intersection est 6gale/t {g~(w #R)... gt (w #R)/We b a* ... a* }.

Consid6rons, maintenant , l ' homomorph i sme h ddfini par: Vie{1 . . . . . n}, Vje {1 . . . . . k}, h(bi)= w~' off r i est la i6me composante du vecteur u 0 et h(aj. i)= w~ ''~ off r~, j e s t la i6me composante du vecteur uj. I1 est, alors, clair que fw (S)= h (L 1 c~ L2) et donc fw(S) appartient/~ H(AB2). []

* Si L e s t une intersection finie Prenons maintenant L inclus dans w~' ... w,. P

de langages alg6briques L 1 . . . . , Lp, f w l ( L ) = O f w X ( L i ~ w * ... w*). D'apr6s la i = 1

proposi t ion 1, Vie{1 . . . . . p}, fwX(Lic~w * ... w*) est un semilin6aire et comme la classe des semilin6aires est close par intersection, S = fw ~ (L) est un semilin6aire. Pour tout homomorph i sme g, g ( L ) = g ( f w ( S ) ) = f y ( S ) avec y = ( g ( w 0 . . . . , g(w,)) ,

... * et h l'homo- appartient ~ la famille SLB. Consid6rons, maintenant L' _~ w* w, morphisme d6fini sur A = {a 1 . . . . . a,} par h(ai)= wi, V ie {1 . . . . . n}. Si L' appart ient

un c6ne rationnel qui ne contient que des PSL-langages, L " = h - l ( L ') c~ a*. . . a* est un PSL-langage et S' =O(L") est un semilindaire, donc E =fw(S') appartient

SLB. Enfin, comme AB 1 est clos par homomorphisme, il est facile de v6rifier que tout langage de H(AB2) est l ' image h o m o m o r p h e alphab6tique de l'inter- section de deux langages alg6briques bornds. Des lemmes 4, 5, et 6, nous pouvons alors d6duire une caract6risation multiple de la famille SLB:

Proposition 7. Soient w = (w 1 . . . . . w,) un n-uple de mots et un langage L ~ w* ... w*. Les propri6t6s suivantes sont 6quivalentes:

i) f ,~ l (L) est un semilin6aire, ii) I1 existe un semilin6aire S tel que L=fw(S ) ,

Intersections de langages alg6briques born6s 237

iii) L e s t une intersection finie de langages alg6briques, iv) Les t l'image homomorphe (alphab6tique) de l'intersection de deux langages

alg6briques born6s, v) L appartient/ t un PSL-c6ne rationnel.

Terminons en mentionnant deux questions, concernant la famille SLB, que nous discuterons ensuite bri6vement.

1. Tout langage de SLB est-il l'image de l'intersection de deux langages alg6briques born6s par un homomorphisme strictement alphab6tique?

2. Tout langage de SLB appartient-il g la plus petite famille contenant les ' langages algdbriques born6s d6terministes, close par union et intersection?

Montrons, d'abord, deux propri6t6s en rapport avec la premi6re question:

Proposition 8. Tout langage de SLB est l'image par un homomorphisme stricte- merit alphab&ique de l'intersection de trois langages lin6aires.

DOmonstration. D'apr6s le r6sultat de Book, Nivat et Paterson [1], il suffit de montrer que SLB est inclus dans BNP, le plus petit c6ne rationnel fid61e clos par intersection et contenant les langages lin6aires. La famille BNP est close par intersection, donc close par insertion, produit et union. Comme le langage C a = {a" b"/n > 0} est lin6aire, la famille BNP est translatable (Le BNP implique ( L ) = {a" w b"/n > O, w e L} ~ BNP).

Donc BNP contient ABi , la famille des langages alg6briques born6s, qui est la plus petite famille de langages close par homomorphisme, union, produit, translation et contenant les langages finis [5]. D'apr6s la proposition pr6c6dente, tout langage de SLB est une intersection finie de langages de A B t et comme BNP est clos par intersection, nous en d6duisons l'inclusion de SLB dans BNP. []

Remarquons qu'il n'est pas connu, pour l'instant, si dans la proposition pr6c~dente deux langages lin6aires suffisent et si, d'autre part, on peut remplacer ~ lin6aires >> par ~( alg6briques born6s >>.

Consid6rons, maintenant, le langage L k = { W w/wea* ... at} avec k___>2. Il est connu que L k E A B k / A B k _ 1 [11]. Par contre, en utilisant la technique employ6e dans la d6monstration du lemme 2.2 de [1], on peut montrer:

Proposition9. Pour tout entier positif k, le langage L k = { W W / W ~ a * ... a~} est 1'image par un homomorphisme strictement alphab6tique de l'intersection de deux langages alg6briques born6s.

D#monstration. Consid6rons les alphabets A = {al, . . . , ak} , d = A x A et les pro- jections rq, ~2 d6finies sur A par: Vi, j e { 1 . . . . . k}, ~zi(ai,aj)=ai, 7z2(al,aj)=a j. Le langage rationnel B = rq- 1 (a* ... a*) n n 21 (a* ... a*) est inclus dans (a l, ak)*... (al, al)* (a2, ak)* ... (ak, al)*, donc c'est un langage bo rne D'autre part, il est clair que le langage L' i ={zeA*/rq(z )=lr2(zR)} est un langage lin6aire et L I = (E 1 ~ B) a* ... a~' est un langage lin6aire born6. De m~me L 2 = {z rc 2 (zR)/zeB} est un langage lin6aire born6. Tout 616ment de L ic~L 2 est de la forme z zci(z ) avec zeA* . R6ciproquement, pour tout wea* ... a~, ~z(l(w)~Tz2a(w R) est une partie non vide de B, donc il existe z e B tel que 7rl(Z)=W=rt2(zR).

2 3 8 M . L a t t e u x

On en dhduit que L k = { w w / w e a ~ ... a~}=Tc'l(La~L2) off To' 1 est l'identit6 sur A et est 6gal/t ~z I sur A. []

Revenons, maintenant/ t la deuxihme question, en remarquant que les langages L a et L 2 construits dans la d6monstration du lemme 6 sont des langages dd- terministes. On en ddduit facilement que tout langage de SLB est l 'image par un homomorphisme alphabhtique de l'intersection de deux langages alghbriques born6s d6terministes. Par contre, tout langage de SLB ne peut pas 6tre obtenu comme intersection finie de langages alghbriques bornhs ddterministes. En effet, considhrons le langage L = {a" b v cq/n =t=p off n +q}.

v Si L = ~ L i off L 1, . . . , Lp sont des langages alghbriques dhterministes, L, le

i I p

compldmentaire de L, 6gal fi U Li est donc encore un langage algdbrique, ce i - - 1

qui est impossible car L c~ a* b* c* = {a" b" c"/n > 0}. On peut remarquer, aussi, qu'il existe des langages alg4briques non born6s

n 'appar tenant pas / t la cl6ture boolhenne de la famille des langages alghbriques ddterministes. En effet Cole a montr6 [-2] que, pour tout alphabet T contenant au moins deux lettres, le langage alghbrique L = T * { y e T 3 T * / y = y R} n'ap- partenait pas ~t la famille des langages reconnus par tableaux it6ratifs d 'automates d'6tat fini. Or, cette famille est close pour les op4rations boolhennes [-2] et contient les langages alg4briques ddterministes [-3]. Rdcemment, Wotschke a d6montr6 ce rhsultat par une autre m6thode (cf. [,12]).

Terminons en examinant les langages de SLB inclus dans w* w~. Nous allons, ainsi, apporter une r6ponse partielle/t la deuxihme question. Montrons, d 'abord:

L e m m e 10. Soi t c * L _ a 1 a* un langage de la famille SLB. Si 7~(L)=L(uo; {(Pl, ql), (P2, q2)}) avec Pl P2 ql q2 =0, L e s t un langage d6terministe.

D~monstration. Si Plql + P 2 q z - -0 , L e s t un langage rationnel. On peut, donc, supposer que Pt ql > 0 et P2 q2 = 0. Si P2 + q2 = 0, il est clair que L est un langage d6terministe. Si q2>0, L est 6gal "5. U(a~2) * avec $ ( E ) = L ( u o ; {(Pl,q0}). Donc E est un langage d6terministe, ainsi que L - E t a q2~* qui est le produit d'un langage d6terministe par un langage rationnel [-6]. I1 reste donc ~t examiner le cas off q2=0 et p l p z q l > O . Le langage C l = { a " b " / n > O } est d6terministe, donc Ll=L/(aqzg*={w/~ y=~"=taqa*2J , w y e L } est aussi ddterministe [6] ainsi que L2--~--"r a;~m/~.2 / , /~e N} qui est 6gal ~t L 1 ~ a* (a~9*. I1 est facile de construire une application shquentielle g qui vhrifie: Vn, 2eN, g(a l"l+"a2r2+~pa)-ala2- n .~p, 0171 (r 1 r z ) = U o. Donc, pour tout 2 , # e N , g-l(a~Pl+"qla~pl)c~,rl-*"'2t"v2** ~1 ~ 1 ~ 2 ~ 2 ! ~--- a~l~+XPl+Vq*a~ ~+~p: e t L - - -1 rl * r2 p 2 * - - g (L2) ~ a l al a2 (a2) est un langage d6terministe [-6]. []

Nous dirons qu'un ensemble lindaire L(uo; {u 1 . . . . . uk} ) est propre si les vecteurs Ul, . . . , u k sont lin6airement ind6pendants. Nous pouvons, 6noncer:

L e m m e 11. Soit L~_a* a~ un langage de la famitle SLB. Si 0(L) est un ensemble lin6aire propre, alors L appartient/ t la cl6ture booldenne de la famille des langages alg6briques d6terministes.

DOmonstration. D'apr6s le lemme pr6c6dent, il suffit d'examiner le cas off ~ (L)= L(uo; {(Pl, P2), (q l , q2)}) avec Pl P2 qlq2 >0- On peut supposer, sans nuire /i la

Intersections de langages alg6briques born6s 239

g6n6ralit6 de la d6monstra t ion que Uo=(0,0) et que f l=p2ql -p lq2>O. En posant 2 = p 2 ql, e=q~ q2 et Y=PaP2 on obtient :

1) 2 (q~, qa) = e (Pl, P2) + fl (ql, 0) et

2) ~ (Pl, P2) = ~ (ql , q2) § fl (0, Pe)-

Pour 0 < i < a , 0 < j < 2 et 0 < k < 7 , posons:

Li, j = L(i(pl, P2) +J(ql, qa); {(e Pl, c~ P2), (~ q,, 0)}) et

L~,k=L(j(Pl, Pz) § k(qt, q2); {(7 ql, 7 q2), (0, fl Pz)}).

D'aprhs le lemme prhc6dent A={wea*a*/tp(w)eL~,j, 0 < i < e , 0 < j < 2 } et B = {we a* a~/Ip (w)e L~, k, 0 =<j < 2, 0--<_ k < y} sont des unions finies de langages alg6briques dhterministes.

Montrons , maintenant , l'6galit6 entre L e t A c~ B. Prenons w e A ~B. Comme we A, x = ~ (w)= i(p,, P Z)-l-j (q~, q 2 ) § ]A ~ (Pl, P2) § 6 fl (ql , 0). On obtient, en utilisant 1), x = ( # c~-6 ~+ i) (p,, pa)+(6 2 + j ) (ql, q2). De m~me, comme xeB, on obtient, en utilisant 2), x = (s + 6' 2) (p,, P2) + (#' V - ~' ? + t) (ql, q2). Comme (Pl, P2) et (q,, q2) sont des vecteurs l in6airement indhpendants, on en d6duit que/~ c~ - 6 e + i = s + 6',~ appar t ien t / t N, donc xeO(L) et weL.

Comrne il est clair que L e s t inclus dans A et B, on en dhduit que L = A c~ B appart ient ~t la cl6ture boolhenne des langages alghbriques d6terministes. [ ]

Nous pouvons, mainteriant, prouver:

Proposition 12. Tou t langage de SLB, inclus dans w* w* appart ient ~ la cl6ture 1 2 ,

bool6enne de la famille des langages alg6briques d6terministes.

DOmonstration. Soit L~_w* w~ un langage SLB. S'il existe w tel que w 1 et w2ew*, _ s t o f f s et L est inclus dans w* et L est rationnel. Sinon, posons y l - w ~ , y2--w2

t d6signent, respectivement, les longueurs de w 2 et w~. Alors, Yl et Y2 sont deux mots diff6rents de m6me longueur (cf. [-5]).

Prenons ie {0 . . . . . s - 1} et j e {0, . . . , t - 1}. On peut, alors, construire une application s6quentielle g qui v6rifie: Vp, q e N , i p g(wl Yl Yq2 WJz)--al p a2. q Posons

i , , j , �9 , R i j = w , yl Y2 wz, Li j=Lc~RI j e t L =g(L i j). Clal rement /2 est un langage SLB, �9 * I , ~ , indus dans a I a 2 tel'que Li,~='g- (L)~ Ri, ~. Uensemble @(E) est un semilin6aire,

donc c'est une union finie de lin6aircs propres [5]. D'apr6s le lemme pr6c6dent, L' appartient ~ la clbture bool6enne des langagcs

alg6briques d6terministes, ainsi que L~. j puisque la famille des langages alg6briques d6terministes est fcrm6r par application s6quentielle inverse et intersection avec Its langages rationnels [-6]. La d6monstration est achev6e, car Lest une union finie de langages Li, j. []

R 6 f 6 r e n c e s

1. Book, R., Nivat, M., Paterson, M.: Intersections of linear context-free languages and reversal- bounded multipushdown machines, Procedings of sixth annual ACM Symposium on theory of Computing 290-296 (1974)

240 M. Latteux

2. Cole, S.N.: Real-time computation by n-dimensional iterative arrays of finite-state machines, 1.E.E.E. Transactions on Computer vol. C-18, 4, 349-365 (1969)

3. Cole, S.N.: Deterministic pushdown store machines and real-time computation, J.A.C.M. 18, 306 328 (1971)

4. Eilenberg, S.: Automata, languages and machines, Vol. A, New-York: Academic Press 1974 5. Ginsburg, S.: The mathematical theory of context-free languages, New York: McGraw-Hill 1966 6. Ginsburg, S., Greibach, S.: Deterministic context-free languages, Information and Control 9,

620~648 (1966) 7. Ginsburg, S., Spanier, E.M.: AFL with the semilinear property, J. Comp. Syst. Sc. 5, 365-396

(1971) 8. Latteux, M.: Sur les semilin6aires-langages bornds, Publication du Laboratoire de Calcul de

l'Universit6 de Lille I, n ~ 60 (1975) 9. Latteux, M.: C6nes rationnels commutativement clos, R.A.I .R.O. Informatique th6orique 11,

29-51 (1977) 10. Liu, L.Y., Weiner, P.: A characterization of semilinear sets, J. Comp. Syst. Sc. 4, 299-307 (1970) 11. Liu, L.Y., Weiner, P.: An infinite hierarchy of intersections of context-free languages. Math.

Systems theory 7, 185 192 (1973) 12. Wotschke, D.: Nondeterminism and Boolean operations in pda's, J. Comp. Syst. Sc. 16, 456461

(1978)

Regu le 1 er ddcembre 1977/revis6 le 17 novembre 1978