A P olog Simula o o De e minis ic P
Sys ems wi h Ac i e Memb anes
A. CORD´
ON-FRANCO, M.A. GUTI´
ERREZ-NARANJO,
M.J. P´
EREZ-JIM´
ENEZ, F. SANCHO-CAPARRINI
Dp o. de Ciencias de la Compu aci´on e In eligencia A i icial
E.T.S. Ingenie ´ıa In o m´a ica. Uni e sidad de Se illa
A da. Reina Me cedes s/n, 41012, Se illa, Espa˜na
{aco don, magu ie , ma pe , sancho}@us.es
Abs ac In his pape we p opose a new way o ep esen P sys ems
wi h ac i e memb anes based on Logic P og amming echniques. This
ep esen a ion allows us o exp ess he se o ules and he con igu a ion o
he P sys em in each s ep o he e olu ion as li e als o an app op ia e
language o i s o de logic. We p o ide a P olog p og am o simula e he
e olu ion o hese P sys ems and p esen some auxilia y ools o simula e
he e olu ion o a P sys em wi h ac i e memb anes using 2-di ision which
sol es he SAT p oblem ollowing he echniques p esen ed in 10).
Keywo ds Logic p og amming, Memb ane compu ing, Simula ion,
P olog, SAT-p oblem
§1 In oduc ion
In 5), a new model o compu a ion wi hin he amewo k o Na u al
Compu ing was in oduced, called P Sys ems.
I is based upon he no ion o memb ane s uc u e ha is used o enclose
compu ing cells in o de o make hem independen compu ing uni s. Also, a
memb ane se es as a communica ion channel be ween a gi en cell and o he
cells “adjacen ” o i . This model comes om he obse a ion ha he p ocesses
2A. Co d´on-F anco e al.
which ake place in he complex s uc u e o a li ing cell can be conside ed as
compu a ions.
Since hese compu ing de ices we e in oduced se e al a ian s ha e
been conside ed. See 6) o a ai ly comple e compendium abou P sys ems.
The di e en a ian s o P sys ems ound in he li e a u e a e gene ally
hough as gene a ing de ices. Many o hem ha e been p o ed o be compu a-
ionally comple e 6).
The model we s udy he e, P sys ems wi h ac i e memb anes, wo ks wi h
symbol–objec s, and i p o ides ules o memb ane di ision. In pa icula , P
sys ems wi h ac i e memb anes a e s udied in 6), sec ion 7.2.
The main goal o his pape is o p opose and illus a e a ep esen a ion
o P sys ems wi h ac i e memb anes based on Logic P og amming echniques.
The pape is o ganized as ollows: Sec ion 2 b ie ly p esen s some ideas
abou he con enience o using P olog as he basis o his ep esen a ion; Sec ion
3 in oduces he way o ep esen all basic ing edien s o his model; Sec ion 4
s udies he designed algo i hm o simula e de e minis ic P sys ems wi h ac i e
memb anes; Sec ion 5 p esen s as an example he solu ion gi en o SAT p oblem
using his model in 10); Sec ion 6 p esen s some conclusions and u u e wo k
abou he possibili ies o his new simula o and ep esen a ion echniques using
Logic P og amming; inally, he Appendix shows a s anda d wo k session wi h
he in e ace p o ided wi h he simula o .
§2 Why P olog?
Choosing a p og amming language o an e ec i e implemen a ion o a
P sys em simula o is no an easy decision. The language has o be exp essi e
enough o handle symbolic knowledge in a na u al way and he abili y o e ol ing
he di e en con igu a ions ollowing a se o ules. P olog∗1has bo h hese
ea u es.
On one hand, he based- ee da a s uc u e and he use o in ix ope a o s
de ined ad hoc by he p og amme allow us o simula e he na u al language and
he use can ollow he e olu ion o he sys em wi hou any knowledge o P olog
(see sec ions 3.2 and 3.3). On he o he hand, P olog p og ams a e se s o ac s
and ules and basic mechanisms o P olog a e pa e n ma ching and au oma ic
back acking, so he design o he in e ence engine o pe o m he e olu ions has
a na u al ea men om a p og amme poin o iew.
∗1A good s a ing poin can be 3) o 13).
A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes 3
Finally, he use o P olog as p og amming language has o he desi able
side e ec s which a e ou o he scope o his pape . P olog i s in o all kinds
o symbolic easoning and he use o his ep esen a ion can be a way o link P
sys ems o o he deeply s udied ields in A i icial In elligence.
§3 A Logic P og amming ep esen a ion o P
sys ems wi h ac i e memb ane
Following 6) aP sys em wi h ac i e memb anes is a cons uc :
Π = (V, H, µ, w1, . . . , wm, R),
whe e:
1. m≥1, is he ini ial deg ee o he sys em;
2. Vis he alphabe o symbol-objec s;
3. His a ini e se o labels o memb anes;
4. µis a memb ane s uc u e, o mmemb anes, labelled (no necessa ily
in a one- o-one manne ) wi h elemen s o H;
5. w1, . . . , wma e s ings o e V, desc ibing he ini ial mul ise s o objec s
placed in he m egions o µ;
6. Ris a ini e se o e olu ion ules, o he ollowing o ms:
a. [hx→u]α
h, o h∈H,α∈ {+,−,0},x∈V,u∈V∗. This is an
objec e olu ion ule, associa ed wi h a memb ane labelled wi h h
and depending on he pola i y o ha memb ane, bu no di ec ly
in ol ing he memb ane.
b. x[h]α1
h→[hy]α2
h, o h∈H,α1, α2∈ {+,−,0},x, y ∈V. An objec
om he egion immedia ely ou side a memb ane labelled wi h h
is in oduced in his memb ane, possibly ans o med in o ano he
objec , and simul aneously i s pola i y can be changed.
c. [hx]α1
h→[h]α2
hy, o h∈H,α1, α2∈ {+,−,0},x, y ∈V. An objec
is sen ou om memb ane labelled wi h h o he egion immedia-
ely ou side, possibly ans o med in o ano he objec , and simul a-
neously he pola i y o he memb ane can be changed.
d. [hx]α
h→y, o h∈H,α∈ {+,−,0},x, y ∈V. A memb ane labelled
wi h his dissol ed in eac ion wi h an objec . The skin is ne e
dissol ed.
e. [hx]α1
h→[hy]α2
h[hz]α3
h, o h∈H,α1, α2, α3∈ {+,−,0},x, y, z ∈V.
An elemen a y memb ane can be di ided in o wo memb anes wi h
4A. Co d´on-F anco e al.
he same label, possibly ans o ming some objec s and pola i y.
These ules a e applied acco ding o he ollowing p inciples:
•All he ules a e applied in pa allel and in a maximal manne . In one
s ep, one objec o a memb ane can be used by only one ule (chosen in
a nonde e minis ic way), bu any objec which can e ol e by one ule o
any o m, should e ol e.
•I a memb ane is dissol ed, hen i s con en (mul ise and in e nal mem-
b anes) is le ee in he su ounding egion.
•All objec s and memb anes no speci ied in a ule and which do no e ol e
emain unchanged o he nex s ep.
•I a he same ime a memb ane his di ided by a ule o ype (e) and
he e a e objec s in his memb ane which e ol e by means o ules o ype
(a), hen we suppose ha i s he e olu ion ules o ype (a) a e used,
and hen he di ision is p oduced. O cou se, his p ocess akes only one
s ep.
•The ules associa ed wi h memb anes labelled wi h ha e used o all
copies o his memb ane. A one s ep, a memb ane labelled wi h hcan
be he subjec o only one ule o ypes (b)-(e).
In o de o gi e a o mal ep esen a ion in P olog o he basic s uc u es o P
sys ems wi h ac i e memb anes using 2-di ision, he ollowing ep esen a ion
will be conside ed.
3.1 Rep esen a ion o memb ane s uc u es
A gi en con igu a ion will be exp essed by means o a labelled ee,
whe e:
1. < > is he posi ion o deno e he oo o he ee and i will be associa-
ed o he skin;
2. i < i1, . . . , in>is he posi ion o a memb ane h, hen < i, i1, . . . , in>
will deno e he posi ion o he i- h in e nal memb ane o h.
The e exis s one di e ence be ween he abo e ep esen a ion and he one we
use in P olog: in ou P olog ep esen a ion, i in one s ep o he compu a ion a
memb ane wi h label < i1, . . . , in>has kin e nal memb anes, hen i s child en
do no ha e o be labelled wi h <1, i1, . . . , in>,<2, i1, . . . , in>,. . . ,< k −1,
i1, . . . , in>,< k, i1, . . . , in>.
This is because i one child memb ane is dissol ed, he o he ones a e no e-
A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes 5
labelled. Besides, new memb anes ob ained by di ision a e labelled wi h new
indexes, no by illing he holes o p e iously dissol ed memb anes.
3.2 Rep esen a ion o con igu a ions
Le us emembe ha o gi e a con igu a ion o a P sys em wi h ac i e
memb anes consis s in making explici he memb ane s uc u e and he con en
o e e y memb ane p esen in his s uc u e.
In ou model we will ep esen he con igu a ion in one s ep o he e o-
lu ion as a se o one-li e al clauses, each o hem ep esen ing each ali e mem-
b ane. Hence, in his ep esen a ion each clause will show he label, posi ion,
pola i y, mul ise o objec s and cu en s ep o he compu a ion, as well as he
P sys em his memb ane belongs o. In his way, he se o clauses gi es in o -
ma ion abou he con en s o he memb anes and he memb ane s uc u e (by
means o he posi ion o each one).
In a gene al o m, o deno e ha in he - h s ep o i s e olu ion he P
sys em, P, has a memb ane a posi ion [pos] wi h label h, pola i y αand mas
mul ise , we will w i e
P:: hec αa [pos]wi h ma ime
No e ha we can use he use - iendly ep esen a ion o a P olog li e al, ins ead
o he unc ional ep esen a ion.
In a gene al way, i m={{x1, . . . , xn}} (wi h no necessa ily xi6=xj),
hen we will deno e m= [x1, . . . , xn].
3.3 Desc ip ion o he ules
By means o some new unc ion symbols, he ules a e also ep esen ed
as li e als. In wha ollows we p esen he gene al o m o he di e en ules
showed abo e:
(a) [hx→u]α
h
P ule xe ol es o [u]in hec α
(b) x[h]α1
h→[hy]α2
h
P ule xou o hec α1sends in yo hec α2
(c) [hx]α1
h→[h]α2
hy
P ule xinside o hec α1sends ou yo hec α2
(d) [hx]α
h→y
P ule xinside o hec αdissol es and sends ou y

