dP Automata versus Right-Linear Simple Matrix Grammars

dP Au oma a e sus Righ -Linea Simple Ma ix G amma s Gheo ghe P˘aun1,2, Ma io J. P´e ez-Jim´enez2 1Ins i u e o Ma hema ics o he Romanian Academy PO Box 1-764, 014700 Bucu e¸s i, Romania 2Depa men o Compu e Science and A i icial In elligence Uni e si y o Se illa A da. Reina Me cedes s/n, 41012 Se illa, Spain [email p o ec ed], [email p o ec ed] Summa y. We conside dP au oma a wi h he inpu s ing dis ibu ed in an a bi a y (hence no necessa y balanced) way, and we in es iga e hei language accep ing powe , bo h in he case when a bound he e is on he numbe o objec s p esen inside he sys em and in he gene al case. The ela ion wi h igh -linea simple ma ix g amma s is use ul in his espec . Some esea ch opics and open p oblems a e also o mula ed. 1 In oduc ion dP au oma a a e a class o compu ing de ices conside ed in memb ane compu ing a ea in o de o ha e a dis ibu ed language accep ing machine y, wi h he s ings o ecognize being spli among he componen s o he sys em and wi h hese com- ponen s wo king in pa allel on he inpu s ings. In he gene al case, dP sys ems consis o a gi en numbe o componen s in he o m o a usual sympo /an ipo P sys em, which can ha e hei sepa a e inpu s and communica e om skin o skin memb anes by means o an ipo ules like in issue-like P sys ems. Such de ices we e in oduced in [7] and u he in es iga ed in [3], [8], [9], mainly compa ing hei powe wi h ha o usual P au oma a and wi h amilies o languages in he Chomsky hie a chy. In he basic de ini ion and in all hese pape s, ollowing he s yle o he communica ion complexi y a ea (see, [4]), he so-called balanced mode o in oducing he inpu s ing is conside ed: he s ing is spli in equal pa s, modulo one symbol, and dis ibu ed among componen s. He e we conside he gene al case, wi h no es ic ion on he inpu s ing dis i- bu ion; each componen jus akes symbols om he en i onmen when i can do i i , wi hou any es ic ion on hei numbe . This is a e y na u al and gene al se -up, which, howe e , was only inciden ally in es iga ed so a . Two cases a e dis inguished: wi h a bound on he size o he sys em (on he o al numbe o ob- jec s p esen inside) and wi hou such a bound. Bo h cases a e na u ally ela ed o 294 Gh. P˘aun, M.J. P´e ez-Jim´enez a classic amily o egula ed g amma s, he simple ma ix g amma s o [5] (see also [2]). Ac ually, as expec ed, igh -linea simple ma ix g amma s a e closely ela ed o dP au oma a, and we will examine below his connec ion (looking o mu ual simula ions among he wo ypes o language iden i ying machine ies). This con- nec ion was al eady poin ed ou in [8], whe e he conjec u e was o mula ed ha , in he same way as a usual ini e au oma on can be simula ed by a P au oma on, a igh -linea simple ma ix g amma can be simula ed by a dP au oma on. We con i m he e his conjec u e (in he gene al, no he balanced case). 2 Fo mal Language Theo y P e equisi es The eade is assumed o ha e some amilia i y wi h basics o memb ane compu - ing, e.g., om [6], [10], and o o mal language heo y, e.g., om [2], [11], bu we ecall below all no ions necessa y in he subsequen sec ions. In wha ollows, V∗is he ee monoid gene a ed by he alphabe V,λis he emp y wo d, V+=V∗− {λ}, and |x|deno es he leng h o he s ing x∈ V∗.REG, LIN, CF, CS, RE deno e he amilies o egula , linea , con ex - ee, con ex -sensi i e, and ecu si ely enume able languages, espec i ely. Essen ial below will be he igh -linea simple ma ix g amma s in oduced in [5]. Such a g amma o deg ee n≥1 is a cons uc o he o m G= (N1, . . . , Nn, T, S, M), whe e N1, N2, . . . , Nn, T a e pai wise disjoin alphabe s (we deno e by N he union o N1, . . . , Nn), S /∈T∪N, and Mcon ains ma ices o he ollowing o ms: (i) (S→x), x ∈T∗, (ii) (S→A1A2. . . An), Ai∈Ni,1≤i≤n, (iii) (A1→x1B1, . . . , An→xnBn), Ai, Bi∈Ni, xi∈T∗,1≤i≤n, (i ) (A1→x1, . . . , An→xn), Ai∈Ni, xi∈T∗,1≤i≤n. A de i a ion s a ing wi h a ma ix o ype (ii) con inues wi h an a bi a y numbe s o s eps which use ma ices o ype (iii) and ends by applying a ma ix o ype (i ). We deno e by L(G) he language gene a ed in his way by Gand by RSMn he amily o languages L(G) o igh -linea simple ma ix g amma s Go deg ee a mos n, o n≥1. The union o all hese amilies is deno ed by RSM∗. The s ic inclusions RSMn⊂RSMn+1, n ≥1, a e known. Mo eo e , REG =RSM1, RSM∗⊂CS,RSM∗is incompa able wi h LIN and CF, all languages in RSM∗ a e semilinea , and his amily is closed unde union, in e sec ion wi h egula languages, di ec and in e se mo phisms (bu no unde in e sec ion, complemen and Kleene +). Clea ly, a no mal o m can be easily ound o hese g amma s: in ma ices o ype (iii) we can ask o ha e xi∈T∪ {λ},1≤i≤n, and in ma ices o ype (i ) we can ha e xi=λ o all 1 ≤i≤n. dP Au oma a e sus Righ -Linea Simple Ma ix G amma s 295 3 dP Au oma a We in oduce now he compu ing de ices we in es iga e in his pape , also gi ing a ele an example. As usual in memb ane compu ing, he mul ise s o e an alphabe Va e ep e- sen ed by s ings in V∗; a s ing and all i s pe mu a ions co espond o he same mul ise , wi h he numbe o occu ences o a symbol in a s ing ep esen ing he mul iplici y o ha objec in he mul ise . (We wo k he e only wi h mul ise s o ini e mul iplici y.) The e ms “symbol” and “objec ” a e used in e changeably, all objec s a e he e ep esen ed by symbols. AdP au oma on (o deg ee n≥1) is a cons uc ∆= (O, E, Π1, . . . , Πn, R), whe e: (1) Ois an alphabe (o objec s); (2) E⊆O( he objec s a ailable in a bi a ily many copies in he en i onmen ); (3) Πi= (O, µi, wi,1, . . . , wi,ki, E, Ri,1, . . . , Ri,ki) is a sympo /an ipo P sys em o deg ee ki(Ois he alphabe o objec s, µiis a memb ane s uc u e o deg ee ki,wi,1, . . . , wi,kia e he mul ise s o objec s p esen in he memb anes o µi in he beginning o he compu a ion, Eis he alphabe o objec s p esen – in a bi a ily many copies – in he en i onmen , and Ri,1, . . . , Ri,kia e ini e se s o sympo /an ipo ules associa ed wi h he memb anes o µi; he sympo ules a e o he o m (u, in),(u, ou ), whe e u∈O∗, and he an ipo ules a e o he o m (u, ou ; , in), whe e u, ∈O∗; no e ha we do no ha e an ou pu memb ane), wi h he skin memb ane labeled wi h (i, 1) = si, o all i= 1,2, . . . , n; (4) Ris a ini e se o ules o he o m (si, u/ , sj), whe e 1 ≤i, j ≤n, i 6=j, and u, ∈O∗, u 6=λ. The sys ems Π1, . . . , Πna e called componen s o ∆and he ules in Ra e called communica ion ules. Fo a ule (si, u/ , sj), |u |is he weigh o his ule. Using a ule (u, in),(u, ou ) associa ed wi h a memb ane imeans o b ing in he memb ane, espec i ely o send ou o i he mul ise u; using a ule (u, ou ; , in) associa ed wi h a memb ane imeans o send ou o he memb ane he objec s o mul ise uand, simul aneously, o b ing in he memb ane, om he egion su - ounding memb ane i, he objec s o mul ise . A communica ion ule (si, u/ , sj) mo es he objec s o u om componen Πi o componen Πj, simul aneously wi h mo ing he objec s in he mul ise in he opposi e di ec ion. Each componen Πican ake symbols om he en i onmen , wo k on hem by using he ules in se s Ri,1, . . . , Ri,ki, and communica e wi h o he componen s by means o ules in R. A hal ing compu a ion wi h espec o ∆accep s he s ing x=x1x2. . . xn o e Oi he componen s Π1, . . . , Πn, s a ing om hei ini ial con igu a ions, using he sympo /an ipo ules as well as he in e -componen s communica ion 296 Gh. P˘aun, M.J. P´e ez-Jim´enez ules, in he non-de e minis ic maximally pa allel way, b ing om he en i onmen he subs ings x1, . . . , xn, espec i ely, and e en ually hal s. A p oblem appea s in he case when se e al objec s a e ead a he same ime om he en i onmen , by se e al ules o by a single ule o he o m (u, ou ; , in), wi h | | ≥ 2; in such a case any pe mu a ion o he symbols b ough in he sys em in he same s ep a e conside ed as a alid subs ing o he inpu s ing ( hus, a compu a ion can ecognize se e al s ings, di e ing o each o he by pe mu a ions o ce ain subs ings). No e ha we impose he e no condi ion on he ela i e leng hs o s ings x1, x2, . . . , xn(as i is done in p e ious pape s dealing wi h dP au oma a, unde he in luence o communica ion complexi y a ea). We deno e by L(∆) he language o all s ings ecognized by ∆in his way, and by LdPn he amily o languages L(∆), o ∆o deg ee a mos n≥1. The union o all hese amilies is deno ed by LdP∗. The dP au oma a a e synch onized de ices, a uni e sal clock exis s o all componen s, ma king he ime in he same way o he whole dP au oma on. When he sys em has only one componen , hen we ob ain he usual no ion o a P au oma on, as in es iga ed in a se ies o pape s (mainly in he ex ended e sion, wi h a e minal alphabe o objec s – see he espec i e chap e in [10] and he e e ences he ein). We deno e by LP he amily o languages ecognized by P au oma a. Hence, LP =LdP1and, om [3], i is known ha REG ⊂LP ⊂CS and LP is incompa able wi h CF. We conside now a somewha su p ising example, o a dP au oma on o deg ee 2, gene a ing a complex language, L1={ww |w∈ {a, b}∗}. The au oma on is gi en in Figu e 1, in he s anda d way o ep esen ing a dP au oma on. We ha e O={a, b, c1, c2, d, #}and E={a, b}. All an ipo ules which b ing objec s om he en i onmen a e o weigh one, hence he numbe o objec s p esen in he sys em is cons an , ou in each compo- nen . In he i s s ep, objec s d elease c2ain he skin egion o he i s componen and c1ain he second. Each symbol acan b ing ei he an ao a b om he en- i onmen and, a he same ime, he objec s c1, c1a e in e changed be ween he wo componen s (o he wise, hey elease he ap objec #, which will oscilla e o e e ac oss memb anes (1,1), espec i ely, (2,1), and he compu a ion ne e s ops). Wi h c1α, α ∈ {a, b}, in he i s componen and c2β, β ∈ {a, b}, in he second one, he only con inua ion which does no elease he ap objec is possi- ble when α=β, by using he communica ion ule (s1, c1α/c2α, s2) (i one o he symbols α, β b ings new symbols om he en i onmen , he co esponding c1, c2 should en e he memb ane (1,2) o (2,2), b inging ou he objec #). We ob ain a con igu a ion as ha we s a ed wi h, hence he p ocess can be i e a ed. I , a any momen when c2is in Π1and c1is in Π2, one o he ules (c2α, in), α ∈ {a, b}, is used in he i s componen , o (c1α, in), α ∈ {a, b}, is used in he second com- ponen , hen his should be done simul aneously in bo h componen s, o he wise again one o c1, c2has o elease he ap objec . In conclusion, he s ings ead om he en i onmen by he wo componen s a e iden ical, hence L(∆) = L1. dP Au oma a e sus Righ -Linea Simple Ma ix G amma s 297 ' & $ % ' & $ % º ¹ · ¸ º ¹ · ¸º ¹ · ¸ º ¹ · ¸ -¾ s1 d (1,1) a c2 (c2a, ou ;d, in) (c2a, in) (c2b, in) (#, in) (#, ou ) # (#, ou ;c1, in) (#, ou ;c2, in) (a, ou ;a, in) (a, ou ;b, in) (b, ou ;a, in) (b, ou ;b, in) (s1, c1a/c2a, s2) (s1, c1b/c2b, s2) (s1, c2/c1, s2) s2 d (2,1) c1 a (c1a, ou ;d, in) (c1a, in) (c1b, in) (#, in) (#, ou ) (2,2)(1,2) # (#, ou ;c2, in) (#, ou ;c1, in) (a, ou ;a, in) (a, ou ;b, in) (b, ou ;a, in) (b, ou ;b, in) Fig. 1. A dP au oma on ecognizing he language L1. No e he impo an ac s ha he sys em eads he inpu in a balanced way and ha i is bounded, he o al numbe o objec s p esen inside is always bounded by a cons an (8 in ou case) gi en in ad ance. This las cha ac e is ics is impo an , so ha we deno e by LdPb n, n ≥1, he amily o languages ecognized by bounded dP au oma a o deg ee a mos n; when nis no speci ied, we eplace i by ∗. 4 The Powe o dP Au oma a We s a by e o mula ing in a mo e gene al way a esul al eady sugges ed by a p oo in [9]. Theo em 1. LdPb n⊆RSMn, o all n≥1. P oo . Le ∆be a dP au oma on o deg ee n(wi h he se o objec s O) which is bounded. Then, he se o all i s con igu a ions is ini e. Le σ0, σ1, . . . , σpbe his se , wi h σ0being he ini ial con igu a ion. We cons uc he ollowing igh -linea simple ma ix g amma : 298 Gh. P˘aun, M.J. P´e ez-Jim´enez G= (N1, . . . , Nn, O, S, M),wi h Ni={(σj)i|0≤j≤p}, i = 1,2, . . . , n, M={(S→(σ0)1(σ0)2. . . (σ0)n)} ∪ {(σi)1→α1(σj)1, . . . , (σi)n→αn(σj)n)| om con igu a ion σi he dP au oma on ∆can pass o he con igu a ion σjby a co ec ansi ion, aking om he en i onmen he objec s α1, . . . , αnby i s componen s, whe e αs∈O∪ {λ},1≤s≤n} ∪ {(σh)1→λ, . . . , (σh)n→λ)|σhis a hal ing con igu a ion}. No e ha all non e minals in he ules o a ma ix con ain he same “co e in- o ma ion”, namely he cu en con igu a ion o he sys em, hence he comple e con ol o he sys em wo king is ob ained in his way. The equali y L(∆) = L(G) is ob ious. 2 This esul canno be ex ended o a bi a y dP au oma a. Ac ually, we ha e: Theo em 2. LdP2−RSM∗6=∅. P oo . Le us conside he ollowing dP au oma on: ∆= (O, E, Π1, Π2, R),wi h O={a, c, d, e, , #}, E={a, c, d, e}, Π1= (O, [ ]s1, , E, {( , ou ;a, in),(a, ou ;aa, in)}), Π2= (O, [ [ ](2,1) ]s2, E, {( , ou ;d, in),(a, ou ;c, in),(d, ou ;e, in)}, {( , ou ; , in)}), R={(s1, a/λ, s2)}. Fo an easie examina ion o he wo k o he sys em, we also ep esen i g aph- ically, in Figu e 2. Le us look o s ings accep ed by his dP au oma on which a e o he o m aidcje, o some i, j ≥1. A e in oducing he symbol ain he i s componen , le us assume ha o n≥0 s eps we use he e he ule (a, ou ;aa, in), hence we p oduce 2ncopies o ain Π1, while he second componen uses he ule ( , ou ; , in)∈R(2,1). Suppose now ha p≥0 copies o a emains in he i s componen and he o he s = 2n−pa e mo ed o he second componen . He e, all copies o amus go ou , in exchange o objec s c, hence he s ing ead by he second componen s a s wi h c . A he same ime o one s ep be o e, he second componen mus in oduce he symbol d. This objec becomes immedia ely e, hence he exchange o a o cshould be done ei he in he same s ep wi h eading do a he same ime wi h eading ein dP Au oma a e sus Righ -Linea Simple Ma ix G amma s 299 ' & $ % ' & $ % ¾ ½» ¼ - s1 ( , ou ;a, in) (a, ou ;aa, in) (s1, a/λ, s2) s2 (2,1) ( , ou ; , in) ( , ou ;d, in) (d, ou ;e, in) (a, ou ;c, in) Fig. 2. A dP sys em ecognizing a language no in RSM∗ he second componen (because any pe mu a ion o he objec s is allowed in he s ing, ei he a ian is possible). Howe e , a e e, we do no wan o ha e any symbol, hence all copies o awe e al eady mo ed o he second componen , and hus he wo k o he i s componen s ops. When in oducing he symbol din he second componen , he pcopies o a om he i s componen canno use he ule (a, ou ;aa, in), bu hey mus come immedia ely in he second componen , o in oduce che e a he same ime wi h in oducing e. The e o e, i he s ing has he o m aidcje, hen i=j= 2n o some n≥0 (n= 0 is ob ained i he unique ain oduced in he i s s ep in Π1is immedia ely sen o componen Π2). Consequen ly, L(∆)∩a∗dc∗e={a2ndc2ne|n≥0}, which is no in RSM∗, hence also L(∆) is no in RSM∗: his amily is closed unde in e sec ion wi h egula languages and con ains only semilinea languages. 2 No e ha he p e ious cons uc ion akes he inpu s ing in an almos bal- anced way, and, i in he i s s ep, he i s componen uses a ule ( , ou ;dea, in) ins ead o ( , ou ;a, in), hen we ha e a balanced unc ioning, hence he esul in he p e ious heo em holds ue also o he balanced way o de ining he ecog- nized s ing. We pass now o he coun e pa o Theo em 1 announced abo e. Theo em 3. RSMn⊆LdPb n+1, o all n≥1. P oo . Le us conside a igh -linea simple ma ix g amma G= (N1, . . . , Nn, T, S, M) as in oduced in Sec ion 2, wi h he alphabe s N1, N2, . . . , Nn( hei union is deno ed by N) and T. Ma ices o he o m (i), (S→x), x ∈T∗, can be eplaced by ma ices o o ms (ii), (iii) and (i ), in an ob ious way, hence we assume ha we do no ha e such ma ices. We assume all ma ices labeled in a one- o-one way; le mj: (A1→x1B1, . . . , An→xnBn), wi h 1≤j≤k, be all ma ices o ype (iii), wi h Ai, Bi∈Ni, xi∈T∗,1≤i≤n. Simila ly, le mj: (A1→x1, . . . , An→xn), wi h k+ 1 ≤j≤p, be all ma ices o 300 Gh. P˘aun, M.J. P´e ez-Jim´enez ype (i ), wi h Ai∈Ni, xi∈T∗,1≤i≤n. Wi hou any loss o he gene ali y we can assume ha all s ings xiin hese ma ices a e om T∪ {λ}. Fo each ma ix, o any o m, mj: (A1→u1, . . . , Ai→ui, . . . , An→un), le us conside he symbol [mj, Ai→ui] ( hus iden i ying he ma ix and i s i h ule), and le Xj(i) be a sho hand o i . Conside he alphabe s Mi={Xj(i)|1≤j≤p}, o all 1 ≤i≤n. We also deno e by M0 i he alphabe o p imed symbols in Mi. Fo a ma ix mj: (A1→x1B1, . . . , An→xnBn) o ype (iii), le us deno e lhsj=A1A2. . . Anand hsj=B1B2. . . Bn. Simila ly, o a ma ix mj: (A1→ x1, . . . , An→xn) o ype (i ), we deno e lhsj=A1A2. . . An. I hsj=lhsk, hen we w i e mj;mk. Simila ly, we w i e S;mji (S→A1A2. . . An)∈Mand A1A2. . . An=lhsj. Fo a se Q, we deno e by Qalso he mul ise consis ing o he elemen s o Q, wi h he mul iplici y one o each o hem (hence Qcan be conside ed also as he s ing composed by he elemen s o he se , in any o de ing). We a e now eady o cons uc he dP sys em we look o (a0is an a bi a y symbol o T ixed in ad ance): ∆= (O, E, Π1, . . . , Πn+1, R),wi h : O= n [ i=1 (Mi∪M0 i)∪T∪ {ci|1≤i≤n}∪{d, , #}, E=T, Πi= (O, [ [ ](i,1)[ ](i,2) ]si, λ, M0 iTci,#, Rsi, R(i,1), R(i,2)), Rsi={(a, ou ;b, in)|a, b ∈T}, R(i,1) ={(X0 j(i), ou ;Xj(i), in), (Xj(i)cia, ou ;X0 j(i)cia, in)|1≤j≤p, i Xj(i) = [mj, Ai→aBi], a ∈T} ∪ {(X0 j(i)a, ou ;Xj(i)a, in), (Xj(i)cia, ou ;X0 j(i)cia, in)|1≤j≤p, a ∈T, i Xj(i) = [mj, Ai→Bi]} ∪ {(#, in),(#, ou )}, R(i,2) ={(#, ou ;ci, in)} ∪ {(#, ou ;Xj(i), in)|1≤j≤p, i Xj(i) = [mj, Ai→Bj]}, o all 1 ≤i≤n, Πn+1 = (O, [ [ ](n+1,1) ]sn+1 , c1. . . cn , M2 1. . . M2 nTnan 0,∅, R(n+1,1)), R(n+1,1) ={(Xj(1) . . . Xj(n)an 0, ou ; , in)|1≤j≤pi S;mj} ∪ {(Xk(1)a1. . . Xk(n)an, ou ;Xj(1)a1. . . Xj(n)an, in) |1≤j, k ≤p, ai∈T, 1≤i≤n, i mj;mk} dP Au oma a e sus Righ -Linea Simple Ma ix G amma s 301 ∪ {(Xj(1)c1a1. . . Xj(n)cnan, in) |ai∈T, 1≤i≤n, i mjis a e minal ma ix}, R={(si, λ/ci, sn+1), (si, ci/Xj(i)a, sn+1, (si, Xj(i)cia/λ, sn+1)|1≤j≤p, 1≤i≤n, a ∈T}. This dP sys em, wi h one componen Πiand wi h Πn+1 gi en in ull de ails, is ep esen ed in Figu e 3. ' & $ % ' & $ % ' & $ % ' & $ % ' & $ %                       6 ? 6 ? 6 ? s1 (1,1) (1,2) ... si (i, 1) (i, 2) ... sn (n,1) (n,2) sn+1 (n+1,1) (a, ou ;b, in), a, b ∈T (X0 j(i), ou ;Xj(i), in), (Xj(i)cia, ou ;X0 j(i)cia, in), i Xj(i) = [mj, Ai→aBi], a ∈T, 1≤j≤p (X0 j(i)a, ou ;Xj(i)a, in), (Xj(i)cia, ou ;X0 j(i)cia, in), i Xj(i) = [mj, Ai→Bi],1≤j≤p, a ∈T (#, in) (#, ou ) (#, ou , ci, in) (#, ou ;Xj(i), in), i ule iin mjis Ai→Bi,1≤j≤p (si, λ/ci, sn+1) (si, ci/Xj(i)a, sn+1), a ∈T, 1≤j≤p (si, Xj(i)cia/λ, sn+1), a ∈T, 1≤j≤p c1c2...cn Sn i=1 M2 i Tn an 0 (Xj(1) ...Xj(n)an 0, ou ; , in) i S;mj (Xk(1)a1...Xk(n)an, ou ;Xj(1)a1. . . Xj(n)an, in), i mj;mk (Xj(1)c1a1...Xj(n)cnan, in) i mjis e minal Fig. 3. The dP sys em in he p oo o Theo em 3 The componen s Πi,1≤i≤n, simula e he co esponding “componen ” o he g amma G, while Πn+1 is a “synch onize ” o he o he componen s, i akes no