Gene a ion o Diophan ine Se s by Compu ing
P Sys ems wi h Ex e nal Ou pu
Ál a o ROMERO JIMÉNEZ and Ma io J. PÉREZ JIMÉNEZ
Dp o. de Ciencias de la Compu ación e In eligencia A icial
Uni e sidad de Se illa, España
E-mail:
{Al a o.Rome o,Ma io.Pe ez}@cs.us.es
Abs ac .
In his pape a a ian o P sys ems wi h ex e nal ou pu
designed o compu e unc ions on na u al numbe s is p esen ed. These
P sys ems a e s able unde composi ion and i e a ion o unc ions. We
p o e ha e e y diophan ine se can be gene a ed by such P sys ems;
hen, he uni e sali y o his model can be deduced om he heo em by
Ma iyase ich, Robinson, Da is and Pu nam in which hey es ablish ha
e e y ecu si ely enume able se is a diophan ine se .
1 In oduc ion
In 1998 G. Pun ini ia ed a new b anch o he eld o
Na u al Compu ing
by
in oducing a new model o molecula compu a ion, based on he s uc u e and
unc ioning o he li ing cell:
ansi ion P sys ems
(see [3]). The amewo k
wi hin which compu a ion a e pe o med in his model is he memb ane s uc-
u e, which ec ea es he cell-like one. Mul ise s o symbol-objec s a e p ocessed
along he compu a ions, making hem o e ol e and dis ibu ing hem among
he memb anes. The esul o a hal ing compu a ion is he numbe o objec s
collec ed in a specied ou pu memb ane.
Since he in oduc ion o his model o compu a ion many a ian s o i ha e
been p oposed. One o hem, p esen ed in [5] by G. Pun, G. Rozenbe g and
A. Salomaa, is he model o
ansi ion P sys ems wi h ex e nal ou pu
. In his
model, he esul o a hal ing compu a ion is no collec ed in a xed memb ane
o he memb ane s uc u e, bu in he ex e nal en i onmen associa ed wi h i .
In his way, he ou pu o a compu a ion can be hough as a se o s ings,
ins ead o as a na u al numbe , as occu ed in he basic model.
P sys ems a e usually conside ed as de ices which gene a e numbe s. Ne-
e heless, besides gene a ing de ices, hey can also be hough as ecognizing
de ices and as compu ing de ices. These kind o P sys ems ha e been s udied
in [6].
In his pape we wo k wi h compu ing P sys ems, bu ins ead o he basic
ansi ion ones we conside hose wi h ex e nal ou pu . Thanks o he special
unc ioning o hese appa a us, we ha e been able o dene, in a com o able
manne , se e al ope a ions be ween compu ing P sys ems wi h ex e nal ou pu ;
mo e specically, we ha e dened composi ion and i e a ion, wha ha e allowed
us o p o e he uni e sali y o hese de ices h ough he gene a ion o all he
diophan ine se s.
2 Mul ise s. Memb ane s uc u es. E olu ion ules
A
mul ise
o e a se ,
A
, is an applica ion
m:A→IN
. A mul ise is said o be
emp y ( esp. ni e) i i s suppo ,
supp(m) = {a∈A:m(a)>0}
, is emp y ( esp.
ni e). I
m
is a ni e mul ise o e
A
, we will deno e i
m={{a1, . . . , ak}}
,
whe e he elemen s
ai
a e possibly epea ed. We w i e
M(A)
o he se o all
he mul ise s o e
A
.
The se o
memb ane s uc u es
,
MS
, is dened by ecu sion as ollows:
1.
[ ] ∈MS
; 2. I
µ1, . . . , µn∈MS
, hen
[µ1. . . µn]∈MS
.
A memb ane s uc u e,
µ
, can also be seen as a oo ed ee,
V(µ), E(µ)
.
Then, he nodes o his ee a e called
memb anes
, he oo node he
skin mem-
b ane
and he lea es
elemen a y memb anes
o he memb ane s uc u e. The
deg ee
o a memb ane s uc u e is he numbe o memb anes in i .
The concep s o
dep h
o a memb ane s uc u e and
dep h
o i s memb anes
a e easily dened om hose o a ee and i s nodes. We will also need he
no ion o
le el
o a memb ane wi hin a memb ane s uc u e, which is dened as
he die ence be ween he dep h o he second and he dep h o he  s .
The
memb ane s uc u e wi h ex e nal en i onmen
associa ed wi h a mem-
b ane s uc u e,
µ
, is
µE= [Eµ]E
. I we conside he la e as a oo ed ee, he
oo node is called he
ex e nal en i onmen
o
µ
.
Gi en an alphabe ,
Γ
, we associa e wi h e e y memb ane o a memb ane
s uc u e a ni e mul ise o elemen s o
Γ
, which a e called he
objec s
o he
memb ane.
We also associa e wi h e e y one o hese memb anes a ni e se o
e olu ion
ules
. A e olu ion ule o e
Γ
is a pai
(u, )
, usually w i en
u→
, whe e
u
is
a s ing o e
Γ
and
= 0
o
= 0δ
, whe e
0
is a s ing o e
Γ×{he e, ou }∪{inl:l∈V(µ)}
The idea behind a ule is ha he objec s in
u
e ol e in o he objec s in
0
,
mo ing o no o ano he memb ane and possibly dissol ing he o iginal one.
3 Compu ing P sys ems wi h ex e nal ou pu
We a e now p epa ed o in oduce ou new model o compu a ion.
Deni ion 3.1.
A compu ing P sys em wi h ex e nal ou pu o o de
(m, n)
and
deg ee
p
is a uple
Π=Σ, Λ, Γ, #, µΠ, ι, M1, . . . , Mp,(R1, ρ1), . . . , (Rp, ρp)
whe e

