CANONICAL DECOMPOSITION OF CATENATION OF FACTORIAL LANGUAGES 7 A.E.FRID 0 0 2 Abstra t. A ording to a previous result byS. V. Avgustinovi h and n a theauthor,ea hfa toriallanguageadmitsaunique anoni alde omposition J to a atenation of fa torial languages. In this paper, we analyze the 1 appearan eofthe anoni alde ompositionofa atenationoftwofa torial 3 languages whose anoni al de ompositions are given. ] 1. Introdu tion O L This paper ontinuesaresear hof de ompositionsof fa torial languagesstarted in[1,2℄andinspiredby the(cid:28)eldoflanguageequationsandalgebrai operationson . s languages in general (see, e. g., [7, 8℄ and referen es therein). As the development c [ of the theory shows, even language expressions where the only used operation is atenation prove very di(cid:30) ult to work with. It seems that nothing resembling the 3 Makanin's algorithm for word equations (see, e. g., [4℄) an appear for language v 9 equations with atenation. Even easiest quesXtions tend to have very ompli ated 4 answers.In parti ular, the maximal solution of the ommutation equation 1 LX =XL 0 1 may be arbitrarily ompli ated: as it was shown by Kun [6℄, even if the language 6 L X is (cid:28)nite, the maximal language ommuting with it may be not re ursively 0 xy = yx / enumerxable. Tyhis situation x o=ntrzansts wiyth=thzamt for words, sin ze n,mf≥or0some s words and implies that and for some word and . c : In some sense, the problems of atenation of languages are due to the fa t that v a unique fa torization theorem is not valid for it: as it was shown by Salomaa i X and Yu [9℄, even a (cid:28)nite unary language an admit several essentially di(cid:27)erent r de ompositions to a atenation of smaller languages,and an in(cid:28)nite languagemay a L havenode ompositiontoprimelanguagesandall;herealanguage is alledprime L = L L L = {λ} λ L = L 1 2 1 2 if implies that , where is the empty word, and , or vi e versa. Toavoidambiguityofthiskind,werestri tourselvestofa torial languages.This family is large and widely investigated sin e it in ludes, e. g., languages of fa tors of (cid:28)nite or in(cid:28)nite words and languages avoiding patterns (in the sense of [3℄). We an also onsider the fa torial losure of an arbitrary language. Furthermore, the lassoffa toriallanguagesis losedundertaking atenation,unit,andinterse tion, and onstitutes a monoid with respe t to the atenation. De ompositions of fa torialla∗ng∗uages∗to a ∗ate∗natio∗n o∗f fa t∗oriallanguagesalso a b = (a +b )b = a (a +b ) may be several: for example, (here and below Frid, A. E., Catenationof fa toriallanguages. (cid:13) 2006 Frid A. E.. Theworkissupported byRFFI(grants 05-01-00364 and06-01-00694). 1 2 A.E.FRID (+) denotes unit). However,asit wasprovedin [1℄, we ande(cid:28)ne the notion ofthe anoni al de omposition of a fa torial language whi h alwaysexists and is unique. In this paper, we ontinue investigation of anoni al de ompositions of fa torial languagesandsolvethefollowinggeneralproblem:Given anoni alde ompositions A B AB oflanguages and ,whatisthe anoni alde ompositionoftheir atenation ? Besides the self-dependent interest, the answer to this question may help to solveequationsonfa toriallanguages.Indeed,equallanguageshaveequal anoni al de ompositions, and these anoni al de ompositions may be ompared as words. So, te hniques valid for words an be applied for them. Thus, this paper may be onsidered as a des ription a tool helpful for solving equations on fa torial languages. 2. Definitions and previous results ∗ ∗ Σ L ⊆ Σ u ∈ Σ Let be a (cid:28)nite alphabet, a∗nd be a language on it. A word is v ∈Σ v = sut s alled a fa tor of a word if for some (possibly empty) words and t L (L) . The set of all fa tors of words of a language is denoted by Fa . Clearly, ( (L))= (L) (L) L Fa Fa Fa , so that Fa may be alled the fa torial losure of . L L = (L) A language is alled fa torial if Fa . In parti ular, ea h fa torial λ language ontainsthe empty worddenoted by . In what follows,we onsideronly fa torial languages. The atenation of languages is an asso iative operation de(cid:28)ned by XY ={xy|x∈X,y ∈Y}. Clearly,languages onstituteamonoidwithrespe ttothe atenation,anditsunitis {λ} λ thelanguage ,where istheemptyword.Itisalso learthatfa toriallanguages form a submonoid of that monoid, sin e the atenation of two fa torial languages is fa torial. L L = XY L = X A fa torial language is alled inde omposable if implies or L=Y X Y for all fa torial languages and . ∗ ∆⊆Σ ∆ Lemma 1. [1℄ For ea h subalphabet , the language is inde omposable. Other examples of inde omposable languages dis ussed in [1℄ in lude languages of fa tors of re urrent in(cid:28)nite words, et . L=L ···L L ,...,L 1 n 1 n Ade omposition tofa toriallanguages is alledminimal if • L={λ} n=1 L ={λ} 1 implies and ; ′ • L6={λ} i=1,...,n Li 6={λ} L6=L1···Li−1LiLi+1···Ln If ,thenfor ′ wehave and for any fa torial language Li (Li. A minimal de ompositionto inde omposablefa torial languageis alled anoni al. L Theorem 1. [1℄ A anoni al de omposition of ea h fa torial language exists and is unique. L L In what follows, we shall denote the anoni al de omposition of by . Note F that a anoni al de omposition an be onsidered as a wo.rd on the alphabet of (=) all inde ompo∗sable fa toriallanguages.Inwhat follows, will denote equality of F elements of ; this notation will be used to ompare anoni al de ompositions. Allexamplesoffa toriallanguagesweshall onsiderinthispaperwillberegular, justbe auseregularlanguagesareeasytodealwith.Notethatthefa torial losure CANONICAL DECOMPOSITION OF CATENATION OF FACTORIAL LANGUAGES 3 of a regular language is always regular (whi h is a lassi al exer ise). We have proved also L L Theorem 2. [2℄ If is a regular fa torial language, then all entries of are also regular. 3. Preliminary results A B Suppose that we are given two fa torial languages, and , on an alphabet Σ A B , and know their anoni al de ompositions and . Our goal is to des ribe the AB anoni al de omposition , and the main result of the paper, Theorem 3, will givesu hades ription.TostateTheorem 3, weneedto de(cid:28)netwosubalphabetsof Σ Π ∆ , namely, and . L For a fa torial language , let us de(cid:28)ne Π(L)={a∈Σ|La⊆L}, and ∆(L)={a∈Σ|aL⊆L}. u ∈ L Th∗us, if we take any word , we an ext∗end it to the left by any word from ∆ (L) Π (L) L and to∗the righ∗t by any word from to get a word from . In other L = ∆ (L)LΠ (L) Π(L) ∆(L) words, , and and are de(cid:28)ned as maximal languages with this property. Forthemainresultofthispaper,weshallneedtoknowtherelationshipbetween Π(A) Π ∆(B) ∆ (further denoted by ) and (further denoted by ). The following lemmasexplainthemeaningofthesesubalphabets.NotethatanaloguesofLemmas 2(cid:21)5' were proved in [1℄, but the lemmas are reproved here both for the sake of ompleteness and of more pre ise wording. . L=L ···L Π(L)=Π(L ) ∆(L)=∆(L ) 1 k k 1 Lemma 2. If , then and . Π(L) ∆(L) Proof.Let us provethe statementfor ; the statement for is symmetri to it. α∈Π(L ) L α⊆L Lα=L ···L α⊆L ···L = k k k 1 k 1 k First, impliesthat andthus L Π(L )⊆Π(L) k ; so, . α∈Π(L) L1···Lk−1vα⊆L v ∈Lk Ontheotherhand, meansthat forall .Sin e L L k is a fa tor of the anoni′ al de omposition of ,′it annot be ontra ted to a smaller fa torial language Lk su h that L1···Lk−1Lk = L. It means that for ea h v ∈ Lk\{λ} wtv ∈ L w ∈ L1···Lk−1 tv ∈ Lk , there exists some word su h that , , w wtv L1···Lk−1 tv and is the longest pre(cid:28)x of belonging to . Sin e is not the w L1···Lk−1 wtvα ∈ L empty word, is also the longest pre(cid:28)x from of the word . tvα ∈ L vα ∈ L L k k k We see that and thus sin e is fa torial. Moreover, by the α∈L λα∈L L α⊆L α∈Π(L) k k k k same reaαso∈nΠ(L ) , whi h means that and thus . So, (cid:3) k implies , whi h was to be proved. A ∆⊆Σ Givenafa toriallanguage andasubalphabet ,letusde(cid:28)nethefa torial L (A) = (A\∆A) L (A) A ∆ ∆ language Fa . So, is the subset of ontaining exa tly Σ\∆ words starting with letters from and their fa tors. Symmetri ally, we de(cid:28)ne R (A) A Σ\∆ ∆ the subset of ontaining exa tly words whi h end with letters from R (A)= (A\A∆) ∆ and their fa tors: Fa . 4 A.E.FRID X B Σ Lemma 3. Let and be fa torial languages on . If there exists a fa torial A X = AB language ′ su h that , then there exists a unique minimal one, and it is A =R (A) ∆(B) equal to . ′ AB = X ⊆ ′Proof. First of a′ll, let us prove that . The in lusion is obvious: A ⊆ A AB ⊆ AB = X ⊇ and thus . To prove the in lusion, onsider a word x ∈ X b B X = AB x = ab , and let be its longest su(cid:30)x from : sin e , we have for a ∈ A a δ ∈ ∆(B) δb ∈ B some word . Suppose that ends with a symbol ; then ∆(B) b X B by the de(cid:28)nition of , and is not the longest su(cid:30)x of bel′onging to . A x = ab ∈ (A\A∆(B))B ⊆ R (A)B = AB x ∆(B) ontradi tion. Thus, , and sin ′e X ⊇ X = AB was an arbitrary element of , the in lusion (and thus the equality ) is proved. ′ A ⊆Y Y YB = It remains to provethat for every fa to′rial la′nguage ′ su h that X a ∈A A =R (A) ∆(B) .Let′us onsideranarbitrarynon-′emptyword .Sin e , the a sat ∈ A\A∆(B) wo′rd is a fa tor of some word ′ ′′ . Let the′last letter of the word sat α α∈Σ\∆ at=a α∈A atB ⊆AB =X =YB be equal to ; then , and . So, ′ ′′ . b∈B y(b) atb=a αb Forea h , let′us denoteby thelongest′pre(cid:28)xof ′ ′ belonging Y b atb = y(b)b b ∈ B to′ . Let the word be de(cid:28)ned by the equality ; then sin e atb∈YB . ′ ′ y(b) a b ∈ B a Clearly, if is not shorter than for some , then its pre(cid:28)x belongs′ Y Y y(b) a to (sin e is fa torial), and′this is what we need. But if is shorter than b ∈ B b αb αb ∈ B b ∈ B for all , then ea h word ontains as a su(cid:30)x. So, for all B α∈∆(B) ∆(B) (s′in e isfa to′rial),′and ′ bythede(cid:28)nitionof . A ontradi ′tion.So, a ∈Y a ∈A A AB =X (cid:3) for all , and is indeed the minimal language su h that . Symmetri ally, we an prove X A Σ Lemma 3' Let and be fa torial languages on . If there exists a fa torial B X = AB language ′ su h that , then there exists a unique minimal one, and it is B =L (B) Π(A) equal to . The following lemma is one of the main steps of the proof. A B Lemma 4. For ea h fa torial languages and , we have . . AB =R (A)·L (B)=R (A)·L (B). ∆(B) Π(R∆(B)(A)) ∆(LΠ(A)(B)) Π(A) Proof.Weshallprovethe(cid:28)rst′equality;these ondone an′b′ eprovedsymmetri ally. R (A) = A L (B) = B ′Let us denote ∆(B) and′ ′′Π(R∆(′B)(A)) .′ D′′ue to Lemma 3, AB = AB AB = AB AB = AB , and due to Lemma 3', . So, . Now note that all entries of the anoni al de omposition of a language aAreBin=.deA o′m·Bp′o′sable. So, to provethe required equality of anoni al de ompositionAs′ B′′ , we must proveonlythatnoentryofthe anoni alde ompositions or anbede reased to get the same produ t. ′ (A) Indeed, suppose we substit′uted an inde omposable entry of by its proper A A 1 fa torial subset. Ins′tead of , we obtained its proper fa torial su′bset . Then A B ⊆ AB A AB = AB 1 ′′ sin e′′ is the minimal fa tori′a′l language su h that . But B ⊆B A B ⊆A B (AB A B 6=AB 1 1 1 ; so, , and . B′′ Nowsupposewesubstitutedaninde omposableentr′y′ of by′itsprop′erf′′a torial B B AB 6=AB =AB 1 1 subset,′a′ndobtainedaproperfa torialsubset of .Then ′ B AB A sin e is the minAi′malBfa′ ′torial set giving when atenated with . So, no eAntBry of or an be repla ed by its proper subset without hangin(cid:3)g the result . The equality is proved. CANONICAL DECOMPOSITION OF CATENATION OF FACTORIAL LANGUAGES 5 X Y Σ ∆⊂Σ Lemma 5. Let ∗ and be fa torial languages on , and be a subalphabet Y *∆ R (XY)=XR (Y) ∆ ∆ su h that . Then . u∈XR (Y) u∈X y ∈Y ∆ Proof. Consider a word . If , let us hoose a symbol Σ\∆ uy ∈ XY\XY∆ ⊆ R (XY) u ∈ R (XY) u ∈/ X ∆ ∆ from . T′ hen , and thus ′ . If , u=xu x u X u ∈R (Y) ∆ then ,where i′s′thelongestpre(cid:28)xof belongingto′ and ′′ is′a u Y\Y∆ u u =sut non-emptyword.Let beawordfrom su hthat isits fa to′r: s t t Σ\∆ ut∈Y\Y∆ forsomewords an′d su hthatthelastletterof isfrom .Then , ut = xut ∈ XY\XY∆ ⊆ R (XY) u ∈ R (XY) ∆ ∆ and hen e . It follows that , and ⊇ the in lusion is proved. ′ ⊆ u ∈ R (XY) u = sut ∆ To prove the in lusion, onsider a word . Let be a XY\XY∆ u Σ\∆ word from whose fa tor is , so that its last letter is from . Then ut ∈ XY\XY∆ ut = xy x ∈ X y ∈ Y y ∈ Y\Y∆ . Let , where an′d ; then ′ and ut ∈ X(Y\Y∆) u ∈ X u = xy y y y′ ∈R (Y) . So, either u,∈oXr R (Y) for some pre(cid:28)x of : sin (cid:3)e ∆ ∆ , in both ases we have , and the in lusion is proved. Symmetri ally, we prove X Y Σ Π⊂Σ Lemma 5' Let ∗ and be fa torial languages on , and be a subalphabet X *Π L (XY)=L (X)Y Π Π su h that . Then . The followingseriesof lemmas isalsoone of importantparts ofthe main result. X Π⊂Σ ∆(X)\Π6= Lemma 6. Let be a fa torial language, be a subalphabet, and ∅ L (X)=X Π . Then . α∈Σ ∆(X)\Π u X Proof.Let be asymbol from ; then ea hword from anbe αu ∈ X ∆(X) u ∈ (αu) ⊂ (X\ΠX) = extended to by the de(cid:28)nition of . So, Fa Fa L (X) u L (X) ⊆ X Π Π L (X).=SiXn e was hosen arbitrarily, and , we get the equality(cid:3): Π . The symmetri lemma is X ∆⊂Σ Π(X)\∆6= Lemma 6'Let be a fa torial language, be a subalphabet, and ∅ R (X)=X ∆ . Then . . X X =X ···X 1 k Lemma 7. For ea h fa torial language with we have ∗ L∆(X)(X)=. (cid:26) XX2,···Xk, if X1 =∆ (X), otherwise. Symmetri ally, ∗ RΠ(X)(X)=. (cid:26) XX1,···Xk−1, if Xk =Π (X), otherwise. Proof. We shall prove the (cid:28)rst equality; the se ond one is symmetri . Let us ∆(X)=∆ denote . ∗ ∗ X 6= ∆ X ) ∆ L (X) = 1 1 ∆ Suppose (cid:28)rst that , that is, ∗ . Due to Lemma 5', L (X )X ···X X = ∆ L (X ) X ∆ 1 2 k 1 ∆ 1 1 . By the de(cid:28)nitions, ∗ . But the language is ∆ X = L (X ) X = 1 ∆ 1 inde omposable and is not.equal to , so, , and the equality L (X) L (X)=X ∆ ∆ (and thus ∗) is proved. X =∆ L (X)=L (X ···X ) 1 ∆ ∆ 2 k Now suppose that . Then by the de(cid:28)nition of L X\X ···X L (X) ∆ 2 k ∆ theoperator ,sin eallelementsof annoto urin∗ an∗yway. L (X ) = X X X = ∆ X = ∆ Y ∆ 2 2 1 2 2 Then, be ause otherwise we would have for Y =L (X )(X X ∆ 2 2 some , ontradi ting to the minimality of the de omposition . L (X) = L (X ···X ) = L (X )X ···X = X ···X ∆ ∆ 2 k ∆ 2 3 k 2 k So, due to Lemma 3', (cid:3). The latter de omposition is minimal and thus anoni al. 6 A.E.FRID 4. Main result . . A B A = A ···A B = 1 k Theorem 3. Let and be fa torial languages with and B ···B Π=Π(A) ∆=∆(B) 1 m .Letusdenote and .Thenthe anoni alde omposition AB of the atenation an be found as follows.: ∆\Π6=∅ Π\∆6=∅ AB =A·B (1) If and ∗ , then ∗ . . ∆=Π A 6=∆ B 6=∆ AB =A·B k 1 (2) If , and ∗ , ., then . (3) If ∆=Πand∗ Ak =∆ ,t.henAB =A1···Ak−1B.Symmetri ally,if∆=Π B =∆ AB =AB ···B 1 2 m and , then . . . Π ( ∆ AB = R (A)·B ∆ ( Π AB = ∆ (4) If , then . Symmetri ally, if , then A·L (B) Π . Proof. Cases (1) and (4) are obtained dire tly by applying Lemmas 6 and 6' to the equality from Lemma 4. Case (2) is as well obtained by applying to Lemma 4 Lemma 7. ∗ . A = ∆ L (A) = k ∆ At last, in Case (3), if , we apply Lemmas 7 and 2 to get A1···Ak−1 Π(L∆(A)) = Π(Ak−1) Π(Ak−1) ∆ and ∗ . Assume th∗at in ludes as a subset.ThenAk−1.=Ak−1∆ ,and∗A=A1···Ak−1∆ =A1···Ak−1, ontradi ting A=A1···Ak−1∆ ∆\Π(Ak−1)6=∅ tothefa tthat .So, ,andweapplyLemma6to L (B)=B (cid:3)get Π(Ak−1) . It remains to use Lemma 4 to get Case (3) of the Theorem. AB A Corollary 1. The anoni al de omposition of either begins with , or ends B A B with , so that only one of the languages and an give anoni al fa tors of AB di(cid:27)erent from the anoni al fa tors of the language itself. ∗ ∗ A = {a,b} B = {a,c} Π(A) = {a,b} ∆(B) = {a,c} Example 1. If and , then ∗ ∗ , , AB {a,b} ·{a,c} and the anoni al de omposition of is just (Case (1)). ∗ ∗ A = {a,ab} B = {a,ac} Π(A) = ∆(B) = {a} Example 2. If Fa and Fa , the∗n ∗ , AB {a,ab} {a,ac} and the anoni al de omposition of is just Fa Fa (Case (2)). A {a,b} Here isthelanguageofallwordson whi hdonot ontaintwosu essive b B {a,c} s,and isthelanguageofallwordson whi hdonot ontaintwosu essive c s. ∗ ∗ A = a B = {a,ab} Π = ∆ = {a} AB = B Example 3. If and Fa , then , and (Case (3)). ∗ ∆ = Π A = B = ∆ k 1 Example 4. Note that when and ∗ ∗ , Case (3)∗m∗ay be A=a b B =b a appli.ed∗in a∗ny∗of the two dire tions. For example, if and ∗ , then AB =a ·b ·a b ,anditdoesnotmatterwhi hoftheo urren esof wasremoved. Before giving exa′mples for Case (4), we will spe ify the form of the anoni al A = R (A) A ∆ de omposition of . . Re all that is a fa torial language with the A=A ···A ∆ Σ 1 k anoni al de omposition ′ , and is a subalphabet of . A i = k,...,1 Let us de(cid:28)ne languages i, , as obtained by the following iterative ∆ :=∆ i k k pro edure: starting from , we put for ea h from to 1 ′ ′ ∗ Ai = R∆i(Ai) and ∆i−1 =∆(Ai), if Ai *∆i, ′ Ai = {λ} ∆i−1 =∆i, . and otherwise ′ A =R (A) ∆ Lemm{λa}8. The anoni al de ompositionoAf′ =A′ ·A′ ·· ·aAn′beobtainedbydeleting extra entries from the de omposition 1 2 k. CANONICAL DECOMPOSITION OF CATENATION OF FACTORIAL LANGUAGES 7 ′ ′ Proof.Fi′rstof′all,notethat′dueto′ Lemma5appliediteratively′,A =A1···Ak−1Ak = A1···Ak−2Ak−1Ak = ... =∗A1···Ak.′Some of the languages Ai an be equal to {λ} A ⊆ ∆ A = {λ} ;′ in parti ular, if , then , as well as a′ll its fa tors. However, A 6= {λ} A {λ} i if , then we an anoni ally de ompose fa tors not equal to and erase the others. ′ A i Clearly, if we substi′t′ute an′y of anoni al fa tors of by its proper subset, we A ( A ge′t a n′ew lan′guag′′e ′ i i′. So, to pro′′ve the′ lemma, we should just show that A 6=A1···Ai−1AiAi+1···Ak for any Ai (′ Ai. ′ Forall i=1,...,k, letusde(cid:28)neDi =A1···Ai andEi−1 =A1···Ai−1. Wealso D ={λ} i≥1 D 0 i de(cid:28)ne . Note that by th′e de(cid:28)nit′ion an′d Lemma 3, for all , is the D A ···A = A m′inimal′′language s′′u h that i i+1 k . So, it remains′′to prove only that Ai = Ai Ai Di−1Ai = Di , whe′′re is the ′minimal language su h that . By Lemma A =L (A ) 3', we have i Π(Di) i . ′ ′ First, suppose that Di−1 6= Ei−1. We knew that Di = Di−1′Ai = Ei−1Ai, and Di−1 is the minimal languagegiving DDi when atenated with Ai. So, byAC′orollary 1, in the ano′ni al′d′e omposition of i the fa tors orresponding to i do not A =A hange, and i i, whi h was to be proved. Di−1 = Ei−1 Π(Di−1) = Π(Ei−1) = Π(Ai−1) Now suppose that . Then ′ . From Π A i now on, we denote this subalphabet just by . We knew that was equal to LΠ′(Ai) Ei sin eitwastheminimal f′a′ toriallan′ guage′giving when atenatedwith Ei−1 Ai =LΠ′(Ai)6=Ai . Assume by ontrary that ′ ′′ . ′′ u∈A \A A Let u′s onsider a wo′rd∗ i i. It∗does not belong to i, whi h means that su∈A su∈ΠΣ s∈Σ u i ′ implies for a′ll (in parti ular, starts with a letter from Π u ∈ A ut ∈ A ∩A (Σ\∆ ) ). O∗n the other hand, i,′whi h means that i i i for some t ∈ Σ ut ∈ A ut . By the de(cid:28)nition, i, and the set of non-empty left extensions of A u i to elements of is a subset of that for : {s∈Σ+|sut∈A }⊆{s∈Σ+|su∈A′}⊆Π′Σ∗. i i ′ ∗ λu = u ∈ ΠΣ ut ∈/ LΠ′(Ai) Sin e we already know that , we see that . So, Ai 6= LΠ′(Ai) Ei = A1···Ai , ontradi ting to the fa t that the de omposition ′ ′′ A 6=A was mini′mal. W′′ e have found a ontradi tion to the assum′ption′that ′ i i. A = A A = A ···A {λ}So, i i, and the de omposition obtained from 1 k by deletin(cid:3)g entries is minimal, whi h was to be proved. Tomakethedes ription omplete,westate.thesymmetri lemma,forthe aseof ∆(Π B B =B1···Bm Π . Let beafa toriallanguagewith and beasubalphabet; Π =Π j =1,...,m 1 we start from and su essively de(cid:28)ne for ea h ′ ′ ∗ Bj = LΠj(Bj) and Πj+1 =Π(Bj), if Bj *Πj, ′ B = {λ} Π =Π , . j j+1 j and otherwise The lemma symmetri to Lemma 8 is ′ B =L (B) Π {Lλe}mma8'The anoni al de omposiBtio′n=oBf′ ·B′ ···B′ an be obtainedby deleting entries from the de omposition 1 2 m. The following easy example for Case (4) of Theorem 3 illustrates Lemma 8. A = (a∗b∗)k +(b∗a∗)k A =. (a∗+ bE∗x)2akmple 5A. T=he·· ·a=noAni al=de( ao∗m+pob∗si)tion of+ is 1 2k with ∗ ′ ∗ ′ (here ∗denotes the unit). If we atenate B = a A = b A = a iAt′w=it(ha∗b∗)k , AwBe g=.et(a∗2·kb∗)k·a,∗ 2k−1 , and so on, and at last obtain and . 8 A.E.FRID Referen es [1℄ S. V. Avgustinovi h, A. E. Frid, A unique de omposition theorem for fa torial languages, Internat. J.AlgebraComput.15(2005),149(cid:21)160. [2℄ S. V.Avgustinovi h, A. E. Frid,Canoni al de omposition of a regular fa torial language, in: D. Grigoriev, J. Harrison, E. Hirs h (Eds.), Computer S ien e - Theory and Appli ations, Springer,2006 (LNCS3967),18(cid:21)22. [3℄ J. Cassaigne, Unavoidable patterns, in: in: M. Lothaire, Algebrai Combinatori s on Words, CambridgeUniv.Press,2002.Pp.111(cid:21)134. [4℄ V. Diekert, Makanin's Algorithm, in: M. Lothaire, Algebrai Combinatori s on Words, CambridgeUniv.Press,2002.Pp.387(cid:21)442. [5℄ J. Karhum(cid:4)aki, M. Latteux, I. Petre, Commutation with odes, Theoret. Comput. S i. 340 (2005), 322-333. [6℄ M. Kun , The power of ommuting with (cid:28)nite sets of words, in: Theoreti al Aspe ts of Computer S ien e(STACS'05),Springer,2005(LNCS3404),569(cid:21)580. [7℄ M.Kun ,Simple language equations,Bull.EATCS85(2005), 81-102. [8℄ A.Okhotin,De isionproblemsforlanguageequationswithBooleanoperations,in:Automata, Languages andProgramming,Spriger, 2003(LNCS2719),239(cid:21)251. [9℄ A. Salomaa, S. Yu, On the de omposition of (cid:28)nite languages, in: Developments of Language Theory.Foundations,Appli ations,Perspe tives, WorldS ienti(cid:28) ,2000,22(cid:21)31. Anna E. Frid Sobolev Institute of Mathemati s, pr. Koptyuga, 4, 630090, Novosibirsk, Russia E-mail address: fridmath.ns .ru