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