Σ
is an o de ed alphabe o size
m
, he inpu alphabe .

Λ
is an o de ed alphabe o size
n
, he ou pu alphabe .

Γ
is an alphabe such ha
Σ∪Λ⊂Γ
, he wo king alphabe .

#
is a dis inguished elemen in
Γ Σ∪Λ)
, he hal ing elemen .

µΠ
is a memb ane s uc u e o deg ee
p
, whose memb anes we suppose labeled
om 1 o
p
.

The inpu memb ane o
Π
is labeled by
ι∈ {1, . . . , p}
.

Mi
is a mul ise o e
Γ Σ
associa ed wi h he memb ane labeled by
i
, o
e e y
i= 1, . . . , p
.

Ri
is a ni e se o e olu ion ules o e
Γ
associa ed wi h he memb ane
labeled by
i
, and
ρi
is a s ic pa ial o de o e i , o e e y
i= 1, . . . , p
.
To o malize he seman ics o his model we dene  s wha a congu a ion
o a P sys em is, om wha ollows he no ion o compu a ion.
Deni ion 3.2.
Le
Π
be a compu ing P sys em wi h ex e nal ou pu .

A congu a ion o
Π
is a pai
(µE, M)
, whe e
µ
is a memb ane s uc u e
such ha
V(µ)⊆V(µΠ)
and has he same oo han
µΠ
, and
M
is an
applica ion om
V(µE)
in o
M(Γ)
. Fo e e y node
nd ∈V(µE)
we deno e
Mnd =M(nd)
.