6A. Co d´on-F anco e al.
(e) [hx]α1
h→[hy]α2
h[hz]α3
h
P ule xinside o hec α1di ides in o yinside o h
ec α2and zinside o hec α3
§4 The algo i hm
The P olog algo i hm o simula e a P sys em wo ks in a na u al way.
The inpu o he p og am is he ini ial con igu a ion o he memb anes (which
is ep esen ed as a se o li e als wi h p edica e symbol **, all o hem a ime
0) and an app op ia e se o ules.
•S ep 1: Ini ializa ion. A he beginning, all he memb anes a e se
o applicable and hei objec s a e spli in o wo mul ise : one usable
mul ise , con aining all he objec s o he ini ial memb ane, and one used
mul ise which is emp y.
•S ep 2: T ansi ion. I he e exis s an applicable memb ane sa is ying
he condi ion o a ule, hen he ule is applied in he ollowing way:
– (a)-s ep: A his s age, only ules o ype (a) a e checked. The ob-
jec which igge s he ule is emo ed om he usable and he esul
mul ise by he applica ion o he ule is added o used, o p e en
ha he same objec is used by wo di e en ules a he same s ep.
A e he e olu ion s ep, he memb ane emains o be applicable and
new e olu ion ules can be applied.
This s age ends when no mo e ules o ype (a) can be applied.
– Non-(a)-s ep: A his s age, only one ule o he o he ypes (no (a))
can be applied. Le us emembe ha his simula ion only wo ks wi h
de e minis ic P sys ems (in ac , i wo ks wi h con luen ones). The
ac ion depends on he kind o ule o apply:
∗Send ou ule: The elemen which igge s he ule is emo ed om
usable mul ise and he new one is added o he used mul ise o
he a he memb ane. Bo h memb anes changes o no applicable
mode. I he elemen is sen ou o he skin, hen i is ma ked wi h
he p ope y ou side.
∗Send in ule: I is he ecip ocal o he p e ious one. The ele-
men which igge s he ule is emo ed om usable in he a he
memb ane and he new one is added o he used mul ise . Bo h
memb anes changes o no applicable mode.
∗Dissolu ion ule: The elemen which igge s he ule belongs o
A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes 7
usable and he new elemen ob ained oge he wi h he es o he
elemen s o he memb ane a e added o he used mul ise o he
a he memb ane. When a memb ane mis dissol ed, i s inne mem-
b anes (i.e. i s child en) become child en o he a he memb ane o
min he nex s age o e olu ion. Fo ha , he new posi ions ha e o
be a anged. The a he memb ane changes o no applicable mode.
∗Di ision ule: The elemen which igge s he ule belongs o us-
able and he di ision c ea es wo new memb anes in no applicable
mode. One o hem keeps he o iginal posi ion and he second one
ge s a posi ion which has no been occupied by any memb ane.
– End: When no mo e ules can be applied o applicable memb anes, a
new con igu a ion (wi h a ime inc emen ed by 1) is s o ed. In his
momen no memb ane has applicable o no applicable s a e. These
modes only ha e alidi y du ing he e olu ion. A his s age, he P
sys em is eady o a new s ep o he e olu ion.
•S ep 3: End o compu a ion. The e olu ion o he P sys em inishes
when he e a e no ules o be applied.
No ice ha due o he ea u es o he implemen a ion, he p og am
only ensu es a co ec simula ion o he e olu ion o de e minis ic (con luen )
P sys ems. Ne e heless, mos o he usual algo i hms ha sol e in e es ing
p oblems a e co e ed.
§5 A s udy case: SAT p oblem
5.1 A linea solu ion o he SAT p oblem by P sys ems
wi h ac i e memb anes
P oposi ional Sa is iabili y is he p oblem o de e mining, o a o mula
o he p oposi ional calculus, i he e is an assignmen o u h alues o i s
a iables o which ha o mula e alua es o ue. By SAT we mean he p oblem
o p oposi ional sa is iabili y o o mulas in conjunc i e no mal o m (CNF).
Following 10) we p esen a amily o ecognizing P sys ems wi h ac i e
memb anes using 2–di ision (see 6), sec ion 7.2) sol ing he SAT p oblem in
linea ime.
Le us suppose ha ϕ=C1∧· · ·∧Cmin CNF and V a (ϕ) = {x1, . . . , xn}.
Fo each (m, n)∈N2we conside he ecognizing P sys em
(Π(hm, ni),Σ(m, n), i(m, n)),
8A. Co d´on-F anco e al.
whe e Σ(m, n) = {xi,j, xi,j : 1 ≤i≤m, 1≤j≤n},i(m, n) = 2 and
Π(hn, mi) = (Γ(m, n),{1,2},[1[2]2]1, w1, w2, R)
is de ined as ollows:
Γ(m, n) = Σ(m, n)∪ {ck: 1 ≤k≤m+ 2}∪{dk: 1 ≤k≤3n+ 2m+ 3}
∪ { i,k : 0 ≤i≤m, 1≤k≤2n} ∪ {e, }∪{Y es, No}.
We will say ha e e y in e nal memb ane wi h label 2 is an in e nal memb ane.
The ini ial con en o each memb ane is: w1=∅and w2={d1}.
The se Ro ules is gi en by:
(a){[2dk]0
2→[2dk]+
2[2dk]−
2: 1 ≤k≤n}.
By using a ule o (a), a memb ane wi h label 2 is di ided in o wo
memb anes wi h he same label, bu wi h di e en pola iza ions. These
ules allow us o duplica e, in one s ep, he o al numbe o in e nal
memb anes.
(b){[2xi,1→ i,1]+
2,[2xi,1→ i,1]−
2: 1 ≤i≤m},
{[2xi,1→λ]−
2,[2xi,1→λ]+
2: 1 ≤i≤m}.
The ules o (b) y o implemen a p ocess allowing o he in e nal mem-
b 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,1will appea in he memb ane. In o he
case, he objec encoding he a iable will disappea .
(c){[2xi,j →xi,j−1]+
2,[2xi,j →xi,j−1]−
2: 1 ≤i≤m, 2≤j≤n},
{[2xi,j →xi,j−1]+
2,[2xi,j →xi,j−1]−
2: 1 ≤i≤m, 2≤j≤n}.
The check p ocess desc ibed p e iously 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 (c) 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.
(d){[2dk]+
2→[2]0
2dk, , [2dk]−
2→[2]0
2dk: 1 ≤k≤n},
{dk[2]0
2→[2dk+1]0
2: 1 ≤k≤n−1}.
The ules o (d) a e used as con olle s o he gene a ing p ocess o he
assignmen s and he encoding o he sa is ied clauses: he objec s da e
sen ou o he skin a he same ime he checking is made and hey come
back o he in e nal memb anes o s a he di ision o hese memb anes.
(e){[2 i,k → i,k+1]0
2: 1 ≤i≤m, 1≤k≤2n−1}.
A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes 9
The use o objec s in he ules (i), (j) and (k) makes necessa y o
pe o m a o a ion o hese objec s. This is he mission o he ules
o (e).
( ){[1dk→dk+1]0
1:n≤k≤3n−3}; [1d3n−2→d3n−1e0]0
1.
Th ough he coun e -objec s d, he ules o ( )con ol he o a ion o he
elemen s i,k in he in e nal memb anes.
(g)e[2]0
2→[2c1]+
2; [1d3n−1→d3n]0
1.
The applica ion o he ules o (g) will show ha he sys em is eady
o check which clauses a e made ue by he assignmen encoded by an
in e nal memb ane.
(h){[1dk→dk+1]0
1: 3n≤k≤3n+ 2m+ 2}.
The ules o (h) supply coun e s in he skin h ough objec s d, in such a
way ha , i objec s d3n+2mappea , hen hey show he end o he checking
o he clauses. The objec s dk, wi h 3n+ 2m+ 1 ≤k≤3n+ 2m+ 3, will
con ol he inal s age o he compu a ion.
(i) [2 1,2n]+
2→[2]−
2 1,2n.
The applicabili y o he ule (i) encodes he ac ha an in e nal mem-
b ane makes ue he clause ep esen ed by he objec 1,2n, h ough a
change in he sign o i s pola iza ion. Because o his, we mus elabel he
alues o ep esen ing he di e en in e nal memb anes. This is done
by means o he ules (j).
(j){[2 i,2n→ i−1,2n]−
2: 1 ≤i≤m}.
(k) 1,2n[2]−
2→[2 0,2n]+
2.
By using he ule (k) he ask o making explici he assignmen s ha
make ue he clause encoded in ha momen o he execu ion by he
objec 1,2nis ended.
(l){[2ck→ck+1]−
2: 1 ≤k≤m}.
The p esence o objec s ck(wi h 2 ≤k≤m+ 1) in he in e nal mem-
b anes shows ha he assignmen s making ue e e y clause a e being
de e mined.
(m) [2cm+1]+
2→[2]+
2cm+1.
16 A. Co d´on-F anco e al.
13) Logic P og amming: h p://www.a m.sbu.ac.uk/logic-p og/
§7 Appendix
In wha ollows we p esen a sample o he ules w i en in he o ma
hey mus be gi en o he simula o ∗3.
% Se (a)
p1 ule d1 inside_o e2 ec 0 di ides_in o d1 inside_o
e2 ec 1 and d1 inside_o e2 ec-1 ** 1.
p1 ule d2 inside_o e2 ec 0 di ides_in o d2 inside_o
e2 ec 1 and d2 inside_o e2 ec-1 ** 2.
% Se (b)
p1 ule x1_1 e ol es_ o [ 1_1]in e2 ec 1 ** 3.
p1 ule z1_1 e ol es_ o [ 1_1]in e2 ec-1 ** 4.
...
% Se (c)
p1 ule x1_2 e ol es_ o [x1_1]in e2 ec 1 ** 11.
p1 ule x1_2 e ol es_ o [x1_1]in e2 ec-1 ** 12.
p1 ule z1_2 e ol es_ o [z1_1]in e2 ec 1 ** 13.
...
% Se (d)
p1 ule d1 inside_o e2 ec 1 sends_ou d1 o e2 ec 0 ** 19.
p1 ule d1 inside_o e2 ec -1 sends_ou d1 o e2 ec 0 ** 20.
...
% Se (e)
p1 ule 1_1 e ol es_ o [ 1_2] in e2 ec 0 ** 24.
p1 ule 1_2 e ol es_ o [ 1_3] in e2 ec 0 ** 25.
...
% Se ( )
p1 ule d2 e ol es_ o [d3] in e1 ec 0 ** 30.
p1 ule d3 e ol es_ o [d4] in e1 ec 0 ** 31.
p1 ule d4 e ol es_ o [d5, e] in e1 ec 0 ** 32.
% Se (g)
p1 ule e ou _o e2 ec 0 sends_in c1 in o e2 ec 1 ** 33.
p1 ule d5 e ol es_ o[d6]in e1 ec 0 ** 34.
% Se (h)
∗3The numbe a e ** is he o dinal associa ed o he ule.

