Tissue-like P Sys ems wi h Channel-S a es
Rudol FREUND1, Gheo ghe P ˘
AUN2,3, Ma io J. P´
EREZ JIM´
ENEZ3
1Facul y o Compu e Science
Vienna Uni e si y o Technology
Fa o i ens . 9–11, A–1040 Vienna, Aus ia
E-mail: [email p o ec ed]
2Ins i u e o Ma hema ics o he Romanian Academy
PO Box 1-764, 014700 Bucu e¸s i, Romania
3Resea ch G oup on Na u al Compu ing
Depa 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
E-mail: {gpaun,ma pe }@us.es
Abs ac . We conside issue-like P sys ems wi h s a es associa ed wi h he
links (we call hem synapses) be ween cells, con olling he passage o objec s
ac oss he links. We in es iga e he compu ing powe o such de ices o he
case o using – in a sequen ial manne – an ipo ules o small weigh s. Sys-
ems wi h wo cells a e p o en o be uni e sal when ha ing a bi a ily many
s a es and minimal an ipo ules, o wo s a es, and an ipo ules o weigh
wo. Also he sys ems wi h a bi a ily many cells, h ee s a es, and minimal
an ipo ules a e uni e sal. In con as , he sys ems wi h one cell and any
numbe o s a es and ules o any weigh only compu e Pa ikh se s o ma-
ix languages (gene a ed by ma ix g amma s wi hou appea ance checking);
cha ac e iza ions o Pa ikh images o ma ix languages a e ob ained o such
one-cell sys ems wi h an ipo ules o a educed weigh . A se ies o open
p oblems a e also o mula ed.
1 In oduc ion
In memb ane compu ing a ea he e a e wo main classes o sys ems: cell-like and issue-
like P sys ems. The o me ype is inspi ed om he cell o ganiza ion (and has memb anes
hie a chically a anged, hence co esponding o a ee), he la e one mimics he “collab-
o a ion” o cells om issues o a ious kinds (hence co esponds o memb anes placed in
he nodes o an a bi a y g aph).
Ac ually, he e a e wo sub-classes o issue-like P sys ems, one using sympo /an ipo
ules o communica ing among cells, and he o he one, close o he neu al ne o ganiza-
ion, ha ing s a es associa ed wi h he cells, o con olling mul ise ew i ing ules which
make e ol e he mul ise s o objec s om he cells.
206
In he p esen pape , we ake a di e en pe spec i e, somewha mixing he wo sub-
cases o issue-like sys ems: we associa e s a es o he links be ween cells, and use hese
s a es in o de o con ol he communica ion among cells; in i s u n, he communica ion is
done by means o sympo /an ipo ules. Among wo cells a mos one link is es ablished
(also called synapse). Because he s a es can be changed by using ules, a con lic can
appea when wo ules used on he same link ask o changing he s a e o wo di e en
new s a es. Tha is why we use he ules in a sequen ial manne : on each possible channel
be ween wo cells we use only one ule. A he le el o he whole ne o cells, he e olu ion
is pa allel (synch onous): we ha e o use a ule on each synapse whe e a ule can be used.
Conside ing a sequen ial use o ules on each link be ween cells is also challenging om
a ma hema ical poin o iew; he maximal pa allelism, usual in memb ane compu ing,
combined wi h he de ini ion o success ul compu a ions as he hal ing ones, is a powe ul
ool in “p og amming” he wo k o P sys ems o a ious ypes (in pa icula , i p o ides a
way o implemen “appea ance checking”, as in egula ed con ex - ee g amma s). In ou
amewo k, he expec ed loss in powe induced by he sequen ial use o ules is compensa ed
by he use o s a es.
The issue o conside ing s a es associa ed wi h he communica ion channels among
memb anes is pa o a mo e gene al esea ch opic, ha o conside ing issue-like P
sys ems wi h a dynamic s uc u e (dynamically changing memb anes and/o links among
hem). Ou app oach can be conside ed as a pa ial answe o his gene al p oblem, as he
s a es con ol he passage o objec s ac oss he links, selec i ely pe mi ing he objec s o
pass, possibly comple ely inhibi ing ce ain channels.
The powe o sys ems as sugges ed abo e, wi h an ipo ules o small weigh s used
sequen ially a e shown o be Tu ing comple e in he case o wo cells (e en wi h minimal
an ipo ules, i “enough” s a es a e used) and o cha ac e ize he Pa ikh images o
languages gene a ed by ma ix g amma s wi hou appea ance checking in he case o one
cell (no ma e how many s a es and no ma e how gene al ules a e used).
The case o he pa allel use o ules (in a s ep we can use simul aneously all ules
which pass om a gi en s a e o a unique nex s a e) – as well as o he ela ed p oblems
– emain o be in es iga ed.
2 Tissue-like P Sys ems wi h S a es
The eade is supposed o be amilia wi h basic elemen s o memb ane compu ing, e.g.,
om [11] ( a he use ul is he comp ehensi e in o ma ion which can be ound in he web
page h p://psys ems.disco.unimib.i ), in pa icula , wi h he issue-like P sys ems
in oduced in [9]. He e we deal wi h he ollowing ype o sys ems ( o he e y ew
elemen s o compu abili y – mainly o mal language heo y – we e e o any monog aph
in his a ea, in pa icula , o [13]; jus o he sake o comple eness, we men ion ha V∗
is he ee monoid gene a ed by he alphabe Vunde he ope a ion o conca ena ion and
he emp y s ing, deno ed by λ, as iden i y).
A issue-like P sys em (o deg ee m≥1) wi h channel-s a es is a cons uc
Π = (O, T, K, w1, . . . , wm, E, syn, (s(i,j))(i,j)∈syn,(R(i,j))(i,j)∈syn, io),
whe e Ois he alphabe o objec s,T⊆Ois he alphabe o e minal objec s, Kis he
alphabe o s a es (no necessa ily disjoin o O), w1, . . . , wma e s ings o e O ep e-
sen ing he ini ial mul ise o objec s p esen in he cells o he sys em (i is assumed
207
ha we ha e mcells, labelled wi h 1,2, . . . , m), E⊆Ois he se o objec s p esen in
a bi a ily many copies in he en i onmen , syn ⊆ {(i, j)|i, j ∈ {0,1,2, . . . , m}, i 6=j}
is he se o links among cells (we call hem synapses; 0 indica es he en i onmen ) such
ha o i, j ∈ {0,1, . . . , m}a mos one o (i, j),(j, i) is p esen in syn,s(i,j)is he ini-
ial s a e o he synapse (i, j)∈syn,R(i,j)is a ini e se o ules o he o m (s, x/y, s0),
o some s, s0∈Kand x, y ∈O∗, associa ed wi h he synapse (i, j)∈syn, and, inally,
io∈ {1,2, . . . , m}is he ou pu cell.
We no e he impo an es ic ion ha he e is a mos one synapse among wo gi en
cells, and he synapse is gi en as an o de ed pai (i, j), wi h which a s a e om Kis
associa ed. The ac ha he pai is o de ed does no es ic he communica ion among
he wo cells (o be ween a cell and he en i onmen ), because we wo k he e in he gene al
case o an ipo ules, speci ying simul aneous mo emen s o objec s in he wo di ec ions
o a synapse.
A ule o he o m (s, x/y, s0)∈R(i,j)is in e p e ed as an an ipo ule o he o de ed
pai (i, j) o cells, ac ing only i he synapse (i, j) has he s a e s; he applica ion o he ule
means mo ing he objec s speci ied by x om cell i( om he en i onmen , i i= 0) o cell
j, a he same ime wi h he mo e o he objec s speci ied by yin he opposi e di ec ion,
as well as he change o he s a e o he synapse om s o s0. (The ules wi h one o x, y
emp y a e, in ac , sympo ules, bu we do no explici ly conside he e his dis inc ion, as
i is no ele an o wha ollows.) The objec s om Ea e ne e exhaus ed, i espec i e
how many copies o each o hem a e b ough in o he sys em, a bi a ily many copies
emain a ailable in he en i onmen .
The compu a ion s a s wi h he mul ise s speci ied by w1, . . . , wmin he mcells; in
each ime uni , a ule is used on each synapse o which a ule can be used (i no ule is
applicable o a synapse, hen no objec passes o e i and i s s a e emains unchanged).
The e o e, he use o ules is sequen ial a he le el o each synapse, bu i is pa allel
a he le el o he sys em: all synapses which can use a ule mus do i ( he sys em is
synch onously e ol ing). The compu a ion is success ul i and only i i hal s and he
esul o a hal ing compu a ion is he ec o which desc ibes he mul iplici y o objec s
om Tp esen in cell ioin he hal ing con igu a ion ( he objec s om O−Ta e igno ed
when conside ing he esul ). The se o all ec o s compu ed in his way by he sys em
Π is deno ed by Ps(Π).
The amily o se s Ps(Π) o ec o s compu ed as abo e by sys ems wi h a mos m
cells, using a mos ks a es, and ules (s, x/y, s0) wi h |x| ≤ i, |y| ≤ iis deno ed by
PsO Pm(s a esk, an ii). When one o he pa ame e s m, k, i is no bounded, i is eplaced
wi h ∗. We also deno e by PsFL he se o Pa ikh images o languages om a gi en
amily FL; by RE we deno e he amily o ecu si ely enume able languages, and by CF
he amily o con ex - ee languages.
3 Two Examples
Be o e in es iga ing he compu ing powe o he abo e in oduced de ices, le us illus a e
hei wo k by some examples. The i s one (o deg ee 3) is simple . Fo mally, i is gi en
as ollows:
Π1= (O, T, K, w1, w2, w3, E, syn, (s(i,j))(i,j)∈syn,(R(i,j))(i,j)∈syn, io),
O={a, b},
T={a, b},
208
K={s, s0, s00},
wi=λ, o all i= 1,2,3,
E=O,
syn ={(0,1),(1,2),(1,3)},
R(0,1) ={(s, a/λ, s),(s, a/λ, s0),(s0, b/λ, s0),(s0, b/λ, s00)},
R(1,2) ={(s, a/λ, s),(s, b/λ, s),(s, λ/a, s),(s, λ/b, s)},
R(1,3) ={(s, b/λ, s0),(s0, a/λ, s)},
io= 3.
The sys em is pic o ially gi en in Figu e 1, wi h he synapses ep esen ed by a ows,
ha ing associa ed he ini ial s a es and he ules om he espec i e se s ( he di ec ionali y
o he a ows hus speci ies he way he ules a e applied); each cell has inside he ini ial
mul ise o objec s and ou side he label; he ou pu cell, ha wi h label 3, is indica ed
by ha ing i doubly enci cled.
Figu e 1. The sys em Π1( ules and ini ial con igu a ion)
¹¸
º· ¹¸
º·
ÁÀ
¿
½¼
¾»
?
??
1
23
s
ss
λ
λ λ
(s, a/λ, s)
(s, a/λ, s0)
(s0, b/λ, s0)
(s0, b/λ, s00)
(s, a/λ, s)
(s, b/λ, s)
(s, λ/a, s)
(s, λ/b, s)
(s, b/λ, s0)
(s0, a/λ, s)
The unc ioning o he sys em Π1is a he clea : in s a e s, cell 1 b ings inside n≥0
copies o objec a, hen he synapse (0,1) changes he s a e o s0when one u he ain
b ough in; in s a e s0we b ing in cell 1 a numbe m≥0 o copies o objec b; he p ocess
is inished only by passing o s a e s00, hence a leas one copy o bis in oduced. Any
copy o aand bcan oscilla e o e e among cells 1 and 2, hence he compu a ion can s op
only i all objec s a e mo ed o cell 3, he ou pu one. The channel om cell 1 o cell
3 can be “open” only by a copy o b, which changes he s a e o his synapse o s0; in
he p esence o s0, a copy o ais mo ed om cell 1 o cell 3 and he s a e e u ns o s.
Consequen ly, we can s op i and only i ei he he numbe s o aand bin oduced in cell
1 we e equal, o he numbe o copies o bis la ge by 1 han he numbe o copies o a.
Tha is, Ps(Π1) = {(n, n)|n≥1}∪{(n, n + 1) |n≥1}.
I is wo h no ing ha he p e ious sys em uses only unipo ules (only one objec
passes h ough a synapse, in ei he di ec ion).
209
The unc ioning o he second example we discuss he e, Π2, is much mo e in ica ed.
Ins ead o gi ing his sys em in a o mal manne , we p esen i pic o ially, in Figu e 2,
ollowing he same con en ions as in Figu e 1. The ou pu cell is 1 and he only e minal
objec is a.
Figu e 2. The sys em Π2( ules and ini ial con igu a ion)
¹¸
º· ¹¸
º·
&%
'$
"!
#Ã
?
¾
6
¾
QQQQQQQQQQQ
Q
?
1
2
3
s00
s0
s
s
s
ab
de
# #
(s0, g/de , s)
(s, b/b0b0a3c, s0)
(s, b/b0a2, s)
(s, #/#, s)
(s0, λ/de , s00)
(s00, λ/b, s00)
(s, c/λ, s0)
(s0, b/#, s)
(s0, λ/d, s)
(s, c/λ, s)
(s, λ/d, s)
(s, λ/e, s0)
(s0, b0/b, s0)
(s0, b0/#, s0)
(s0, b0/b , s00)
(s00, b0/#, s00)
(s00, g/λ, s)
(s, de /c, s)
(s, b/λ, s)
(s, b/λ, s0)
(s, λ/g, s)
This sys em compu es he squa es o na u al numbe s, in he ollowing way. We s a
wi h objec s abde in cell 1. The objec s de go along he synapse (0,1) and change i s
s a e o s, b inging gin cell 1; his objec passes o cell 3, changing he s a e o he synapse
o sand hen exi s h ough he synapse (0,3).
Assume ha we a e in a con igu a ion wi h all synapses in s a e s, wi h n2copies o
objec aand ncopies o bp esen in cell 1; ini ially, a e he s eps men ioned abo e, his
is he case. Each copy o bis sen o he en i onmen , in exchange o b0and wo copies o
a; he las copy o b om cell 1 is exchanged o wo copies o b0and h ee copies o a. In
his way, he numbe o copies o abecomes n2+ 2n+ 1 = (n+ 1)2. In he las s ep, also
cis b ough in cell 1; his objec passes o cell 2, “opening” his synapse o objec b; i
any copy o bis s ill p esen in cell 1, hen he ap-objec # is b ough in cell 1 and he
compu a ion ne e s ops.
F om cell 2, cpasses o cell 3, and om he e exi s o he en i onmen , b inging in cell
3 he objec s de . The objec dwill go o cell 2 and hen o cell 1, es o ing he s a e o
he synapse (1,2) o s, while egoes o cell 1, changing he s a e o he synapse (1,3) o s0.
This makes possible he exchange o each copy o b0 om cell 1 wi h a copy o b om cell 3
( his las objec is con inuously b ough in cell 3 om he en i onmen – bu he p ocess
can be inished by passing he synapse (0,3) o s a e s0; howe e , i his happens oo ea ly,
210

hen he objec # is mo ed om cell 3 o cell 1 and he compu a ion will las o e e ).
The exchange o b0wi h bcon inues un il changing he s a e o he synapse (1,3) o s00,
and also mo ing om cell 3 o cell 1. This should comple e he change o b0, o he wise
again he ap-objec is mo ed o cell 1. In his momen , all objec s de a e again in
cell 1, as in he ini ial con igu a ion, hence we can i e a e he p ocess ( hus passing o
he squa e o he nex na u al numbe ). I , ins ead, we send de ou side by means o he
ule (s0, λ/de , s00), hen he synapse (0,1) passes o s a e s00, which only allows he exi
o all objec s b om cell 1. In his way, only copies o objec a emain in cell 1. The ule
(s0, λ/de , s00) can be used also in he ini ial con igu a ion, hence also he squa e o 1 is
ob ained.
Consequen ly, Ps(Π2) = {n2|n≥1}. No e ha in he hal ing con igu a ion, only
copies o he e minal objec aa e p esen in he ou pu cell.
As we will see soon, he same se o numbe s can be compu ed by sys ems wi h a small
numbe o cells o s a es, and wi h simple ules.
4 Technical P e equisi es
In he p oo s om he nex sec ion we will use he egis e machines and he ma ix
g amma s (wi hou appea ance checking), ha is why we in oduce he e hese compu ing
de ices.
In wha conce ns he egis e machines, we e e o [10] o o iginal de ini ions, and o
[5], [14] o de ini ions like ha we use in his pape .
An n- egis e machine is a cons uc M= (n, R, l0, lh),whe e nis he numbe o
egis e s, Ris a ini e se o ins uc ions injec i ely labelled wi h elemen s om a gi en
se lab(M), l0is he ini ial/s a label, and lhis he inal label.
The ins uc ions a e o he ollowing o ms:
–l1: (add( ), l2),
Add 1 o he con en s o egis e and p oceed o he ins uc ion (labelled wi h) l2.
(We say ha we ha e an ADD ins uc ion.)
–l1: (sub( ), l2, l3),
I egis e is no emp y, hen sub ac 1 om i s con en s and go o ins uc ion l2,
o he wise p oceed o ins uc ion l3. (We say ha we ha e a SUB ins uc ion.)
–lh:hal ,
S op he machine. The inal label lhis only assigned o his ins uc ion.
A egis e machine Mis said o ecognize a ec o (s1, . . . , sk) o na u al numbe s i ,
s a ing wi h he ins uc ion wi h label l0, wi h he numbe s s1, . . . , skplaced in he i s k
egis e s (and he o he egis e s con aining he numbe 0), he machine s ops (i eaches
he ins uc ion lh:hal ) wi h all egis e s con aining he numbe 0.
The egis e machines a e know o be compu a ionally uni e sal, equal in powe o
Tu ing machines: hey ecognize exac ly he se s o ec o s o na u al numbe s which can
be ecognized/compu ed by Tu ing machines, ha is, he amily PsRE.
Wi hou loss o he gene ali y, in he p oo s om he ollowing sec ion we will assume
ha in each ADD ins uc ion l1: (add( ), l2) and in each SUB ins uc ion l1: (sub( ), l2, l3)
he labels l1, l2, l3a e mu ually dis inc . This goal can be easily achie ed. Fo ins ance,
211
in he case o SUB ins uc ions, we eplace each ins uc ion l1: (sub( ), l2, l3) wi h he
ins uc ions l1: (sub( ), l0
2, l00
3), l0
2: (add(n+ 1), l000
2), l000
2: (sub(n+ 1), l2, lh), l00
3: (add(n+
1), li
3), li : (sub(n+1), l3, lh), whe e n+1 is a new egis e ( he same o all s a ing SUB
ins uc ions), and all p imed labels a e dis inc and di e en om he ini ial labels.
We also use below he ma ix g amma s. Fo de ails, we e e o [3] and o he chap e
o [13] de o ed o egula ed ew i ing, and we in oduce he e only he pa icula case we
need below.
A ma ix g amma (wi hou appea ance checking) is a cons uc G= (N, T, S, M),
whe e N, T a e disjoin alphabe s, S∈N, and Mis a ini e se o o de ed sequences
o he o m (A1→x1,. . . , An→xn), n≥1, o con ex - ee ules o e N∪T(wi h
Ai∈N, xi∈(N∪T)∗, in all cases); Nis he non e minal alphabe , Tis he e minal
alphabe , Sis he axiom, while he elemen s o Ma e called ma ices.
Fo w, z ∈(N∪T)∗we w i e w=⇒zi he e is a ma ix (A1→x1, . . . , An→xn) in
Mand he s ings wi∈(N∪T)∗,1≤i≤n+ 1, such ha w=w1, z =wn+1,and, o
all 1 ≤i≤n,wi=w0
iAiw00
i, wi+1 =w0
ixiw00
i, o some w0
i, w00
i∈(N∪T)∗. The language
gene a ed by Gis de ined by L(G) =}w∈T∗|S=⇒∗w}.
By MAT we deno e he amily o languages gene a ed by ma ix g amma s. I is known
ha PsCF ⊂PsMAT ⊂PsRE ( o ins ance, PsMAT con ains non-semilinea se s o
ec o s, which is no he case wi h PsCF; on he o he hand, he one-dimensional ec o s
om PsMAT a e semilinea , while PsRE con ains non-semilinea se s o numbe s).
The powe o ma ix g amma s is no dec eased i we only wo k wi h ma ix g amma s
in he bina y no mal o m (see [3]). A g amma G= (N, T, S, M) is in his o m i i has
N=N1∪N2∪ {S}, whe e hese h ee se s a e mu ually disjoin , and each ma ix in M
is in one o he ollowing o ms:
1. (S→XA),wi h X∈N1, A ∈N2,
2. (X→Y, A →x),wi h X, Y ∈N1, A ∈N2, x ∈(N2∪T)∗,|x| ≤ 2,
3. (X→λ, A →x), wi h X∈N1, A ∈N2,and x∈T∗,|x| ≤ 2.
Mo eo e , he e is only one ma ix o ype 1 and a ma ix o ype 3 is used only once,
in he las s ep o a de i a ion.
In he ollowing we shall use a sligh ly di e en a ian o his bina y no mal o m
by adding one new non- e minal indica ing i s unique inal “s a e”, i.e., om a ma ix
g amma G= (N, T, S, M) in he bina y no mal o m as abo e we cons uc he ma ix
g amma G = (N∪ { }, T, S, M ) in -bina y no mal o m wi h
M = (M− {(X→λ, A →x)|(X→λ, A →x)∈M, X ∈N1, A ∈N2, x ∈T∗})
∪ {(X→ , A →x)|(X→λ, A →x)∈M, X ∈N1, A ∈N2, x ∈T∗})
∪ {( →λ)}.
Hence, M con ains ules o he ollowing o ms:
1. (S→XA),wi h X∈N1, A ∈N2,
2. (X→Y, A →x),wi h X, Y ∈N1, A ∈N2, x ∈(N2∪T)∗,|x| ≤ 2,
3. (X→ , A →x), wi h X∈N1, A ∈N2,and x∈T∗,|x| ≤ 2,
4. ( →λ).
212
Mo eo e , he e is only one ma ix o ype 1 and only one ma ix o ype 4, which
is only used in he las s ep o a de i a ion yielding a e minal esul .I is ob ious ha
a usual issue-like P sys em (wi hou s a es) can be conside ed as ha ing he same s a e
associa ed wi h all synapses, ne e changing. Because P sys ems wi h one memb ane
and using an ipo ules o weigh a leas wo a e uni e sal in he case o maximally
pa allel use o ules (see, e.g., [7], [6]), i is expec ed ha a simila esul holds ue also
in ou case. Howe e , his does no happen: i we ha e only one cell, i espec i e how
many s a es and how complex ules we use, we ge a mos he Pa ikh images o ma ix
languages (wi hou appea ance checking). The explana ion o his impo an di e ence
be ween ou esul s and hose om [7], [6] lies in he di e ence be ween he way he wo
ypes o sys ems wo k: sequen ially he e, in a maximally pa allel manne in he men ioned
pape s (as we ha e men ioned in he In oduc ion, he maximal pa allelism oge he wi h
he hal ing condi ion o de ining he success ul compu a ions p o ides he necessa y ools
o simula ing he appea ance checking, which is no he case o he sequen ial use o ules;
hen, he appea ance checking is exac ly he di e ence be ween MAT and uni e sali y –
ma ix g amma s wi h appea ance checking a e equi alen o Tu ing machines).
Howe e , uni e sali y can be ob ained also in ou case as soon as we use a leas wo
cells.
We s a wi h he cha ac e iza ion o he Pa ikh images o ma ix languages.
Lemma 4.1 PsMAT ⊆PsO P1(s a e∗, an i1).
P oo . Le us conside a ma ix g amma G= (N1∪N2∪ {S, }, T, S, M) in he
-bina y no mal o m. We cons uc he issue-like P sys em
Π=(O, T, K, A0Z, O, {(0,1)}, X0, R(0,1),1),
O=N2∪T∪ {Z},
K=N1∪ { } ∪ {hX, αi | X∈N1∪ { }, α ∈N2∪T},
R(0,1) ={(X, α/A, Y )|(X→Y, A →α)∈M,
X∈N1, Y ∈N1∪ { }, A ∈N2, α ∈N2∪T∪ {λ}}
∪ {(X, α1/A, hY, α2i),(hY, α2i, α2/λ, Y )|(X→Y, A →α1α2)∈M,
X∈N1, Y ∈N1∪ { }, A ∈N2, α1, α2∈N2∪T}
∪ {( , A/A, )|A∈N2}∪{( , λ/Z, )}
∪ {(X, Z/Z, X)|X∈N1},
whe e (S→X0A0) is he ini ial ma ix o M.
The ma ices (X→Y, A →x) o Ma e simula ed by simul aneously changing he s a e
o he unique synapse and exchanging an in e nal objec A o he mul ise x. I xconsis s
o a mos one symbol, hen he simula ion is done in only one s ep. I x=α1α2, hen he
objec s α1, α2a e b ough in o he sys em in wo consecu i e s eps. When he s a e is
in oduced, we check whe he he de i a ion in Gis e minal and only in he a i ma i e
case we hal . As long as he s a e o he synapse (0,1) is no , he compu a ion con inues,
a leas by a ule o he o m (X, Z/Z, X) o some X∈N1. The auxilia y objec Zis
sen ou by means o he ule ( , λ/Z, ) and hen he compu a ion s ops. Consequen ly,
ΨT(L(G)) = Ps(Π) and he p oo is comple e. 2
The numbe o s a es can be dec eased o one i we can use mo e powe ul ules.
213
Lemma 4.2 PsMAT ⊆PsO P1(s a e1, an i2).
P oo . Conside again a ma ix g amma G= (N1∪N2∪ {S, }, T, S, M) in he
-bina y no mal o m and cons uc he issue-like P sys em
Π=(O, T, {s}, X0A0Z, O, {(0,1)}, s, R(0,1),1),
O=N1∪ { } ∪ N2∪T∪ {hX, αβi | X∈N1∪ { }, α, β ∈N2∪T},
R(0,1) ={(s, Y x/XA, s)|(X→Y, A →x)∈M
X∈N1, Y ∈N1∪ { }, A ∈N2, x ∈N2∪T∪ {λ}}
∪ {(s, Y hY, α1α2i/XA, s),(s, α1α2/hY, α1α2i, s)|(X→Y, A →α1α2)∈M,
X∈N1, Y ∈N1∪ { }, A ∈N2, α1, α2∈N2∪T}
∪ {(s, α/α, s)|α∈N1∪N2}
∪ {( , λ/Z, )},
whe e (S→X0A0) is he ini ial ma ix o M.
The s a e plays no ˆole, he ma ices o Ma e simula ed by he an ipo ules. As
long as a leas a non e minal om N1∪N2is p esen , he compu a ion mus con inue.
The equali y ΨT(L(G)) = Ps(Π) is ob ious and his comple es he p oo . 2
We pass now o conside ing he opposi e inclusions, p o ing ha one-cell sys ems
canno exceed he powe o ma ix g amma s, i espec i e how many s a es and how
complex ules a e used.
Lemma 4.3 PsO P1(s a e∗, an i∗)⊆PsMAT.
P oo . Le Π = (O, T0, K, w1, E, {(0,1)}, s0, R(0,1),1) be a issue-like P sys em. We
cons uc he ma ix g amma G= (N, T0, S, M) wi h
N=K∪ {s0|s∈K}∪{a0|a∈O}∪{S},
T={s00 |s∈K} ∪ O,
and he ollowing ma ices:
1. (S→s0h(w1)),
2. (s1→s2h(x)), o (s1, x/λ, s2)∈R(0,1),
3. (s1→s2, x0
1→λ, . . . , x0
k→λ), o (s1, λ/x, s2)∈R(0,1),
o x=x1x2. . . xk,k≥1, wi h xi∈O, 1≤i≤k,
4. (s1→s2, y0
1→x, y0
2→λ, . . . , y0
k→λ), o (s1, x/y, s2)∈R(0,1),
o y=y1y2. . . yk,k≥1, wi h yi∈O, 1≤i≤k,
5. (s→s0, a0→a),
(s0→s0, a0→a), o s∈K, a ∈O,
(s0→s00), o s∈K,
whe e his he mo phism which eplaces each a∈Owi h a0.
In he p esence o non e minals om K, we simula e he ules om R(0,1); a any
momen we can in oduce a p imed s a e, in he p esence o which we ans o m each a0
214
#
"
Ã
!
µ´
¶³
µ´
¶³
µ´
¶³ µ´
¶³ µ´
¶³
HHHHHHHHHHHHH
Hj
ZZZZZZZZ
Z~
CCCCCC
CW
½
½
½
½
½
½
½
½
½=
©
©
©
©
©
©
©
©
©
©
©
©
©
©¼
- - - - - -
? ? ? ?
-
µ´
¶³
µ´
¶³
µ´
¶³
-6
-
-
¾
¾
¾
µ´
¶³ µ´
¶³
µ´
¶³ µ´
¶³
µ´
¶³ µ´
¶³
- -
´
´
´
´
´+
- -
- -
Z
Z
Z
Z
Z}
A
A
A
A
A
AK
l0
ssss
12ikk+ 1
s
ss
s s
s
. . . . . .
s s
s
s
s
s
add1
s
#
#
#
s
addi
s
...
s
...
s
addu
k+ 2
s
s
s
sub1sub0
1
. . .
s s
subisub0
i
s
s
...
s
s
sub sub0
(s, ai/λ, s0)
(s0, bi/λ, s)
(s, ei/λ, s00 )
s
(s, ei/λ, s0)
(s0, l0/λ, s0)
(s, ai/λ, s)
(s, bi/λ, s)
(s, l0/λ, s)
(s, #/#, s)
(s, λ/lh, s)
#e
#e
#e
(s, a /λ, s)
(s, l2/λ, s)
(s, e/λ, s0)
(s, l1/λ, s0)
(s0, λ/a , s00 )
(s00 , λ/l2, s)
(s0, λ/#, s)
(s00 , λ/#, s)
(s, l1/λ, s0)
(s0, a /λ, s00 )
(s00 , λ/l2, s)
(s00 , λ/#, s)
(s0, λ/l3, s)
(s, l2/e, s0)
(s0, e/λ, s)
(s, l3/λ, s)
(s, l2/l1, s0)
(s0, l3/λ, s)
λ
λ λ λ λ
Figu e 3. The s uc u e o he sys em om he p oo o Theo em 4.4
The SUB ins uc ion subi, o he o m l1: (sub( ), l2, l3), is simula ed h ough he
in e ac ion o cell k+2 wi h he cells subiand sub0
i, in he ollowing way. Fi s , he objec
l1is sen om cell k+ 2 o cell subi, and he s a e o he synapse (k+ 2, subi) is changed
o s0. In he nex s ep, l1exi s cell subi, being exchanged wi h l2, and he s a e o he
synapse (0, subi) becomes s0. Simul aneously, i any copy o a is p esen in cell k+2, hen
he ule (s0, a /λ, s00) is used, hence one copy o a lea es cell k+ 2 and he s a e o he
synapse (k+ 2, subi) becomes s00. I no copy o a exis s in cell k+ 2, hen he s a e o he
synapse emains s0and no ule is used he e. In he hi d s ep, i he s a e o he synapse
(k+ 2, subi) is s00, hen l2passes om cell subi o cell k+ 2, e u ning he s a e o his
synapse o s(and making possible he simula ion o ano he ule). A he same ime, l3
en e s cell subi, e u ning he s a e o he synapse (0, subi) o s. Ins ead o passing o cell
k+ 2, he objec l2can also pass o cell sub0
i, bu in his case he ap-objec should be
221

sen o cell k+ 2, by means o he ule (s00, λ/#, s), and he compu a ion will ne e s op.
I he simula ion o he case when a exis s is co ec , hence l2en e s cell k+ 2, hen l3
will pass in he nex s ep o cell sub0
i: he s a e o he synapse (subi, sub0
i) has emained
s, hence he ule (s, l3/λ, s)∈R(subi,sub0
i)can be used.
I no copy o a is p esen in cell k+2, hen, a e passing l1 o cell subiand exchanging
i wi h l2 om he en i onmen , l2mus pass o cell sub0
i, in exchange wi h e, eplacing
s a e swi h s0on he synapse (subi, sub0
i). A he same ime, l3en e s cell subi. In he
nex s ep, l3canno go o cell sub0
i, because o he s a e s0o he synapse (subi, sub0
i),
hence i will go o cell k+ 2, by means o he ule (s0, λ/l3, s) ( he s a e o his synapse
has emained s0, because no a has changed s0in o s00 as abo e). A he same ime, he
auxilia y objec epasses back om cell subi o cell sub0
i, e u ning he s a e o his synapse
o s.
The simula ion o he SUB ins uc ion is comple e, he s a es o he synapses a e again
s, hence he simula ion o ins uc ions o Mcan con inue.
In his p ocess, i is essen ial ha he labels l1, l2, l3 om each ins uc ion l1:
(sub( ), l2, l3) a e mu ually di e en .
When he hal label lhis in oduced in cell k+2, i exi s by means o he ule (s, λ/lh, s)
and he compu a ion s ops.
We conclude ha N(M) = Ps(Π) and his ends he p oo . 2
5 Fu he Va ian s
The p e ious sys ems wo k in he gene a i e mode, using he ules in a sequen ial manne .
Ob ious a ia ions a e ob ained by conside ing he accep ing mode. A possibili y is o
designa e a cell as he inpu one, and o s a he compu a ion by in oducing a mul ise
in ha cell; his mul ise is accep ed i and only i he compu a ion hal s.
Because in he accep ing mode we do no ha e o ake ca e o he way he ini ial
alues o he egis e machine simula ed by a P sys em as in Theo ems 4.2, 4.3, 4.4 a e
in oduced, we can sa e s a es in he cons uc ions om he p oo s o hese heo ems.
This is especially o in e es in he case o Theo em 4.3, whe e we use he wo s a es only
o in oducing he inpu , and o he compu a ion one s a e su ices; he e o e, in he
accep ing case, he uni e sali y is ob ained wi h only one s a e.
Ano he possibili y is o conside as accep ed he sequence o objec s aken om he
en i onmen du ing a hal ing compu a ion (as in [2] and [4]) and in his way we ob ain
language ecognizing de ices. The i s example om Sec ion 3 wo ks in a way o which
his mode o de ine he ecognized language is appa en – he language ecognized by Π1
is non- egula .
Then, o in e es is o conside a pa allel use o ules. In o de o a oid con lic s in
changing he labels, in each s ep, on each synapse, all ules leading om a s a e s o he
same s a e s0should be conside ed. Mo e speci ically, “ ables” o he o m Ti,j(s, s0) =
{(s, x/y, s0)|(s, x/y, s0)∈R(i,j)}can be de ined, o each synapse (i, j) and o each pai
(s, s0) o s a es; in each s ep one able is non-de e minis ically chosen and hen used in a
maximally pa allel manne .
All hese possibili ies emain o be in es iga ed. In gene al, we belie e ha he issue-
like P sys ems dese e u he esea ch e o s, mo i a ed bo h by he ma hema ical p ob-
lems hey aise and also by he in e es ing connec ions wi h in e -cell communica ion in
222
issues (an impo an biological ac , see, e.g., [8]), neu on in e ac ion in he b ain, dis-
ibu ed compu ing (in e ne included).
Re e ences
[1] F. Be na dini, A. P˘aun, Uni e sali y o minimal sympo /an ipo : Fi e memb anes
su ice. In Aspec s o Molecula Compu ing. Essays Dedica ed o Tom Head on he
Occasion o His 70 h Bi hday (N. Jonoska, Gh. P˘aun, G. Rozenbe g, eds.), Lec u e
No es in Compu e Science LNCS 2950, Sp inge -Ve lag, Be lin, 2004, 43–54.
[2] E. Csuhaj-Va ju, G. Vaszil, P au oma a o pu ely communica ing accep ing P sys-
ems. In [12], 219–233.
[3] J. Dassow, Gh. P˘aun, Regula ed Rew i ing in Fo mal Language Theo y. Sp inge -
Ve lag, Be lin, 1989.
[4] R. F eund, M. Oswald, A sho no e on analysing P sys ems wi h an ipo ules.
Bulle in o he EATCS, 78 (Oc obe 2002), 231–236.
[5] R. F eund, Gh. P˘aun, On he numbe o non- e minal symbols in g aph-con olled,
p og ammed and ma ix g amma s. P oc. Con . Uni e sal Machines and Compu a-
ions, Chi¸sin˘au, 2001 (M. Ma gens e n, Y. Rogozhin, eds.), Lec u e No es in Com-
pu e Science 2055, Sp inge -Ve lag, Be lin, 2001, 214–225.
[6] R. F eund, Gh. P˘aun, On de e minis ic P sys ems. Submi ed, 2003.
[7] P. F isco, H.J. Hoogeboom, Simula ing coun e au oma a by P sys ems wi h sym-
po /an ipo . In [12], 288–301.
[8] W.R. Loewens ein: The Touchs one o Li e. Molecula In o ma ion, Cell Commu-
nica ion, and he Founda ions o Li e. Ox o d Uni e si y P ess, New Yo k, Ox o d,
1999.
[9] C. Ma ´ın-Vide, J. Pazos, Gh. P˘aun, A. Rod ´ıguez-Pa ´on, Tissue P sys ems. Theo-
e ical Compu e Sci., 296, 2 (2003), 295–326.
[10] M.L. Minsky, Compu a ion: Fini e and In ini e Machines. P en ice Hall, Englewood
Cli s, New Je sey, USA, 1967.
[11] Gh. P˘aun, Compu ing wi h Memb anes: An In oduc ion. Sp inge -Ve lag, Be lin,
2002.
[12] Gh. P˘aun, G. Rozenbe g, A. Salomaa, C. Zand on, eds., Memb ane Compu ing. In e -
na ional Wo kshop WMC 2002, Cu ea de A ge¸s, Romania, Re ised Pape s.Lec u e
No es in Compu e Science 2597, Sp inge -Ve lag, Be lin, 2003.
[13] G. Rozenbe g, A. Salomaa, eds., Handbook o Fo mal Languages (3 olumes),
Sp inge -Ve lag, Be lin, 1997.
[14] P. Sosik, R. F eund, P sys ems wi hou p io i ies a e compu a ionally uni e sal. In
[12], 400–409.
223