Suppose ha
Π
is o o de
(m, n)
and
Σ= (a1, . . . , am)
. Then, any
m
- uple
o na u al numbe s can be codied by a mul ise o e
Σ
and gi en as inpu o
he P sys em. Thus, he ini ial congu a ion o
Π
o a uple
(k1, . . . , km)∈
INm
is he pai
(µE, M)
, whe e
µ=µΠ
,
ME=∅
,
Mι=Mι∪{{ak1
1. . . akm
m}}
and
Mi=Mi
, o e e y
i6=ι
.
We can pass, in a non-de e minis ic manne , om one congu a ion o
Π
o ano he by applying o i s mul ise s he e olu ion ules associa ed wi h hei
co esponding memb anes. This is done as ollows: gi en a ule
u→
o a
memb ane
i
, he objec s in
u
a e emo ed om
Mi
; hen, o e e y
(ob, ou )∈
an objec
ob
is pu in o he mul ise associa ed wi h he pa en memb ane (o
he ex e nal en i onmen i
i
is he skin memb ane); o e e y
(ob, he e)∈
an objec
ob
is added o
Mi
; o e e y
(ob, inj)∈
an objec
ob
is added o
Mj
(i
j
is no a child en memb ane o
i
, he ule canno be applied). Finally,
i
δ∈
, hen he memb ane
i
is dissol ed, ha is, i is emo ed om he
memb ane s uc u e ( he objec s associa ed wi h his memb anes a e collec ed
by he pa en memb ane, and he ules a e los . The skin memb ane canno
dissol e). Mo eo e , he
p io i y ela ion
among he ules o bids he applica ion
o a ule i ano he one o highe p io i y is applied.
Gi en wo congu a ions,
C
and
C0
, o
Π
, we say ha
C0
is ob ained om
C
in one ansi ion s ep, and we w i e
C⇒C0
, i we can pass om he  s o
he second by using he e olu ions ules appea ing in he memb ane s uc u e o
C
in a pa allel and maximal way, and o all he memb anes a he same ime.
Deni ion 3.3.
Gi en a compu ing P sys em wi h ex e nal ou pu o o de
(m, n)
,
Π
, a compu a ion o
Π
wi h inpu
(k1, . . . , km)∈INm
is a sequence,
possibly inni e, o congu a ions o
Π
,
C0⇒C1⇒. . . ⇒Cq
,
q≥0
, such ha

C0
is he ini ial congu a ion o
Π
o
(k1, . . . , km)
.

Each
Ci
is ob ained om he p e ious congu a ion by one ansi ion s ep.
We say ha a compu a ion,
C
, is a hal ing compu a ion o
Π
, i
q∈IN
and he e
is no ule applicable o he objec s p esen in i s las congu a ion.
Then, he ou pu o a hal ing compu a ion and o a compu ing P sys em
wi h ex e nal ou pu can be dened in a na u al way.
Deni ion 3.4.
Le
Π
be a compu ing P sys em wi h ex e nal ou pu o o de
(m, n)
and suppose ha
Λ= (b1, . . . , bn)
. Le
C
be a hal ing compu a ion o
Π
wi h inpu
(k1, . . . , km)∈INm
and
(µE, M)
i s las congu a ion. Then, he
ou pu o ha compu a ion is gi en by
Ou pu (C) = ME(b1), . . . , ME(bn).
Deni ion 3.5.
Le
Π
be a compu ing P sys em wi h ex e nal ou pu o o de
(m, n)
. The ou pu o
Π
wi h inpu
(k1, . . . , km)∈INm
is gi en by
Ou pu (Π;k1, . . . , km) = {Ou pu (C) : C
is a hal ing compu a ion o
Π
wi h inpu
(k1, . . . , km)}.
The idea behind P sys ems wi h ex e nal ou pu is ha we canno know
wha is happening inside he memb ane s uc u e, bu we can only collec he
in o ma ion h own om i o he ex e nal en i onmen . In acco dance wi h i ,
i seems na u al ha he hal ing compu a ions o hese P sys ems epo o he
ou side when hey ha e eached hei nal congu a ions.
Fu he mo e, he idea behind compu ing P sys ems is o use hem as com-
pu ing models o unc ions be ween na u al numbe s. These conside a ions lead
us o he ollowing no ions:
Deni ion 3.6.
A compu ing P sys em wi h ex e nal ou pu o o de
(m, n)
,
Π
,
is said o be alid when he ollowing is e ied:

