P Sys ems wi h Ac i e Memb anes
and Sepa a ion Rules
Linqiang PAN1,2, Tse en-Onol ISHDORJ2
1Depa men o Con ol Science and Enginee ing
Huazhong Uni e si y o Science and Technology
Wuhan 430074, Hubei, People’s Republic o China
E-mail: [email p o ec ed]
2Resea ch G oup on Ma hema ical Linguis ics
Ro i a i Vi gili Uni e si y
Pl. Impe ial T`a aco 1, 43005 Ta agona, Spain
E-mail: {lp@ ll, se enonol .ishdo j@es udian s}.u .es
Abs ac . The P sys ems a e a class o dis ibu ed pa allel compu ing de ices
o a biochemical ype. In his pape , a new de ini ion o sepa a ion ules in
P sys ems wi h ac i e memb anes is gi en. Unde he new de ini ion, he
e iciency and uni e sali y o P sys ems wi h ac i e memb anes and sepa a ion
ules ins ead o di ision a e in es iga ed.
1 In oduc ion
The P sys ems a e a class o dis ibu ed pa allel compu ing de ices o a biochemical
ype, in oduced in [7], which can be seen as a gene al compu ing a chi ec u e whe e
a ious ypes o objec s can be p ocessed by a ious ope a ions. The a ea s a s om
he obse a ion ha ce ain p ocesses which ake place in he complex s uc u e o li ing
o ganisms can be conside ed as compu a ions. Fo a mo i a ion and de ailed desc ip ion
o a ious P sys em models we e e o [7], [9].
In o mally speaking, in P sys ems wi h ac i e memb anes one uses six ypes o ules:
(a) mul ise ew i ing ules, (b) ules o in oducing objec s in o memb anes, (c) ules
o sending objec s ou o memb anes, (d) ules o dissol ing memb anes, (e) ules o
di iding elemen a y memb anes, and ( ) ules o di iding non-elemen a y memb anes.
Memb ane di ision – inspi ed om cell di ision well-known in biology – is he mos
in es iga ed way o ob aining an exponen ial wo king space in a linea ime, and sol ing
on his basis ha d p oblems, ypically NP-comple e p oblems, in polynomial (o en, linea )
ime. De ails can be ound in [8, 9, 10]. Recen ly, also PSPACE-comple e p oblems we e
a acked in his way (see [13, 2]).
Sepa a ion is also a well known phenomenon o cell biology. Many mac omolecules
a e oo la ge o be anspo ed h ough memb anes by means o esicle o ma ion. This
p ocess can anspo packages o chemicals ou o he cell.
325
By di ision, he wo new memb anes ha e exac ly he same objec s excep o a mos
a pai o di e en objec s; i is also possible ha he wo new memb anes ha e di e en
cha ges. Howe e , in he biological phenomenon o sepa a ion, he wo new memb anes
e ol ed om a memb ane can ha e much di e ence, such as he numbe o objec s. In
[1], sepa a ion ules a e in oduced o P sys ems wi h ac i e memb anes, whe e o each
sepa a ion ule, a di e en subse Uo objec s is de ined o ac i a e he memb ane o
sepa a e, and by Uobjec s a e pu in o he wo new memb anes. In his pape , we gi e a
new de ini ion o sepa a ion ules. In he new de ini ion, o each sepa a ion ule one objec
is used o ac i a e sepa a ion; o all sepa a ion ules a uni o m subse O1o objec s is used
o deno e which memb ane objec s should go. F om his poin o iew, he new de ini ion
is an imp o emen o he de ini ion in [1]. Unde he new de ini ion, he e iciency and
uni e sali y o P sys ems wi h ac i e memb anes and sepa a ion ules ins ead o di ision
a e in es iga ed.
2 P Sys ems wi h Ac i e Memb anes
We assume he eade o be amilia wi h basic elemen s o complexi y heo y and o mal
language heo y, o ins ance, om [6, 12, 11], as well as wi h he basic knowledge o
memb ane compu ing, o ins ance, om [9] (de ails and ecen esul s om memb ane
compu ing can be ound a he web add ess h p://psys ems.disco.unimib.i ). We
only men ion ha RE deno e he amily o ecu si ely enume able languages, and ha o
a amily o languages FL, by P sF L we deno e he amily o Pa ikh se s o languages in
FL; as usual, he Pa ikh mapping associa ed wi h an alphabe Vis deno ed by ΨV.
A P sys em wi h ac i e memb anes (and elec ical cha ges) is a cons uc
Π = (O, H, µ, w1, . . . , wm, R),
whe e:
1. m≥1 ( he ini ial deg ee o he sys em);
2. Ois he alphabe o objec s, whe e O=O1∪O2,O1, O26=∅,O1∩O2=∅;
3. His a ini e se o labels o memb anes;
4. µis a memb ane s uc u e, consis ing o mmemb anes, labeled (no necessa ily in a
one- o-one manne ) wi h elemen s o H;
5. w1, . . . , wma e s ings o e O, desc ibing he mul ise s o objec s placed in he m
egions o µ;
6. Ris a ini e se o de elopmen al ules, o he ollowing o ms:
(a) [ a→ ]e
h,
o h∈H, e ∈ {+,−,0}, a ∈O, ∈O∗
(objec e olu ion ules, associa ed wi h memb anes and depending on he label
and he cha ge o he memb anes, bu no di ec ly in ol ing he memb anes,
in he sense ha he memb anes a e nei he aking pa in he applica ion o
hese ules no a e hey modi ied by hem);
326
(b)a[ ]e1
h→[b]e2
h,
o h∈H, e1, e2∈ {+,−,0}, a, b ∈O
(communica ion ules; an objec is in oduced in he memb ane, possibly modi-
ied du ing his p ocess; also he pola iza ion o he memb ane can be modi ied,
bu no i s label);
(c) [ a]e1
h→[ ]e2
hb,
o h∈H, e1, e2∈ {+,−,0}, a, b ∈O
(communica ion ules; an objec is sen ou o he memb ane, possibly modi ied
du ing his p ocess; also he pola iza ion o he memb ane can be modi ied, bu
no i s label);
(d) [ a]e
h→b,
o h∈H, e ∈ {+,−,0}, a, b ∈O
(dissol ing ules; in eac ion wi h an objec , a memb ane can be dissol ed,
while he objec speci ied in he ule can be modi ied);
(e) [ a]e1
h→[b]e2
h[c]e3
h,
o h∈H, e1, e2, e3∈ {+,−,0}, a, b, c ∈O
(di ision ules o elemen a y memb anes; in eac ion wi h an objec , he mem-
b ane is di ided in o wo memb anes wi h he same label, possibly o di e en
pola iza ions; he objec speci ied in he ule is eplaced in he wo new mem-
b anes by possibly new objec s);
( ) [ [ ]α1
h1. . . [ ]α1
hk[ ]α2
hk+1 . . . [ ]α2
hn]α0
h0
→[ [ ]α3
h1. . . [ ]α3
hk]α5
h0[ [ ]α4
hk+1 ...[ ]α4
hn]α6
h0,
o k≥1, n > k, hi∈H, 0≤i≤n, and α0, . . . , α6∈ {+,−,0}wi h
{α1, α2}={+,−}; i he memb ane wi h he label h0con ains o he mem-
b anes han hose wi h he labels h1, . . . , hnspeci ied abo e, hen hey mus
ha e neu al cha ges in o de o make his ule applicable; hese memb anes a e
duplica ed and hen a e pa o he con en s o bo h new copies o he mem-
b ane h0
(di ision o non-elemen a y memb anes; his is possible only i a memb ane
con ains wo immedia ely lowe memb anes o opposi e pola iza ion, + and −;
he memb anes o opposi e pola iza ions a e sepa a ed in he wo new mem-
b anes, bu hei pola iza ion can change; always, all memb anes o opposi e
pola iza ions a e sepa a ed by applying his ule).
(No e ha , in o de o simpli y he w i ing, in con as o he s yle cus oma y in he
li e a u e, we ha e omi ed he label o he le pa en hesis om a pai o pa en heses which
iden i ies a memb ane.) The ules o ype (a) a e applied in he pa allel way (all objec s
which can e ol e by such a ule should do i ), while he ules o ypes (b),(c),(d),(e),( )
a e used sequen ially, in he sense ha one memb ane can be used by a mos one ule
o hese ypes a a ime. In o al, he ules a e used in he non-de e minis ic maximally
pa allel manne : all objec s and all memb anes which can e ol e, should e ol e. Only
hal ing compu a ions gi e a esul , non-hal ing compu a ions gi e no ou pu .
The sepa a ion ules in oduced in [1] a e o he ollowing o m (wi hou pola iza ions):
(h0) [ O]h→[U]h[O−U]h, o h∈H, U ⊂O.
I pola iza ion is conside ed, hey will be o he o m:
(h) [ O]e1
h→[U]e2
h[O−U]e3
h, o h∈H, U ⊂O.
327
He e, we in oduce a new de ini ion o sepa a ion ules.
(g) [ a]e1
h→[O1]e2
h[O2]e3
h,
o h∈H,e1, e2, e3∈ {+,−,0},a∈O
(sepa a ion ules o elemen a y memb anes; in eac ion wi h an objec , he
memb ane is sepa a ed in o wo memb anes wi h he same label, possibly di -
e en pola iza ion; a he same ime, he objec acan e ol e; he objec s om
O1a e placed in he i s memb ane, hose om O2a e placed in he second
memb ane).
As he ules o ypes (b),(c),(d),(e), and ( ), he ules o ype (g) a e used sequen ially,
in he sense ha one memb ane can be used by a mos one ule o hese ypes a a ime.
I a he same ime a memb ane his sepa a ed, and he e a e objec s in his memb ane
which e ol e by means o ules o ype (a), hen in he wo new memb anes we in oduce
he esul o e olu ion; ha is, we suppose ha i s he e olu ion ules o ype (a) a e
used, changing he objec s, hen sepa a ion is p oduced. O cou se, his p ocess akes one
s ep.
No e he di e ence be ween di ision ule and sepa a ion ule. In di ision ule, excep
o he objec speci ied in he ule is eplaced by wo possibly di e en new objec s, he wo
new memb anes ha e he same copy o objec s. Bu in sepa a ion ule, he new objec s a e
placed in o he wo new memb anes acco ding o O1and O2, hese wo new memb anes
can ha e much di e ence, such as he numbe o objec s.
Fo he di e ence be ween he de ini ions o (g) and (h), see he in oduc ion.
To unde s and wha i means sol ing a p oblem in a uni o m and con luen way, he e
we b ie ly ecall some ela ed no ions. Gi en a decision p oblem X, we say ha i can be
sol ed in polynomial (linea ) ime by ecognizing P sys ems in a uni o m way, i , in o mally
speaking, we can cons uc in polynomial ime a amily o ecognizing P sys ems Πn,n∈N,
associa ed wi h he sizes no ins ances X(n) o he p oblem, such ha he sys em will
always s op in a polynomial (linea , espec i ely) numbe o s eps, sending ou he objec
yes i he ins ance X(n) has a posi i e answe and he objec no i he ins ance X(n) has
a nega i e answe . I he compu a ion o a P sys em is nonde e minis ic, bu all b anches
o a compu a ion e en ually each a unique con igu a ion, hen we say ha he sys em is
con luen .
In he nex sec ion, we will show ha P sys ems wi h sepa a ion ules ins ead o
di ision ules can sol e he SAT p oblem in linea ime in a uni o m and de e minis ic way.
3 Sol ing SAT by P Sys ems wi h Sepa a ion Rules
Theo em 3.1 P sys ems wi h ules o ypes (a),(b),(c), and (g)can sol e SAT in linea
ime in a uni o m and de e minis ic way.
P oo . Le us conside a p oposi ional o mula in he conjunc i e no mal o m:
β=C1∧ · · · ∧ Cm,
Ci=yi,1∨ · · · ∨ yi,li,1≤i≤m, whe e
yi,k ∈ {xj,¬xj|1≤j≤n},1≤i≤m, 1≤k≤li.
The ins ance β( o which he size (m, n) is associa ed) is encoded as a mul ise o e
V(hn, mi) = {xi,j,¯xi,j |1≤i≤m, 1≤j≤n}.
328
The objec xi,j ep esen s he a iable xjappea ing in he clause Ciwi hou nega ion,
and objec ¯xi,j ep esen s he a iable xjappea ing in he clause Ciwi h nega ion. Thus,
he inpu mul ise is
w={xi,j |xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n}
∪ {¯xi,j | ¬xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n}.
Fo gi en (n, m)∈N2, we cons uc a ecognizing P sys em (Π(hn, mi), V (hn, mi),2) wi h:
Π(hn, mi)=(O(hn, mi), H, µ, w1, w2, R),
O(hn, mi) = O1∪O2,
O1={xi,j,¯xi,j,|0≤i≤m, 1≤j≤n} ∪ {ci|1≤i≤m+ 2}
∪ {di|1≤i≤2n+ 2m+ 2}∪{ i,j |0≤i≤m, 1≤j≤n}
∪ {e, , λ, yes,no},
O2={x0
i,j,¯x0
i,j,|0≤i≤m, 1≤j≤n} ∪ {d0
i|1≤i≤n}
∪ { i,j |0≤i≤m, 1≤j≤n}∪{e0},
µ= [ [ ]2]1,
w1=λ, w2=d1,
H={1,2},
and he ollowing ules (we also gi e explana ions abou he use o hese ules):
1. [ di]0
2→[O1]+
2[O2]−
2, 1 ≤i≤n.
In memb ane wi h label 2, when i is “elec ically neu al”, objec dicauses he
memb ane o sepa a e and o choose o a a iable xi, 1 ≤i≤n, bo h alues ue
and alse, in o m o cha ges + and −o he wo c ea ed memb anes wi h he label
2. These ules allow us o ha e 2nin e nal memb anes, in ns eps.
2. [ xi,j →xi,jx0
i,j]0
2, 1 ≤i≤m, 1 ≤j≤n.
[ ¯xi,j →¯xi,j ¯x0
i,j]0
2, 1 ≤i≤m, 1 ≤j≤n.
[di→di+1ed0
i+1e0]0
2, 1 ≤i≤n−1.
A he same ime wi h using he ule o ype (1), he objec s e ol e by ules o ype
(2).
3. [ xi,1→ i,1]+
2, 1 ≤i≤m.
[ ¯xi,1→λ]+
2, 1 ≤i≤m.
[x0
i,1→λ]−
2, 1 ≤i≤m.
[ ¯x0
i,1→ 0
i,1]−
2, 1 ≤i≤m.
The ules o ype (3) y o implemen a p ocess allowing he in e nal memb anes
o encode he assignmen o a a iable and, simul aneously, o check he alue o all
clauses by his assignmen , in such a way ha , i he clause is ue, hen an objec
i,1o 0
i,1will appea in he memb ane. In o he case, he objec encoding he
a iable will disappea .
4. [ xi,j →xi,j−1]+
2, 1 ≤i≤m, 2 ≤j≤n.
[ ¯xi,j →¯xi,j−1]+
2, 1 ≤i≤m, 2 ≤j≤n.
[x0
i,j →xi,j−1]−
2, 1 ≤i≤m, 2 ≤j≤n.
329

[ ¯x0
i,j →¯xi,j−1]−
2, 1 ≤i≤m, 2 ≤j≤n.
The check p ocess desc ibed in he ules o ype (3) is always made wi h espec o
he i s a iable appea ing in he in e nal memb ane. Hence, he ules o ype (4)
ake cha ge o making a cyclic pa h h ough all he a iables o ge ha , ini ially,
he i s a iable is x1, hen x2, and so on.
5. [ e]+
1→[ ]0
1e.
[e0]−
1→[ ]0
1e.
[d0
i→di]−
2, 1 ≤i≤n.
The auxilia y objec s eand e0exi he memb ane changing he pola iza ions o
neu al and he objec d0
iin he memb ane wi h nega i e cha ge e ol es o he
objec di( o he use o he ules o ype (1) and he hi d ules o ype (2)), so ha
he abo e desc ibed gene a ing p ocess o he assignmen s and he encoding o he
sa is ied clauses can cycle.
6. [ i,k → i,k+1 0
i,k+1]0
2, o 1 ≤i≤m, 1 ≤k≤n−1.
[ 0
i,k → i,k+1 0
i,k+1]0
2, o 1 ≤i≤m, 1 ≤k≤n−1.
These ules a e designed o deno e he ac : i clause Ciis sa is ied by he assignmen
encoded by a memb ane, hen he new memb anes ob ained om i by sepa a ion
also sa is y he clause Ci. The second subsc ip o i,k o 0
i,k is used o synch o-
niza ion, which is necessa y, because o he use o objec s i,n and 0
i,n in he ules
o ypes (11), (12), and (13).
7. [ di→di+1]0
2, o n≤i≤2n−2.
[d2n−2→d2n−1c1]0
2.
Th ough he coun e objec s di, he ules o ype (7) con ol he p ocess o synch o-
niza ion o he objec s i,k and 0
i,k in he in e nal memb anes.
8. [ d2n−1]0
2→[ ]+
2d2n−1.
The applica ion o he ules o ype (8) will show ha he sys em is eady o check
which clauses a e ue by he assignmen encoded by an in e nal memb ane.
9. [ di→di+1]0
1, 2n−1≤i≤2n+ 2m+ 1.
The ules o ype (9) supply coun e objec s diin he skin, in such a way ha , i
objec s d2n+2m−1appea , hen hey show he end o he checking o he clauses.
The objec s di, wi h 2n+ 2m≤i≤2n+ 2m+ 2, will con ol he inal s age o he
compu a ion.
10. [ 1,n]+
2→[ ]−
2 1,n.
[ 0
1,n]+
2→[ ]−
2 1,n.
Fo all 2nin e nal memb anes, we check whe he 1,n o 0
1,n is p esen in each
memb ane. I his is he case, hen 1,n o 0
1,n is sen ou o he memb ane whe e i
is p esen (one copy o 1,n o 0
1,n exi s he memb ane whe e i is p esen , he o he
copies will e ol e o 0,n o 0
0,n by he ules o ype (10), which will ne e e ol e
again), changing in his way he pola iza ion o ha memb ane, o nega i e. The
memb anes which do no con ain he objec 1,n o 0
1,n emain posi i e and hey
will no longe e ol e, as no u he ule can be applied o hem.
11. [ i,n → i−1,n]−
2, o 1 ≤i≤n.
[ 0
i,n → 0
i−1,n]−
2, o 1 ≤i≤n.
330
The ules o ype (10) always wo k wi h espec o he objec s 1,n o 0
1,n, The
elabel in he ules o ype (11) akes cha ge o making a cyclic pa h h ough all i,n
and 0
i,n, and e ol es he objec s 1,n o 0
1,n o 0,n o 0
0,n (which will ne e e ol e
again).
12. 1,n[ ]−
2→[ 0,n]+
2.
The objec s 1,n om he skin memb ane e u n o in e nal memb anes wi h nega i e
cha ge, changing o 0,n, and e u ning he pola iza ion o he memb ane o posi i e.
This makes possible he use o ules o ype (10).
No e ha in he skin memb ane he numbe o copies o 1,n is equal o he numbe
o memb anes wi h nega i e cha ge; hus, because o pa allelism, each memb ane
which p e iously con ained objec s 1,n o 0
1,n will now con ain an objec 0,n.
13. [ ci→ci+1]−
2, 1 ≤i≤m.
The p esence o objec ci(wi h 2 ≤i≤m+ 1) in he in e nal memb ane shows ha
he assignmen makes he i s i−1 clauses ue.
14. [ cm+1]+
2→[ ]+
2cm+1.
The p esence o he objec cm+1 shows ha all clauses a e sa is ied by he assignmen
encoded by an in e nal memb ane. The ule o ype (14) sends o he skin he objec s
cm+1 appea ing in he in e nal memb anes.
15. [ cm+1 →cm+2 ]0
1.
The objec s cm+1 in he skin e ol e o objec s cm+2 . The objec s in he skin a e
p oduced simul aneously wi h he appea ance o he objec s d2n+2m+1 in he skin,
and hey will be used o ou pu he compu ing esul .
16. [ ]0
1→[ ]+
1 .
The ule o ype (16) sends ou o he sys em an objec changing he pola iza ion
o he skin o posi i e, hen objec s emaining in he skin a e no able o e ol e.
Then by ule o ype (17), he objec cm+2 can exi he skin p oducing an objec
yes, elling us ha he o mula is sa is iable, and he compu a ion hal s.
17. [ cm+2]+
1→[ ]−
1yes.
The applica ion o he ule o ype (17) changes he pola iza ion in he skin mem-
b ane o nega i e in o de ha he objec s cm+2 emaining in i a e no able o
con inue e ol ing.
18. [ d2n+2m+2]0
1→[ ]+
1no.
By he ule (18) he objec d2n+2m+2 only e ol es when he skin has neu al cha ge
( his is he case when he o mula is no sa is iable). Then he sys em will e ol e
sending ou o he en i onmen an objec no and changing he pola iza ion o he
skin o posi i e, in o de ha objec s d2n+2m+2 emaining in he skin, do no e ol e.
F om he p e ious explana ion o he use o ules, one can easily see how his P
sys em wo ks. I is clea ha he objec yes is sen o he en i onmen i and only
i he o mula βis sa is iable. This is achie ed in 3n+ 2m+ 4 s eps: in 2ns eps we
c ea e 2nin e nal memb anes (as well as he 2ndi e en u h-assignmen s), hen ns eps
o synch oniza ion; i akes 2ms eps o check whe he all clauses a e sa is ied by an
assignmen ; u he 4 s eps a e necessa y o ou pu he compu ing esul yes. I o mula
331
βis no sa is iable, hen a s ep 3n+ 2m+ 4 he sys em sends he objec no o he
en i onmen . The e o e, he amily o memb ane sys ems we ha e cons uc ed is sound,
con luen , and linea ly e icien .
To p o e ha he amily is uni o m, we ha e o show ha o a gi en size, he con-
s uc ion o P sys ems desc ibed in he p oo can be done in polynomial ime by a Tu ing
machine. We omi he de ailed cons uc ion due o he ac ha i is s aigh o wa d bu
cumbe some as explained in he p oo o Theo em 7.2.3 in [9] (al hough P sys ems in [9]
a e semi-uni o m). So SAT p oblem was decided in linea ime (3n+2m+2) by ecognizing
ac i e P sys ems wi h sepa a ion ule in a uni o m way, and his concludes he p oo . 2
4 Remo ing Pola iza ions
Following he idea in [3, 4], le us conside now ules o ypes (a)−(e) and (g) wi hou
pola iza ions. They a e o he ollowing o ms (because “no pola iza ion” means “neu al
pola iza ion”, we add he subsc ip 0 o he p e ious le e s iden i ying he six ypes o
ules; as abo e, O=O1∪O2is he alphabe o objec s and His he se o labels o
memb anes):
(a0) [ a→ ]h, whe e a∈O, ∈O∗, and h∈H,
(b0)a[ ]h→[b]h, whe e a, b ∈Oand h∈H,
(c0) [ a]h→[ ]hb, whe e a, b ∈Oand h∈H,
(d0) [ a]h→b, whe e a, b ∈Oand h∈H,
(e0) [ a]h→[b]h[c]h, whe e a, b, c ∈Oand h∈H,
(g0) [ a]h→[O1]h[O2]h, o h∈H,a∈O.
Rules o ypes (b),(c),(e),(g) in Sec ion 2 we e in oduced wi hou he capabili y o
changing he label o memb anes hey in ol e ( his makes no sense o dissol ing ules),
bu in [9] one al eady conside s ules o ype (e) which can change bo h he label and he
pola iza ion o memb anes. Such ules a e o he o m
[a]e1
h1→[b]e2
h2[c]e3
h3,wi h a, b, c ∈O, e1, e2, e3∈ {+,−,0},and h1, h2, h3∈H,
and hey ha e been called o ype (e0). We ex end his idea and his no a ion o ules o
ypes (b0), (c0), (e0), (g0): hei p imed e sions indica e he ac ha he labels can be
changed. Speci ically, hese ules a e o he ollowing o ms:
(b0
0)a[ ]h1→[b]h2, whe e a, b ∈Oand h1, h2∈H,
(c0
0) [ a]h1→[ ]h2b, whe e a, b ∈Oand h1, h2∈H,
(e0
0) [ a]h1→[b]h2[c]h3, whe e a, b, c ∈Oand h1, h2, h3∈H,
(g0
0) [ a]h1→[O1]h2[O2]h3, o h1, h2, h3∈H,a∈O.
In he ollowing, we conside he e iciency and uni e sali y o ac i e P sys ems wi hou
pola iza ion wi h sepa a ion ules ins ead o di ision.
332
4.1 E iciency
Theo em 4.1 P sys ems wi h ules o ypes (a0),(b0),(c0),(g0
0)can sol e SAT in linea
ime in a uni o m and con luen way.
P oo . Le us conside a p oposi ional o mula in he conjunc i e no mal o m:
β=C1∧ · · · ∧ Cm,
Ci=yi,1∨ · · · ∨ yi,li,1≤i≤m, whe e
yi,k ∈ {xj,¬xj|1≤j≤n},1≤i≤m, 1≤k≤li.
The ins ance β( o which he size (m, n) is associa ed) is encoded as a mul ise o e
V(hn, mi) = {xi,j,¯xi,j |1≤i≤m, 1≤j≤n}.
The objec xi,j ep esen s he a iable xjappea ing in he clause Ciwi hou nega ion,
and objec ¯xi,j ep esen s he a iable xjappea ing in he clause Ciwi h nega ion. Thus,
he inpu mul ise is
w={xi,j |xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n}
∪ {¯xi,j | ¬xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n}.
Fo gi en (n, m)∈N2, we cons uc a ecognizing P sys em (Π(hn, mi), V (hn, mi),2) wi h:
Π(hn, mi)=(O(hn, mi), H, µ, w1, w2, w7, R),
O(hn, mi) = O1∪O2,
O1={xi,j,¯xi,j |1≤i≤m, 0≤j≤n}∪{di|0≤i≤2n+ 2m+ 6}
∪ {ci|1≤i≤m} ∪ {λ, e, 0, 1,yes,no},
O2={x0
i,j,¯x0
i,j |1≤i≤m, 0≤j≤n}∪{d0
i|0≤i≤n−1}
∪ {c0
i|1≤i≤m},
µ= [ [ ]2[ ]7]1,
w1=λ, w2=w7=d0,
H={0,1,2,3,4,5,6,7},
and he ollowing ules (we also gi e explana ions abou he use o hese ules):
Gene a ion phase
G1 [ di]2→[O1]3[O2]4, 0 ≤i < n.
[di→did0
i]2, 0 ≤i < n.
G2 [ di]3→[O1]2[O2]0, 0 ≤i < n.
[di→di+1d0
0]3, 0 ≤i < n.
G3 [ d0
i]4→[O1]2[O2]0, 0 ≤i < n.
[d0
i→di+1d0
0]4, 0 ≤i < n.
G4 [ dn]2→[O1]5[O2]0.
[dn→d0d0
0]2.
333
8. [ A→#] , o all A∈N2.
9. [ # →#]h, o all h∈H.
10. [ a] →[ ] a.
11. [ a]1→[ ]1a, o all a∈T.
The equali y ΨT(L(G)) = Ps(Π) easily ollows om he abo e explana ions. 2
Rema k 4.1 In he abo e p oo , he ules o ype (c0)a e only used o sending he esul
o a compu a ion ou o he sys em. The e o e, ules o ypes (a0)and (g0
0)a e su icien
o each uni e sali y o memb ane sys ems wi h in e nal ou pu .
5 Final Rema k
In his pape , sepa a ion is in oduced in o ac i e P sys ems, and he e iciency and uni-
e sali y o ac i e P sys ems wi h sepa a ion ules ins ead o di ision a e in es iga ed.
The uni e sali y esul is ob ained by a di ec p oo . I s ill emains open using P sys ems
wi h sepa a ion ules o simula e P sys ems wi h di ision ules.
Acknowledgemen s. The au ho s acknowledge IST-2001-32008 p ojec “MolCoNe ”.
The i s au ho (he is also he co esponding au ho ) is also suppo ed by g an DGU-
SB2001-0092 om Spanish Minis y o Educa ion, Cul u e, and Spo , Na ional Na u al
Science Founda ion o China (G an No. 60373089), and Huazhong Uni e si y o Science
and Technology Founda ion. The second au ho acknowledges The S a e T aining Fund
o he Minis y o Science, Technology, Educa ion and Cul u e o Mongolia.
Re e ences
[1] A. Alhazo , T.-O. Ishdo j, Memb ane Ope a ions in P Sys ems wi h Ac i e Mem-
b anes, Manusc ip ci cula ed du ing he Second B ains o ming Week on Memb ane
Compu ing, Se illa, Spain, Feb. 2-7, 2004.
[2] A. Alhazo , C. Ma ´ın-Vide, L. Pan, Sol ing a PSPACE-Comple e P oblem by P
Sys ems wi h Res ic ed Ac i e Memb anes, Fundamen a In o ma icae, 58, 2 (2003),
66–77.
[3] A. Alhazo , L. Pan, Pola iza ionless P Sys ems wi h Ac i e Memb anes, G amma s,
7, 1 (2004).
[4] A. Alhazo , L. Pan, Gh. P˘aun, T ading Pola iza ions o Labels in P Sys ems wi h
Ac i e Memb anes, submi ed 2003.
[5] J. Dassow, Gh. P˘aun, Regula ed Rew i ing in Fo mal Language Theo y, Sp inge -
Ve lag, Be lin, 1989.
[6] Ch. P. Papadimi iou, Compu a ional Complexi y, Addison-Wesley, Reading, MA,
1994.
[7] Gh. P˘aun, Compu ing wi h Memb anes, Jou nal o Compu e and Sys em Sciences,
61, 1 (2000), 108–143,
340

[8] Gh. P˘aun, P Sys ems wi h Ac i e Memb anes: A acking NP-Comple e P oblems,
Jou nal o Au oma a, Languages and Combina o ics, 6, 1 (2001), 75–90.
[9] Gh. P˘aun, Compu ing wi h Memb anes: An In oduc ion, Sp inge -Ve lag, Be lin,
2002.
[10] M.J. P´e ez-Jim´enez, A. Rome o-Jim´enez, F. Sancho-Capa ini, Teo ´ıa de la Comple-
jidad en Modelos de Compu a i´on Celula con Memb anas, Edi o ial K onos, Se illa,
2002.
[11] G. Rozenbe g, A. Salomaa, eds., Handbook o Fo mal Languages (3 olumes),
Sp inge -Ve lag, Be lin, 1997.
[12] A. Salomaa, Fo mal Languages, Academic P ess, New Yo k, 1973.
[13] P. Sos´ık, Sol ing a PSPACE-Comple e P oblem by P Sys ems wi h Ac i e Mem-
b anes, P oceedings o he B ains o ming Week on Memb ane Compu ing (M. Ca a-
lie e, C. Ma ´ın-Vide, and Gh. P˘aun, eds.), Repo GRLMC 26/03, 2003, 305–312.
341