A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes 17
p1 ule d6 e ol es_ o [d7] in e1 ec 0 ** 35.
...
p1 ule d12 e ol es_ o [d13]in e1 ec 0 ** 41.
% Se (i)
p1 ule 1_4 inside_o e2 ec 1 sends_ou 1_4 o e2 ec-1 ** 42.
% Se (j)
p1 ule 1_4 e ol es_ o [ 0_4] in e2 ec -1 ** 43.
p1 ule 2_4 e ol es_ o [ 1_4] in e2 ec -1 ** 44.
% Se (k)
p1 ule 1_4 ou _o e2 ec-1 sends_in 0_4 in o e2 ec 1 ** 45.
% Se (l)
p1 ule c1 e ol es_ o [c2] in e2 ec -1 ** 46.
p1 ule c2 e ol es_ o [c3] in e2 ec -1 ** 47.
% Se (m)
p1 ule c3 inside_o e2 ec 1 sends_ou c3 o e2 ec 1 ** 48.
% Se (n)
p1 ule c3 e ol es_ o [c4, ] in e1 ec 0 ** 49.
% Se (o)
p1 ule inside_o e1 ec 0 sends_ou o e1 ec 1 ** 50.
% Se (p)
p1 ule c4 inside_o e1 ec 1 sends_ou yes o e1 ec-1 ** 51.
% Se (q)
p1 ule d13 inside_o e1 ec 0 sends_ou no o e1 ec 1 ** 52.