I
C
is a hal ing compu a ion o
Π
, hen a ule o he o m
u→ (#, ou )
mus ha e been applied in he skin memb ane o
µΠ
, and only in he las s ep
o he compu a ion.

I
C
is no a hal ing compu a ion o
Π
, hen no ule o he p e ious o m is
applied in he skin memb ane in any s ep o he compu a ion.

Fo e e y
(k1, . . . , km)∈INm
and o e e y wo hal ing compu a ions,
C1
and
C2
, o
Π
wi h inpu
(k1, . . . , km)
,
Ou pu (C1) = Ou pu (C2)
.
Deni ion 3.7.
A compu ing P sys em wi h ex e nal ou pu o o de
(m, n)
,
Π
,
compu es a pa ial unc ion,
: INm− → INn
, i

Π
is a alid P sys em.

Fo e e y
(k1, . . . , km)∈INm
•
is dened o e
(k1, . . . , km)
i and only i he e exis s a hal ing com-
pu a ion o
Π
wi h inpu
(k1, . . . , km)
.
•
I
C
is a hal ing compu a ion o
Π
wi h inpu
(k1, . . . , km)
, hen
Ou pu (C) = (k1, . . . , km)
.
We deno e
CEPm,n
p(α, β, γ)
, whe e
m, n ∈IN, p ≥1
,
α∈ {P i, nP i}
,
β∈ {Coo, Ca , nCoo}
and
γ∈ {δ, nδ}
, he amily o unc ions compu ed by
compu ing P sys ems wi h ex e nal ou pu o o de
(m, n)
, o deg ee a mos
p
,
and wi h o wi hou p io i y, wi h coope a ion, only ca alys s o wi hou coop-
e a ion (see [3]), and wi h o wi hou dissolu ion, espec i ely. The union, o all
p≥1
, o he amilies o one o hese ypes is deno ed
CEPm,n(α, β, γ)
.
4 Composi ion o compu ing P sys ems wi h ex e nal
ou pu
We in oduce now he ope a ion o composi ion be ween compu ing P sys ems
wi h ex e nal ou pu .
Deni ion 4.1.
Le
: INm− → INn
and
g1: IN − → INs1, . . . , g : IN − →
INs
such ha
s1+· · ·+s =m
. Then, he composi ion o
wi h
g1
o
g
, deno ed
C( ;g1, . . . , g )
, is a pa ial unc ion om
IN
o
INn
dened as ollows
C( ;g1, . . . , g )(k1, . . . , k ) = (g1(k1, . . . , k ), . . . , g (k1, . . . , k ))
Theo em 4.2.
Le
∈CEPm,n(α, β, γ), g1∈CEP ,s1(α, β, γ), . . . , g ∈
CEP ,s (α, β, γ)
, wi h
α∈ {P i, nP i}
,
β∈ {Coo, Ca , nCoo}
and
γ∈ {δ, nδ}
.
Then,
C( ;g1, . . . , g )∈CEP ,n(P i, Coo, γ)
.
P oo .
Le
Π =Σ , Λ , Γ ,# , µΠ , ι ,M
1, . . . , M
p ,(R
1, ρ
1), . . . , (R
p , ρ
p )
Πg1=Σg1, Λg1, Γg1,#g1, µΠg1, ιg1,Mg1
1, . . . , Mg1
pg1,(Rg1
1, ρg1
1), . . . , (Rg1
pg1, ρg1
pg1)
.
.
.
Πg =Σg , Λg , Γg ,#g , µΠg , ιg ,Mg
1, . . . , Mg
pg ,(Rg
1, ρg
1), . . . , (Rg
pg , ρg
pg )
be compu ing P sys ems wi h ex e nal ou pu ha compu e, espec i ely, he
unc ion and he unc ions
g1
o
g
.
By means o a enaming o he elemen s o he alphabe s (and, he e o e,
also o he ules), we can suppose ha

Σg1=· · · =Σg = (a1, . . . , a )
.

Λg1= (b1, . . . , bs1), . . . , Λg = (bs1+···+s −1+1, . . . , bm)
.

Σ = (c1, . . . , cm)
.

Λ = (d1, . . . , dn)
.

Λg1∪ · · · ∪ Λg ∩Γ =∅
.

#gi6= #gj
, o e e y
i6=j
.

Le us conside he compu ing P sys em wi h ex e nal ou pu
Π=Σ, Λ, Γ, #, µΠ, ι, M1, . . . , Mp,(R1, ρ1), . . . , (Rp, ρp)
gi en by

Σ= (e1, . . . , e )
. (We suppose ha
Σ∩S
i=1 Γgi=∅
).

The e exis dis inguished elemen s
⊕,, ∈ Γ (Γ ∪S
i=1 Γgi)
.

Λ= (d1, . . . , dn)
.

#6= #gi
, o e e y
i= 1, . . . ,
, and
#6= #
.

µΠ= [1µΠg1. . . µΠg µΠ ]1
, whe e he memb anes om
µΠg1, . . . , µΠg , µΠ
ha e been adequa ely enamed (and he e o e, also he ules o he co es-
ponding P sys ems ha e been adap ed). We deno e
σg1, . . . , σg , σ
he skin
memb anes o he la e . Also, we conside ha
ιg1, . . . , ιg , ι
eec he new
labeling o he inpu memb anes o
Πg1, . . . , Πg , Π
, espec i ely.

ι= 1
.

p=pg1+· · · +pg +p + 1
.

M1={{#,}}
. The emaining mul ise s a e all emp y.

The e olu ion ules a e he ollowing:
•
E olu ion ules o memb ane 1:
ei→(ei, inσg1). . . (ei, inσg ) (i= 1, . . . , )
 → (, inσg1). . . (, inσg )
#g1. . . #g #→(, inσ )>#→#> bi→(bi, inσ ) (i= 1, . . . , m)
di→(di, ou ) (i= 1, . . . , n)
# →(#, ou )
•
Fo e e y unc ion
un =g1, . . . , g ,
and o e e y memb ane
j
o
µΠ un
, he ollowing ules a e included:
 → ⊕(, inj1). . . (, injk)
u⊕ → M un
j>⊕ → ⊕
e olu ion ules associa ed wi h he memb ane in
Π un
whe e
j1
o
jk
a e he child en memb anes o memb ane
j
and
u
is i s
le el wi hin
µΠ un
. Mo eo e , i
j
is
ι un
, hen he ule
⊕ → ⊕
has
highe p io i y han he o iginal ules o
Π un
o his memb ane.
•
Le
un
be as abo e and le
j1, . . . , jq
be he memb ane pa h om
σ un
o
ι un
. Then, o
k= 1, . . . , q −1
he ollowing ules a e included in
memb ane
jk
:
ei→(ei, injk+1 ) (i= 1, . . . , )
o
un =g1, . . . , g
bi→(bi, injk+1 ) (i= 1, . . . , m)
o
un =
Also, he ollowing ules a e included in memb ane
jq=ι un
.
ei→ai(i= 1, . . . , )
o
un =g1, . . . , g
bi→ci(i= 1, . . . , m)
o
un =
The P sys em cons uc ed in his way, deno ed
C(Π ;Πg1, . . . , Πg )
, is a alid
compu ing P sys em wi h ex e nal ou pu which compu es he composi ion o
wi h
g1
o
g
. Fu he mo e, i p ese es he use o no o dissolu ion om he P
sys ems which compu e he unc ions.
Indeed, he sys em wo ks as ollows:

Phase 1:
Compu a ion o he unc ions
g1
o
g
o e he inpu da a
To pe o m his s age, we need o ca y ou wo ope a ions: he  s one
consis s o aking he inpu a gumen s om memb ane 1, which ecall is he
inpu memb ane o
Π
, o all he inpu memb anes o he P sys ems
Πg1
o
Πg
. This is easily done by displacing he objec s ep esen ing he a gumen s
h ough all he necessa y memb anes.
The second ope a ion is a li le bi mo e complica ed: in o de o a specic
P sys em
Πgj
o compu e co ec ly he alue o he unc ion
gj
o e he
inpu da a, we need ha all he memb anes o his P sys em s a o apply
hei o iginal ules
a he same ime
( ha is, we ha e o synch onize locally
he memb anes o each
Πgj
). We achie e his by using coun e s o e e y
one o hese memb anes. Fi s , we use he objec

o ac i a e he coun e s,
ep esen ed by objec s
⊕
, in all he memb anes. These la e objec s use
objec s

o coun and, when a ce ain quan i y is eached, he co esponding
memb ane is allowed o use he ules o
Πgj
. Because o he way we ha e
implemen ed his, hese quan i ies u n ou o be he le els o he memb anes
in he s uc u e
µΠgj
.
I is also impo an ha when he P sys em
Πgj
s a s o compu e he alue,
he objec s ep esen ing he inpu da a ha e eached i s inpu memb ane.
Howe e , as we pe o m he wo ope a ions abo e simul aneously, we ge i
o ee.
Finally, we ha e o wai un il all he alues om
Πg1
o
Πg
ha e been
compu ed, be o e allowing he P sys em
Π
o be used ( ha is, he e mus
be a global synch oniza ion in he skin o
Π
).
Le us see wi h g ea e de ail he ules in ol ed in his phase:
1. A he  s s ep o a compu a ion o
Π
wi h inpu
(k1, . . . , k )
, we ha e
in memb ane 1 he mul ise
{{ek1
1, . . . , ek
,#,}}
and he o he mem-
b anes a e emp y. The e o e, only he ules which send he objec s
ei
and he objec

in o he skins o
µΠg1
o
µΠg
and he ule
#→#
in
memb ane 1 can be applied.
2. Now, memb ane 1 wai s o he alues o
g1
o
g
o e
(k1, . . . , k )
by
means o he ule
#→#
. Wi h ega d o memb ane s uc u es
µΠg1
o
µΠg
, he ule
 → ⊕(, inj1). . . (, injk)
makes he objec

o sp ead
o all hei memb anes, because when i eaches a pa icula memb ane,
i is immedia ely ans o med in o a coun e objec
⊕
and also sen o
he child en memb anes. Thus, om a s ep o he compu a ion o he
nex one,

eaches he memb anes one dep h g ea e . Meanwhile, he
ule
⊕ → ⊕
makes he objec
⊕
o gene a e objec s

. A close look
o he si ua ion c ea ed shows ha he ac i a ing objec

ha e eached
all he memb anes exac ly when he coun e objec s
⊕
ha e gene a ed
in each memb ane a numbe o objec s

equal o hei le els in
µΠ un
(
un =g1, . . . , g
). A ha momen , he ule
u⊕ → M un
j
in oduces
in memb ane
j
he objec s associa ed wi h i in
Π un
, and his is done
o all he memb anes o each
Π un
a he same ime. F om now on, he
alues o
g1
o
g
o e
(k1, . . . , k )
a e compu ed exac ly in he same way
han he P sys ems
Πg1
o
Πg
would do i .
3. Simul aneously, he objec s
ei
co e he pa h om he skin memb ane
o each
µΠgj
o he inpu memb ane o
Πgj
, by means o he ules
ei→
(ei, injk+1 )
, and a e changed he e in o he co esponding objec s
ai
, by
means o he ules
ei→ai
. No e ha he objec s
ei
and he objec

each he inpu memb ane a he same ime. So, when
Πgj
s a s i s
o iginal unc ioning, as s a ed abo e, he inpu da a is in i s place.

Phase 2:
Compu a ion o he unc ion
Phase 1 ends when memb ane 1 has collec ed a leas one objec o each
#g1
o
#g
. I is hen when he alues compu ed ha e o be sen as inpu da a
o he P sys em
Π
. To synch onize he end o phase 1 wi h he beginning
o phase 2, memb ane 1 apply once and again he ule
#→#
un il he ule
#g1. . . #g #→(, inσ )
can be used.
This la e ule sends an objec

in o he skin o
µΠ
, in o de o ini ia e
i s memb anes' coun e s so ha hey s a o apply hei o iginal ules a
he same ime (local synch oniza ion wi hin
Π
). This is done jus as be o e.
Also, in he nex s ep o he compu a ion he objec s
bi
, which ep esen he
alues ob ained in phase 1, a e pu in o he skin o
µΠ
and, subsequen ly,
mo ed, by means o he ules
bi→(bi, injk+1 )
, h ough all he memb anes
om his one o he inpu memb ane o
Π
. Nex , he ules
bi→ci
change
hem in o he co esponding inpu objec s o
Π
.
I is easy o see ha , al hough he e is a gap o one s ep o compu a ion
be ween when

ge s in o a memb ane and when he
bi
s do so, his is no
a all a p oblem.
Now, he alue o he unc ion
o e he a gumen s ep esen ed by he
objec s
ci
is compu ed, and along his compu a ion objec s
di
ep esen ing
he esul a e h own ou o
µΠ
. These objec s a e collec ed in memb ane
1, and immedia ely expelled om
µΠ
. The calcula ion nishes when some
objec s
#
a e collec ed in memb ane 1 and hey a e expelled om
µΠ
as
objec s
#
.
u
5 I e a ion o compu ing P sys ems wi h Ex e nal
Ou pu
We in oduce now he ope a ion o i e a ing a compu ing P sys em wi h ex e nal
ou pu .
Deni ion 5.1.
Le
: INm− → INm
. Then, he i e a ion unc ion o
, deno ed
I ( )
, is a pa ial unc ion om
INm+1
o
INm
dened as ollows:
I ( )(x,0) = x
I ( )(x, n + 1) = I ( )( (x), n)
Theo em 5.2.
Le
∈CEPm,m(α, β, nδ)
, wi h
α∈ {P i, nP i}
and
β∈
{Coo, Ca , nCoo}
. Then
I ( )∈CEP m+1,m(P i, Coo, nδ)
.
P oo .
Le
Π =Σ , Λ , Γ ,# , µΠ , ι ,M
1, . . . , M
p ,(R
1, ρ
1), . . . , (R
p , ρ
p )
be a compu ing P sys em wi h ex e nal ou pu such ha compu es
.
By means o a enaming o he elemen s o he alphabe s (and, he e o e,
also o he ules), we can suppose ha

Σ = (a1, . . . , am)
.

Λ = (b1, . . . , bm)
.
Le us conside he compu ing P sys em wi h ex e nal ou pu
Π=Σ, Λ, Γ, #, µΠ, ι, M1, . . . , Mp,(R1, ρ1), . . . , (Rp, ρp))
e i ying he ollowing

Σ= (c1, . . . , cm+1)
, and is such ha
Σ∩Γ =∅
.

The e exis dis inguished elemen s
⊕,,,⊗, ∈ Γ Γ
.

Λ= (c1, . . . , cm)
.

#6= #
.

µΠ= [1µΠ ]1
, whe e he memb anes om
µΠ
ha e been adequa ely e-
named (and he e o e, also he ules o
Π
ha e been adap ed). We deno e
σ
he skin memb ane o he la e . Also, we conside ha
ι
eec s he
new labeling o he inpu memb ane o
Π
.

ι= 1
.

p=p + 1
.

M1={{#}}
. The emaining memb anes a e all emp y.

The e olu ion ules a e he ollowing:
•
E olu ion ules o memb ane 1:
#cm+1 →(, inσ )>#ci→#(ci, ou ) (i= 1, . . . , m)>
>#→(#, ou )># # →# ># →(, inσ )>
>⊗ubi→ ⊗uci(i= 1, . . . , m)>⊗u→#>
> ci→(ci, inσ ) (i= 1, . . . , m)
whe e
u
is he deg ee o
µΠ
.