Pola iza ionless P Sys ems wi h One Ac i e
Memb ane
A iom Alhazo 1, Rudol F eund2
1Ins i u e o Ma hema ics and Compu e Science, Academy o Sciences o Moldo a
Academiei 5, Chi¸sin˘au MD-2028 Moldo a
E-mail: [email p o ec ed]
2Facul y o In o ma ics, Vienna Uni e si y o Technology
Fa o i ens . 9, 1040 Vienna, Aus ia
E-mail: [email p o ec ed]
Summa y. The aim o his pape is o s udy he compu a ional powe o P sys ems wi h
one ac i e memb ane wi hou pola iza ions. Fo P sys ems wi h ac i e memb anes, i is
known ha compu a ional comple eness can be ob ained wi h ei he o he ollowing com-
bina ions o ea u es: 1) wo pola iza ions, 2)memb ane c ea ion and dissolu ion, 3) ou
memb anes wi h h ee labels, memb ane di ision and dissolu ion, 4)se en memb anes
wi h wo labels, memb ane di ision and dissolu ion.
Clea ly, wi h one memb ane only objec e olu ion ules and send-ou ules a e pe -
mi ed. Two a ian s a e conside ed: ex e nal ou pu and in e nal ou pu .
1 In oduc ion
Memb ane compu ing is a heo e ical amewo k o pa allel dis ibu ed mul ise p ocess-
ing. I has been in oduced by Gheo ghe P˘aun in 1998, and has been an ac i e esea ch
a ea since hen, see [10] o he comp ehensi e bibliog aphy and [6],[8] o a sys ema ic
su ey. Memb ane sys ems a e also called P sys ems.
I has been shown in [4] (some esul s being imp o emen s o he esul s om [1] and
[3]) ha he ollowing P sys ems wi h ac i e memb anes a e compu a ionally comple e:
1) wi h one memb ane and wo pola iza ions, as accep o s, 2) pola iza ionless ones wi h
memb ane c ea ion and dissolu ion, 3) pola iza ionless ones s a ing wi h ou memb anes
and h ee labels, 4) pola iza ionless ones s a ing wi h se en memb anes and wo labels.
The objec o s udy o his pape is he amily o P sys ems wi h one ac i e mem-
b ane wi hou pola iza ions. Simila ques ions o non-coope a i e ansi ional P sys ems
wi hou any addi ional ea u es ha e been add essed in [2].
10 A. Alhazo , R. F eund
2 De ini ions
2.1 Fo mal Language P elimina ies
Conside a ini e se V. The se o all wo ds o e Vis deno ed by V∗, he conca ena ion
ope a ion is deno ed by •(which is w i en only when necessa y) and he emp y wo d
is deno ed by λ. Any se L⊆V∗is called a language. Fo a wo d w∈V∗and a sym-
bol a∈V, he numbe o occu ences o ain wis w i en as |w|a. The pe mu a ions
o a wo d w∈V∗a e Pe m(w) = {x∈V∗| |x|a=|w|a o all a ∈V}. We deno e
he se o all pe mu a ions o he wo ds in Lby Pe m(L), and we ex end his no a ion
o amilies o languages. We use F IN,REG,LIN,CF ,MAT ,CS,RE o deno e i-
ni e, egula , linea , con ex - ee, ma ix wi hou appea ance checking and wi h e asing
ules, con ex -sensi i e, and ecu si ely enume able amilies o languages, espec i ely.
The amily o languages gene a ed by ex ended ( abled) in e ac ionless L sys ems is de-
no ed by E(T)0L. The amily o se s o numbe s gene a ed by o bidden andom con ex
mul ise g amma s is deno ed by N RC. Fo mo e o mal language p elimina ies, we
e e he eade o [9].
Th oughou his pape we use s ing no a ion o deno e he mul ise s. When speak-
ing abou memb ane sys ems, keep in mind ha he o de in which symbols a e w i en
is i ele an , unless we speak abou he symbols sen o he en i onmen . In pa icu-
la , speaking abou he con en s o some memb ane, when we w i e an1
1· · · anm
m(o any
pe mu a ion o i ), we mean a mul ise consis ing o niins ances o symbol ai, 1 ≤i≤m.
2.2 P sys ems wi h One (Ac i e) Memb ane
We p esen he de ini ion o a P sys em wi h ac i e memb anes, simpli ied o s udying
he gene a i e powe in case o one memb ane.
Π= (O, µ = [ ]1, w1, R1, i0),whe e
Ois a ini e se o objec s,
w1is he ini ial mul ise in egion 1,
R1is he se o ules associa ed o memb ane 1,
i0is he ou pu egion; when languages a e conside ed, i0= 0 is assumed.
The ules o a memb ane sys em ha e he o ms (a0) [ a→u]1(e olu ion o an
objec ), and (c0) [ a]1→[ ]1b(sending an objec ou , possibly enaming i ), whe e
a, b ∈Oand u∈O∗.
The ules a e applied in maximally pa allel way: no u he ule should be applicable
o he idle objec s, excep ules o ype (c0) may be applied o a mos one objec a any
s ep.
Aca aly ic P sys em (wi h one memb ane) is a cons uc
Π= (O, C, µ = [ ]1, w1, R1, i0),whe e
Ois a ini e se o objec s,
Cis a special subse o Owhose elemen s a e called ca alys s,
w1is he ini ial mul ise in egion 1,
R1is he se o ules associa ed o memb ane 1,
i0is he ou pu egion; when languages a e conside ed, i0= 0 is assumed.
Pola iza ionless P Sys ems wi h One Ac i e Memb ane 11
The ules in Ra e ei he non-coope a i e ules o he o m a→(b1, a 1)· · · (bk, a k)
wi h aand he bi, 1 ≤i≤k, being om O Cand he a i∈ {he e, ou }be-
ing he a ge s o he co esponding symbols bi, o ca aly ic ules o he o m ca →
c(b1, a 1)· · · (bk, a k) wi h c∈C.
A con igu a ion o a P sys em is a cons uc which con ains he in o ma ion abou
he con en s o he skin memb ane as well as he sequence o objec s sen ou . A sequence
o ansi ions be ween he con igu a ions is called a compu a ion. The compu a ion hal s
when such a con igu a ion is eached ha no ules a e applicable. In case o ex e nal
ou pu (i0= 0), as he esul o a (hal ing) compu a ion we may conside he sequence o
objec s sen o he en i onmen ; we deno e i by L(Π). Bo h in case o in e nal ou pu
(i0= 1) and in case o ex e nal ou pu , we may conside as he esul he ec o o
mul iplici ies o objec s in egion i0, we deno e i by P s(Π), o he o al numbe o
objec s in egion i0, which we deno e by N(Π).
The amily o P sys ems wi h one pola iza ionless ac i e memb ane may be deno ed
by OP1(a0, c0). The class o se s o numbe s/ ec o s/wo ds gene a ed by a amily Fo
P sys em is deno ed by NF,P sFand LF, espec i ely. We use a supe sc ip in o
ex when speaking abou in e nal and ex e nal ou pu , espec i ely, and we may omi
subsc ip ex in he case o gene a ing languages, i.e., ex e nal ou pu is assumed o LF.
Mo eo e , we may use a subsc ip T o deno e e minal il e ing o he esul ; in his
case, a subse T⊂Ois addi ionally speci ied o Π, and he objec s no belonging o Ta e
no conside ed in he esul . Fo example, he amily o se s o ec o s o non-nega i e
in ege s gene a ed in e nally by P sys ems wi h one pola iza ionless ac i e memb ane
wi h e minal il e ing a e deno ed by P sin
TOP1(a0, c0).
Example 1. To illus a e gene a ion, conside he ollowing P sys em:
Π= (O={S, a, b, c, d, }, µ = [ ]1, w1=a, R1, i0),
R1={[S→Sabcd ]1,[S→ ]1,
[a]1→[ ]1a, [b]1→[ ]1b, [c]1→[ ]1c}.
Objec Sp oduces objec s a,b,c,din a bi a y bu equal amoun s. Objec s a,b,ca e
sen ou in a bi a y o de . Hence, i i0= 1 hen N(Π) = N1(i.e., he se o all posi i e
in ege s), and i i0= 0 hen L(Π) = Sn≥0Pe m(anbncn) = {w∈ {a, b, c}∗| |w|a=
|w|b=|w|c}.
P sys ems can be also iewed as accep o s. In ha case, an inpu subalphabe Σis
addi ionally speci ied in he uple de ining P sys em be o e µ, and i0= 1 is he inpu
egion. An inpu mul ise o e Σis addi ionally placed inside he memb ane be o e he
compu a ion s a s, and i is accep ed i and only i he compu a ion hal s. The esul
P sacc(Π) is he se o all accep ed inpu s, and he amily o ec o se s accep ed by P
sys ems wi h one ac i e memb ane is P saccOP1(a0, c0).
3 Compa ison wi h a T ansi ional Model:
Ca aly ic P Sys ems wi h One Ca alys
The model o P sys ems wi h ac i e memb anes, o he case o one memb ane, can
be compa ed o he ollowing case o ansi ional P sys ems: non-dis ibu ed P sys ems
12 A. Alhazo , R. F eund
wi h one ca alys . Indeed, o each P sys em wi h one ac i e memb ane, he e exis s a
1-ca aly ic non-dis ibu ed P sys em wi h he same beha io , as non-coope a i e ules
wo k equi alen ly in bo h models: [ A→u]his equi alen o A→u, and sending ou
co esponds o pa icula ules wi h one ca alys , i.e., [ A]h→[ ]haco esponds wi h
cA →c(a, ou ), o , i wi hou es ic ing gene ali y we assume he se o symbols ha
may appea inside he sys em o be disjoin om he se o symbols ha may be sen o
he en i onmen , simply wi h cA →c(a, he e).
No ice ha o P sys em wi h ex e nal ou pu , we may igno e he objec s emaining
inside he sys em when i hal s (as explained in he nex sec ion), while o P sys ems
wi h in e nal ou pu , we should igno e he objec s sen ou . In his way, o he case
o in e nal ou pu , sending ou co esponds o a ca aly ic e asing, while o he case
o ex e nal ou pu sending ou co esponds o a ca aly ic enaming o a non- e minal
symbol in o a e minal symbol.
Hence, we can immedia ely conclude ha
Xα
βOP1(a0, c0)⊆XβOP1(ncoo, ca 1) o X∈ {N, P s, L}, α ∈ {in , ex }, β ∈ {−, T },
whe e β=−s ands o no speci ying a subsc ip .
One-ca aly ic P sys ems we e in es iga ed in [5], whe e some subclasses o P sys-
ems wi h one ca alys a e de ined and ce ain esul s on hei gene a i e powe a e
p esen ed. In pa icula , i was shown in [5] ha N−cOP1(wsepca 1) = NREG and
N−cOP1(complca 1)⊆N RC. Clea ly, he co esponding es ic ions migh also be
conside ed o pola iza ionless P sys ems wi h one ac i e memb ane, and such esul s
can be claimed as uppe bounds o he co esponding es ic ions, e.g.,
NOP1(wsep(a0, c0)) = NREG,
whe e he es ic ion o he weak sepa a ion can be e o mula ed o he model wi h ac i e
memb anes as ollows: he se Oo objec s is di ided in o h ee disjoin subse s O0,O00
and O000, such ha
•objec s a∈O0ha e no associa ed ules ( hey canno e ol e o be sen ou , so i hey
a e p oduced, hey emain idle inside he sys em),
•objec s a∈O00 ha e associa ed send-ou ules, bu no e olu ion ules,
•objec s a∈O000 ha e associa ed e olu ion ules, bu no send-ou ules.
I is wo h men ioning ha he addi ional equi emen om [5] ha he objec s p oduced
by a ca aly ic ule canno unde go a non-coope a i e ule is au oma ically sa is ied a e
ansla ion in o he ac i e memb ane case, so he only es ic ion emaining in he case
o weak sepa a ion is ha a ule o ype (a0) and a ule o ype (c0) a e no allowed o
compe e o he same objec . This es ic ion means, o ins ance, ha all objec s ha
ha e associa ed send-ou ules canno e ol e inside he sys em, hey simply wai he e
un il hey a e chosen o be sen ou .
A di e en es ic ion conside ed in [5] is comple e P sys ems (men ioned abo e as
complca 1). I can be e o mula ed in he model o pola iza ionless P sys ems wi h ac i e
memb anes as ollows: he e is no objec ha ing associa ed ules o ype (c0) and no ules
o ype (a0). This es ic ion means ha no objec is allowed o be empo a ily idle;
i i is no sen ou , hen i ei he e ol es immedia ely, o emains idle h oughou he
compu a ion. I ollows ha
NREG ⊆NOP1(compl(a0, c0)) ⊆N RC.
Pola iza ionless P Sys ems wi h One Ac i e Memb ane 13
I is in e es ing o no e ha weak sepa a ion and comple eness a e, in some sense, wo
opposi e equi emen s. While he la e one equi es ha all objec s which can be sen
ou mus e ol e i hey a e no chosen o be sen ou , he i s special case equi es ha
no objec s which can be sen ou a e allowed o e ol e. O cou se, in he mos gene al
case he e can be bo h kinds o objec s which can be sen ou .
4 Ex e nal ou pu
The i s goal o his sec ion is o p esen a educ ion o any P sys em wi h one ac i e
memb ane wi hou pola iza ions and ex e nal ou pu o an equi alen no mal o m. Then
we will use his no mal o m o p o e an uppe bound esul . We equi e he no mal o m
men ioned abo e o sa is y he ollowing condi ions:
•E e y objec appea s on he le side o some ule.
•The only e asing ule allowed is o he ini ial objec ; i so, he ini ial objec does no
appea on he igh side o any ule. (I we ha e an ini ial mul ise w, hen we add
he ule S→wwhe e Sis a new symbol now being he ini ial objec .)
We app oach his goal in a ew s ages. Fi s , we ema k ha , wi hou es ic ing gen-
e ali y, we may assume ha no objec s may emain inside he sys em when i hal s.
Indeed, le Oλbe he se o all objec s ha do no ha e associa ed ules. By adding ules
Rλ={[a→λ]1|a∈Oλ}, we make su e ha he e a e no objec s ha do no ha e
associa ed ules. On he o he side, adding ules Rλdoes no a ec he esul o a P sys-
em wi h ex e nal ou pu , since p ese ing/e asing objec s om Oλhas no al e na i es,
and i does no a ec he en i onmen .
Second, we ema k ha , wi hou es ic ing gene ali y, we may assume ha he ini ial
mul ise consis s o only one objec , say S, which does no appea in he igh side o
any ule. Indeed, o a P sys em s a ing wi h a mul ise ( ep esen ed by) w, conside an
equi alen P sys em s a ing wi h a mul ise consis ing o a new objec S, and adding
RS={[S→w]1} o R1.
Thi d, we claim ha o any P sys em sa is ying he assump ions men ioned abo e,
he e exis s a P sys em wi hou e asing ules (excep , possibly, o S).
P oo . Indeed, le us i s add ules R ={[a→# ]1|([ a→λ]1)∈R1o a= #},
whe e # is a new symbol, sha ed o all such educ ions, so i i appea s in a con igu a ion,
he sys em will ne e hal , and will he e o e no p oduce any esul . This ans o ma ion
will ce ainly no a ec he esul o he sys em, since e e y new compu a ion b anch will
no be p oduc i e, while he exis ing b anches will no be a ec ed (since by cons uc ion,
one can always apply some o he ule o ains ead o apping).
Second, compu e he se Oλo e asable objec s as ollows:
•Se Oλ o {a∈O|[a→λ]1∈R1,
•I [ a→u]1is in R1and u∈O∗
λ, hen add a o Oλ,
•I e a e he p e ious p ocedu e un il no mo e elemen s can be added o Oλ.
Thi d, eplace each ule [ a→u]1by ules [ a→u0]1, whe e he u0a e ob ained
om uby emo ing (in all possible combina ions) some objec s om Oλ. This will again
yield an equi alen sys em, because e e y symbol ha could e en ually be dele ed does
no ha e o be p oduced in he i s place.

14 A. Alhazo , R. F eund
Fou h, emo e all e asing ules. We claim ha he esul ing P sys em is s ill equi -
alen o he o iginal P sys em. Indeed, any objec (o he han S) ha should be e ased,
could be “p e-e ased” by no p oducing i in he i s place. Howe e , any objec ha
should e ol e can e ol e by o he ules, and any objec ha should be sen ou can be
sen ou (unless some compe ing objec is sen ou , in which case he simula ion would
no be co ec , so he compu a ion is disca ded by p oducing symbol #). 
Co olla y 1. LOP1(a0, c0)⊆CS.
P oo . Indeed, he o al numbe o objec s (inside and ou side he memb ane) ne e
dec eases h oughou he compu a ion (excep , possibly, o he emp y wo d, gene a ed
in one s ep), and he leng h o he esul ma ches he o al numbe o objec s when he
sys em hal s. 
We now p oceed wi h he lowe bound esul .
Theo em 1. LOP1(a0, c0)⊇REG •Pe m(REG).
P oo . Conside an alphabe Tand wo a bi a y egula languages o e T. Then he e
exis educed egula g amma s G1= (N1, T, P1, S1) and G2= (N2, T, P2, S2) gene a ing
hem, such as N1∩N2=∅. We cons uc he ollowing P sys em:
Π= (O=N1∪N2∪T∪T0, µ = [ ]1, w1=S1, R1),
T0={a0|a∈T},
R1={[A→aB ]1|(A→aB)∈P1} ∪ {[A→S2]1|(A→λ)∈P1}
∪ {[A→a0B]1|(A→aB)∈P2} ∪ {[A→λ]1|(A→λ)∈P2}
∪ {[a0→a0]1|a∈T} ∪ {[a]1→[ ]1a, [a0]1→[ ]1a|a∈T}.
The P sys em cons uc ed abo e gene a es L(G1)•L(G2), excep he symbols gene a ed
by he second g amma s a e p oduced in a p imed o m, and may unde go i ial ew i ing
o an a bi a ily long ime be o e hey a e sen ou , which ensu es ha a e gene a ing
a wo d om L(G1), any pe mu a ion o a wo d om L(G2) may be gene a ed. 
We now p esen a ew closu e p ope ies.
Lemma 1. The amily LOP1(a0, c0)is closed unde enaming mo phisms.
P oo . The s a emen ollows om applying he enaming mo phism o he send-ou
ules. 
Theo em 2. LOP1(a0, c0)is closed unde union.
P oo . The closu e unde union ollows om adding a new axiom and p oduc ions o
non-de e minis ic choice be ween mul iple axioms. 
Pola iza ionless P Sys ems wi h One Ac i e Memb ane 15
5 In e nal ou pu
In his case he en i onmen is no longe ele an : i does no ma e which symbol is
w i en in he igh side o a send-ou ule. The objec sen ou no longe a ec s he
esul , so sending ou is equi alen o a sequen ial e sion o e asing.
O cou se, we can gene a e P sREG wi h ules o ype (a0) co esponding o he ules
o a educed egula g amma . Hence,
P sin OP1(a0, c0)⊇P sREG.
Is i an open ques ion whe he non-semilinea numbe se s can be gene a ed, see also
he pa ial esul s ans e ed om he one-ca aly ic model, ecalled in Sec ion 3.
6 P sys ems wi h inpu
In his sec ion we show ha , no e y su p isingly, o P sys ems wi h one pola iza ionless
ac i e memb ane, hei accep ing powe is e en smalle han hei gene a i e powe . Mo e
exac ly, unless such a P sys em accep s all allowed inpu s, i only accep s speci ic ini e
se s. We s a by es ablishing some use ul ac s (we emind ha we use ⊆ o deno e he
submul ise ela ion, ∪ o deno e he union o mul ise s, and o deno e he di e ence
o mul ise s).
Lemma 2. Le Π∈OP1(a0, c0)be a P sys em wi h alphabe O, le [u]1⇒[ ]1α
in Π(α∈O∪ {λ}) Then o e e y mul ise u0⊆u, ei he [u0]1is al eady a hal ing
con igu a ion, o he e exis s a mul ise 0⊆ and β∈O∪{λ}such ha [u0]1⇒[ 0]1β
in Π.
P oo . In a ansi ion [ u]1⇒[ ]1α, one o h ee possible cases happen o e e y (copy
o ) objec ain u:
•ais ew i en by some ule o Πin o a (possibly emp y) mul ise , con ibu ing o ;
•ais sen ou by some ule o Πas α;
•a emains idle, con ibu ing o .
No e ha consis s exac ly o he esul ing objec s om he i s case and he objec s
o he hi d case. Mo e p ecisely, le he union o mul ise s o he igh side ules o
all copies o ew i en objec s be , and le he mul ise o idle objec s be i; hen,
= ∪ i. By de ini ion o he model, he second case was applied o a mos one (copy
o ) an objec in u. Also by de ini ion o he model, o each objec in he hi d case, he e
exis no ules o e ol e i , excep , possibly, send-ou ules, in which case α6=λ.
We ecall ha u0may be ob ained om uby e asing some (copies) o objec s. Fix
some co espondence o (copies o ) objec s in u0 o objec s in u, and conside a ansi ion
om u0by he same beha io o objec s in u0as o objec s in u:
• ew i en objec s will yield some submul ise 0
o ;
•β0will be p oduced in he en i onmen , β0=αo β0=λ;
•idle objec s will yield some submul ise 0
io i.
16 A. Alhazo , R. F eund
I is ob ious ha hese ules a e applicable, and ha 0
∪ 0
i⊆ . Maximali y also holds,
excep in one special si ua ion: when α6=λ, bu i was p oduced om a (copy o ) an
objec no in u0, while he e exis s a leas one objec b ha was idle in a ansi ion
[u]1⇒[ ]1α.
In his si ua ion, one objec b, ins ead o being idle, should be sen ou as β, and he
esul ing mul ise in he skin is 0= 0
∪ 0
i b(i his si ua ion does no happen, we ake
β=β0and 0= 0
∪ 0
i).
The e o e, [ u0]1⇒[ 0]1βin Πi a leas one (copy) o objec om u0 ell in o he
i s o he second case, and o he wise [ u0]1is al eady a hal ing con igu a ion. 
Lemma 3. I n∈N(Π), hen also n0∈N(Π) o any non-nega i e in ege n0≤n.
P oo . Le he alphabe o Πbe O, le he ini ial con en s o he skin memb ane o Πbe
w1, and le he inpu subalphabe o Πbe Σ. By de ini ion o accep ance, a numbe n
is accep ed i he e exis s a hal ing compu a ion in Πs a ing om con igu a ion [ u]1,
o some u∈w1Σn.
Conside he “sub-inpu ” o only n0objec s, i.e., u0∈w1Σnsuch ha u0⊆u. I
[u]1is al eady hal ing, hen so is [ u0]1, so he s a emen o he lemma holds; now we
assume he con a y: [ u]1⇒[ ]1α. By he p e ious lemma, in one s ep, ei he he
compu a ion wi h u0in he skin will immedia ely hal (and he s a emen o he lemma
again holds), o he e is a one-s ep ansi ion [ u0]1⇒[ 0]1βwi h 0⊆ .
I e a ing he applica ion o he p e ious lemma, by induc ion, we conclude ha he e
exis s a compu a ion s a ing om [ u0]1 ha will hal in a mos as many s ep as he
hal ing compu a ion s a ing om [ u]1 ha we conside ed. Hence n0∈N(Π). 
I ollows ha he accep ed se o numbe s is ei he N, o emp y, o i con ains all
in ege s less han o equal o he maximal accep ed numbe , so accep ing P sys ems
wi h one pola iza ionless ac i e memb ane canno be compu a ionally comple e, and P
sys ems wi h one pola iza ionless ac i e memb ane a e ob iously weake as accep o s
han as gene a o s:
NaccOP1(a0, c0)⊆ {∅,N} ∪ {{k|0≤k≤n} | n∈N}.
In he es o he sec ion we show, by all necessa y examples, ha his inclusion is
an equali y:
Π∅= (O={a}, Σ ={a}, µ = [ ]1, w1=a, R1={[a→a]1}, i0= 1).
ΠN= (O={a}, Σ ={a}, µ = [ ]1, w1=λ, R1={[a→λ]1}, i0= 1).
Πn= (O={ai|0≤i≤n}, Σ ={a0}, µ = [ ]1, w1=λ, R1, i0= 1),whe e
R1={[ai→ai+1 ]1,[ai]1→[ ]1a0|0≤i < n} ∪ {[an→an]1}.
Clea ly, Π∅accep s no hing, since wi h any inpu i s a s wi h a leas one objec , and
ca ies ou an in ini e compu a ion. On he o he end o he spec um, sys em ΠNaccep s
any inpu , by e asing i in one s ep and hal ing. Finally, we claim ha sys em Πnaccep s
exac ly se {k|0≤k≤n}. Indeed, any objec inc emen s i s index e e y s ep, unless
he objec is sen ou , o he index eaches n( o cing an in ini e compu a ion). I is easy
o see ha a mos ninpu objec s may be sen ou in his way; he sys em wi h inpu
(a0)khas a hal ing compu a ion i and only i k≤n.
Pola iza ionless P Sys ems wi h One Ac i e Memb ane 17
O e all, we ha e es ablished he ollowing esul s:
REG •Pe m(REG)⊆LOP1(a0, c0)⊆CS,
P sin OP1(a0, c0)⊆P sREG,
NαOP1(wsep(a0, c0)) = NREG, α ∈ {in , ex },
NREG ⊆NαOP1(compl(a0, c0)) ⊆N RC, α ∈ {in , ex },
NaccOP1(a0, c0) = {{k|0≤k≤n} | n∈N} ∪ {∅,N}.
7 Conclusions
In his pape we ha e conside ed he amily o languages gene a ed by pola iza ionless P
sys ems wi h one ac i e memb ane. A no mal o m was gi en o ex e nal ou pu case. I
was han shown ha he amily o gene a ed languages lies be ween REG •Pe m(REG)
and CS, and is closed unde union and enaming mo phisms. The exac cha ac e iza ion
is an open ques ion, bu pola iza ionless P sys ems wi h one ac i e memb ane can be
simula ed by (and a e, he e o e, a mos as powe ul as) P sys ems wi h one ca alys ,
ans e ing wo esul s on he gene a i e powe o wo es ic ed classes, independen ly
om he ou pu egion.
Then we also conside ed se s o ec o s o numbe s gene a ed in e nally, as well as se s
o ec o s o numbe s accep ed by pola iza ionless P sys ems wi h one ac i e memb ane.
Se e al ques ions abou he amilies o hese se s a e s ill open, oo.
Ano he possible gene aliza ion ha can be conside ed is o also allow ules o ype
(b0) o b ing objec s om he en i onmen back o he skin. No e ha such sys ems
would s ill co espond o a subclass o 1-ca aly ic P sys ems, bu some de ini ions would
ha e o be e ised, as well as all ela ed esul s.
We ha e p o ed ha accep ing P sys ems wi h one pola iza ionless ac i e memb ane
a e no compu a ionally comple e, unlike hose wi h wo pola iza ions o like hose wi h
memb ane c ea ion and dissolu ion, o wi h mul iple memb anes and memb ane dissolu-
ion.
The ques ions abou he compu a ional powe o pola iza ionless P sys ems wi h
ac i e memb anes wi h 2 and 3 memb anes in he ini ial con igu a ion a e s ill open, as
well as o pola iza ionless sys ems wi h less han 7 memb anes and wo labels, o o all
pola iza ionless sys ems wi h only one label.
Re e ences
1. A. Alhazo : P Sys ems wi hou Mul iplici ies o Symbol-Objec s. In o ma ion P o-
cessing Le e s 100, 3, 2006, 124–129.
2. A. Alhazo , C. Ciubo a u, Yu. Rogozhin, S. I ano : The Family o Languages Gene -
a ed by Non-Coope a i e Memb ane Sys ems. In: Gh. P˘aun, M.J. P´e ez-Jim´enez, A.
Riscos-N´u˜nez, G. Rozenbe g, A. Salomaa: Memb ane Compu ing, 11 h In e na ional
Con e ence, CMC11, Jena, Re ised Selec ed Pape s, Lec u e No es in Compu e Sci-
ence 6501, 2011, 65–79.