P io i ies, P omo e s and Inhibi o s in
De e minis ic Non-Coope a i e P Sys ems
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
[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
[email p o ec ed]
Summa y. Memb ane sys ems (wi h symbol objec s) a e dis ibu ed con olled mul ise
p ocessing sys ems. Non-coope a i e P sys ems wi h ei he p omo e s o inhibi o s (o
weigh no es ic ed o one) a e known o be compu a ionally comple e. Since ecen ly,
i is known ha he powe o he de e minis ic subclass o such sys ems is sub egula . We
p esen new esul s on he weigh o p omo e s and inhibi o s, as well as o cha ac e izing
he sys ems wi h p io i ies only.
1 In oduc ion
The mos amous memb ane compu ing model whe e de e minism is a c i e ion o
uni e sali y e sus decidabili y is he model o ca aly ic P sys ems, see [3] and [6].
I is also known ha non-coope a i e ew i ing P sys ems wi h ei he p omo e s
o inhibi o s a e compu a ionally comple e, [2]. Mo eo e , he p oo sa isfies some
addi ional p ope ies:
•Ei he p omo e s o weigh 2 o inhibi o s o weigh 2 a e enough.
•The sys em is non-de e minis ic, bu i es o es he p e ious configu a ion i
he guess is w ong, which leads o co ec simula ions wi h p obabili y 1.
Recen ly, in [1] i was shown ha he compu a ional comple eness canno
be achie ed by de e minis ic non-coope a i e sys ems wi h p omo e s, inhibi o s
and p io i ies (in maximally pa allel o asynch onous mode, unlike he sequen ial
mode), and cha ac e iza ions o he co esponding classes we e ob ained:
28 A. Alhazo , R. F eund
NFIN ∪coNFIN =Nde aOPasyn
1(ncoo, p o1,∗, inh1,∗)
=Nde aOPmaxpa
1(ncoo, p o1,∗)
=Nde aOPmaxpa
1(ncoo, inh1,∗)
=Nde aOPasyn
1(ncoo, (p o∗,∗, inh∗,∗)∗, p i)
=Nde aOPmaxpa
1(ncoo, (p o∗,∗, inh∗,∗)∗, p i),bu
NRE =Nde aOP sequ
1(ncoo, p o1,1, inh1,1).
A ew in e es ing ques ions ha e been le open. Fo ins ance, wha is he powe
o P sys ems, e.g., in he maximally pa allel mode, when we only use p io i ies, o
when we es ic he weigh o he p omo ing/inhibi ing mul ise s. These a e he
ques ions we add ess in his pape .
2 De ini ions
An alphabe is a fini e non-emp y se Vo abs ac symbols. The ee monoid
gene a ed by Vunde he ope a ion o conca ena ion is deno ed by V∗; he emp y
s ing is deno ed by λ, and V∗ {λ}is deno ed by V+. The se o non-nega i e
in ege s is deno ed by N; a se So non-nega i e in ege s is called co- ini e i N S
is fini e. The amily o all fini e (co-fini e) se s o non-nega i e in ege s is deno ed
by NF IN (coNFIN, espec i ely). The amily o all ecu si ely enume able se s
o non-nega i e in ege s is deno ed by NRE. In he ollowing, we will use ⊆bo h
o he subse as well as he submul ise ela ion.
Since fla ening he memb ane s uc u e o a memb ane sys em p ese es bo h
de e minism and he model, in he ollowing we es ic ou sel es o conside mem-
b ane sys ems as one- egion mul ise ew i ing sys ems.
A(one- egion) memb ane sys em (P sys em) is a uple
Π= (O, Σ, w, R′),
whe e Ois a fini e alphabe , Σ⊆Ois he inpu sub-alphabe , w∈O∗is a s ing
ep esen ing he ini ial mul ise , and R′is a se o ules o he o m :u→ ,
u∈O+, ∈O∗.
A configu a ion o he sys em Πis ep esen ed by a mul ise o objec s om O
con ained in he egion, he se o all configu a ions o e Ois deno ed by C(O).
A ule :u→ is applicable i he cu en configu a ion con ains he mul ise
specified by u. Fu he mo e, applicabili y may be con olled by con ex condi ions,
specified by pai s o se s o mul ise s.
De ini ion 1. Le Pi,Qibe ( ini e) se s o mul ise s o e O,1≤i≤m. A ule
wi h con ex condi ions ( , (P1, Q1),· · · ,(Pm, Qm)) is applicable o a con igu a ion
Ci is applicable, and he e exis s some j∈ {1,· · · , m} o which
• he e exis s some p∈Pjsuch ha p⊆Cand
•q⊆ C o all q∈Qj.
Con ols in De e minis ic Non-Coope a i e P Sys ems 29
In wo ds, con ex condi ions a e sa isfied i he e exis s a pai o se s o mul ise s
(called p omo e se and inhibi o se , espec i ely) such ha a leas one mul ise
in he p omo e se is a submul ise o he cu en configu a ion, and no mul ise
in he inhibi o se is a submul ise o he cu en configu a ion.
De ini ion 2. AP sys em wi h con ex condi ions and p io i ies on he ules is a
cons uc
Π= (O, Σ, w, R′, R, >),
whe e (O, Σ, w, R′)is a (one- egion) P sys em as de ined abo e, Ris a se o ules
wi h con ex condi ions and >is a p io i y ela ion on he ules in R; i ule ′has
p io i y o e ule , deno ed by ′> , hen canno be applied i ′is applicable.
Th oughou he pape , we will use he wo d con ol o mean ha a leas one o
hese ea u es is allowed (con ex condi ions o p omo e s o inhibi o s only and
e en ually p io i ies).
In he sequen ial mode (sequ), a compu a ion s ep consis s in he non-
de e minis ic applica ion o one applicable ule , eplacing i s le -hand side
(lhs ( )) wi h i s igh -hand side ( hs ( )). In he maximally pa allel mode
(maxpa ), a mul ise o applicable ules may be chosen non-de e minis ically o
be applied in pa allel o he unde lying configu a ion o disjoin submul ise s, pos-
sibly lea ing some objec s idle, unde he condi ion ha no u he applicable ule
can be added o ha mul ise (i.e., no supe mul ise o he chosen mul ise is
applicable o he same configu a ion). Maximal pa allelism is he mos common
compu a ion mode in memb ane compu ing, see also Defini ion 4.8 in [5]. In he
asynch onuous mode (asyn), any posi i e numbe o applicable ules may be cho-
sen non-de e minis ically o be applied in pa allel o he unde lying configu a ion,
o disjoin submul ise s. The compu a ion s ep be ween wo configu a ions Cand
C′is deno ed by C→C′, hus yielding he bina y ela ion ⇒:C(O)×C(O). A
compu a ion hal s when he e a e no ules applicable o he cu en configu a ion
(hal ing con igu a ion) in he co esponding mode.
The compu a ion o a gene a ing P sys em s a s wi h w, and i s esul is |x|
i i hal s, an accep ing sys em s a s wi h wx,x∈Σ∗, and we say ha |x|is
i s esul s – is accep ed – i i hal s. The se o numbe s gene a ed/accep ed by a
P sys em wo king in he mode αis he se o esul s o i s compu a ions o all
x∈Σ∗and deno ed by Nα
g(Π) and Nα
a(Π), espec i ely. The amily o se s o
numbe s gene a ed/accep ed by a amily o (one- egion) P sys ems wi h con ex
condi ions and p io i ies on he ules wi h ules o ype βwo king in he mode
αis deno ed by NδOPα
1(β, (p ok,l, inhk′,l′)d, p i)wi h δ=g o he gene a ing
and δ=a o he accep ing case; ddeno es he maximal numbe min he ules
wi h con ex condi ions ( , (P1, Q1),· · · ,(Pm, Qm)); kand k′deno e he maximum
numbe o p omo e s/inhibi o s in he Piand Qi, espec i ely; land l′indica e
he maximum o weigh s o p omo o s and inhibi o s, espec i ely. I any o hese
numbe s k,k′,l,l′is no bounded, we eplace i by ∗. As ypes o ules we a e
going o dis inguish be ween coope a i e (β=coo) and non-coope a i e (i.e., he
le -hand side o each ule is a single objec ; β=ncoo) ones.
30 A. Alhazo , R. F eund
In he case o accep ing sys ems, we also conside he idea o de e minism,
which means ha in each s ep o any compu a ion a mos one (mul ise o )
ule(s) is applicable; in his case, we w i e de a o δ.
In he li e a u e, we find a lo o es ic ed a ian s o P sys ems wi h con-
ex condi ions and p io i ies on he ules, e.g., we may omi he p io i ies o
he con ex condi ions comple ely. I in a ule ( , (P1, Q1),· · · ,(Pm, Qm)) we ha e
m= 1, we say ha ( , (P1, Q1)) is a ule wi h a simple con ex condi ion, and
we omi he inne pa en heses in he no a ion. Mo eo e , con ex condi ions only
using p omo e s a e deno ed by |p1,··· ,pn, meaning ( , {p1,· · · , pn},∅), o , equi a-
len ly, ( , (p1,∅),· · · ,(pn,∅)); con ex condi ions only using inhibi o s a e deno ed
by |¬q1,··· ,¬qn, meaning ( , λ, {q1,· · · , qn}), o |¬{q1,··· ,qn}. Likewise, a ule wi h
bo h p omo e s and inhibi o s can be specified as a ule wi h a simple con ex con-
di ion, i.e., |p1,··· ,pn,¬q1,··· ,¬qns ands o ( , {p1,· · · , pn},{q1,··· , qn}). Finally,
p omo e s and inhibi o s o weigh one a e called a omic.
Rema k 1. I we do no conside de e minism, hen ( he effec o ) he ule
( , (P1, Q1),· · · ,(Pm, Qm)) is equi alen o ( he effec o ) he collec ion o ules
{( , Pj, Qj)|1≤j≤m}, no ma e in which mode he P sys em is wo king (ob-
iously, he p io i y ela ion has o be adap ed acco dingly, oo).
Rema k 2. Le ( , {p1,· · · , pn}, Q) be a ule wi h a simple con ex condi ion; hen
we claim ha ( he effec o ) his ule is equi alen o ( he effec o ) he collec ion
o ules
{( , {pj}, Q ∪ {pk|1≤k < j})|1≤j≤m}
e en in he he case o a de e minis ic P sys em: I he fi s p omo e is chosen
o make he ule applicable, we do no ca e abou he o he p omo e s; i he
second p omo e is chosen o make he ule applicable, we do no allow p1 o
appea in he configu a ion, bu do no ca e abou he o he p omo e s p3 o pm;
in gene al, when p omo e pjis chosen o make he ule applicable, we do no
allow p1 o pj−1 o appea in he configu a ion, bu do no ca e abou he o he
p omo e s pj+1 o pm; finally, we ha e he ule {( , {pm}, Q ∪ {pk|1≤k < m})}.
I adding {pk|1≤k < j} o Qhas he effec o p ohibi ing he p omo o pj om
enabling he ule o be applied, his makes no ha m as in his case one o he
p omo e s pk, 1 ≤k < j, mus ha e he possibili y o enabling o be applied.
By cons uc ion, he domains o he new con ex condi ions now a e disjoin , so
his ans o ma ion does no c ea e (new) non-de e minism. In a simila way, his
ans o ma ion may be pe o med on con ex condi ions which a e no simple.
The e o e, wi hou es ic ing gene ali y, he se o p omo e s may be assumed o
be a single on. In his case, we may omi he b aces o he mul ise no a ion o
he p omo e mul ise and w i e ( , p, Q).
Rema k 3. As in a P sys em (O, Σ, w, R′, R, >) he se o ules R′can easily be
deduced om he se o ules wi h con ex condi ions R, we omi R′in he de-
sc ip ion o he P sys em. Mo eo e , o sys ems ha ing only ules wi h a simple
Con ols in De e minis ic Non-Coope a i e P Sys ems 31
con ex condi ion, we omi din he desc ip ion o he amilies o se s o numbe s
and simply w i e
NδOPα
1(β, p ok,l, inhk′,l′, p i).
Mo eo e , each con ol mechanism no used can be omi ed, e.g., i no p io i ies
and only p omo e s a e used, we only w i e NδOPα
1(β, p ok,l).
3 Resul s
3.1 Recen esul s
We fi s ecall om [1] he bounding ope a ion o e mul ise s, wi h a pa ame e
k∈Nas ollows:
o u∈O∗,bk(u) = wi h | |a= min(|u|a, k) o all a∈O.
The mapping bk“c ops” he mul ise s by emo ing copies o e e y objec a
p esen in mo e han kcopies un il exac ly k emain. Fo wo mul ise s u, u′,
bk(u) = bk(u′) i o e e y a∈O, ei he |u|a=|u′|a< k, o |u|a≥kand
|u′|a≥k. Mapping bkinduces an equi alence ela ion, mapping O∗in o (k+ 1)|O|
equi alence classes. Each equi alence class co esponds o speci ying, o each a∈
O∗, whe he no copy, one copy, o · · · k−1 copies, o “kcopies o mo e” a e
p esen . We deno e he ange o bkby {0,· · · , k}O.
Lemma 1. [1] Con ex condi ions a e equi alen o p edica es de ined on bound-
ings.
Theo em 1. [1] P io i ies a e subsumed by condi ional con ex s.
Rema k 4. I is wo h o no e, see also [4], ha i no o he con ol is used, he
p io i ies can be mapped o se s o a omic inhibi o s. Indeed, a ule is inhibi ed
p ecisely by he le side o each highe p io i y ule. This is s aigh o wa d in
case when he p io i y ela ion is assumed o be a pa ial o de .
I i is no , hen bo h he seman ics o compu a ion in P sys ems and he
educ ion o p io i ies o inhibi o s is a bi mo e complica ed, bu he claim s ill
holds.
Fix an a bi a y de e minis ic con olled non-coope a i e P sys em. Take kas
he maximum o size o all mul ise s in all con ex condi ions. Then, he bounding
does no influence applicabili y o ules, and bk(u) is hal ing i and only i uis
hal ing. We ecall ha bounding induces equi alence classes p ese ed by any
compu a ion.
Lemma 2. [1] Assume u→xand →y. Then bk(u) = bk( )implies bk(x) =
bk(y).
Co olla y 1. [1] I bk(u) = bk( ), hen uis accep ed i and only i is accep ed.

32 A. Alhazo , R. F eund
Finally, he “a mos NFIN ∪coNFIN” pa o cha ac e izing
Nde aOPmaxpa
1(ncoo, (p o∗,∗, inh∗,∗)∗, p i)
( he main heo em o [1]) is shown wi h he ollowing a gumen :
Each equi alence class induced by bounding is comple ely accep ed o
comple ely ejec ed. I no infini e equi alence class is accep ed, hen he
accep ed se is fini e (con aining numbe s no exceeding (k−1) · |O|). I
a leas one infini e equi alence class is accep ed, hen he ejec ed se is
fini e (con aining numbe s no exceeding (k−1) · |O|).
3.2 P io i ies only
We s a wi h an example how o de e minis ically ew i e an objec depending
on he p esence o absence o objec a.
Example 1.
Π= ({a, A, A′, , ′, +, −},{a}, A, R, R, >),whe e
R={1 : → ′,2 : a→λ, 3 : A→A′,4 : ′→ +,5 : ′→ −,6 : A′→λ},
>={a→λ > A →A′, A →A′> ′→ −, A′→λ > ′→ +}.
Indeed, objec wai s o one s ep by becoming ′, while Ahas o change o
A′o wai , depending on he p esence o a. Then, objec ′becomes ei he +
o −, depending on whe he Ao A′is p esen . No ice, e.g., how adding ei he
ule +→ +o ule −→ −leads o a sys em accep ing {0}o N {0}. O
cou se, accep ing only ze o could ins ead be done by a i ial one- ule sys em, bu
his example is impo an because such a deciding subsys em can be used, wi h
sui able delays, as a building block o checking combina ions o p esence/absence
o mul iple symbols.
We now p oceed wi h cha ac e izing sys ems wi h p io i ies only.
Theo em 2. Nde aOPmaxpa
1(ncoo, p i) = {Nk,Nk∪ {0} | k≥0} ∪ {{0},∅}.
P oo . We al eady know ha he p io i ies co espond o se s o a omic inhibi o s.
This means ha each sys em accep s a union o some equi alence classes induced
by bounding b1(i.e., checking p esence/absence). No e ha a ious combina ions
o “= 0” and “≥1” yield nume ic se s {0}and Nk(whe e k > 0 is he numbe o
diffe en symbols p esen ). The amily o all unions o hese se s is
Fp i ={Nk,Nk∪ {0} | k≥0} ∪ {{0},∅}.
I ollows ha Nde aOPmaxpa
1(ncoo, p i)⊆Fp i.
We p oceed wi h he con e se inclusion. Le Π0= ({a, },{a}, , R, R, >), hen
R={ → }and emp y ela ion >yields ∅. To accep {0}, we ins ead ake
R={a→a}and emp y ela ion >.
Con ols in De e minis ic Non-Coope a i e P Sys ems 33
Now suppose we wan o accep Nk. I would suffice o coun ha we ha e a
leas one o each objec s a1,· · · , ak(we ecall ha we need o accep a leas one
inpu o size j o each j≥k, o ejec he inpu i j > k). To accep Nk∪ {0}
ins ead, we may fi s pe o m a simul aneous check o he absence o all inpu
symbols.
Using he idea om Example 1, we cons uc he sys em
Π1= (O, Σ ={ai,0|1≤i≤k}, A0,0· · · Ak,0, R, R, >),whe e
O={ai,j |1≤i≤k, 0≤j≤i+ 1} ∪ {Ai,j |0≤i≤k, 0≤j≤i+ 2}
∪ { , z, p}∪{ i|0≤i≤i+ 1},
R={1 : ai,j →ai,j+1 |1≤i≤k, 0≤j≤i}
∪ {2 : Ai,j →Ai,j+1 |1≤i≤k, 0≤j≤i+ 1}
∪ {3 : → 0,4 : 0→z, 5 : 0→ 1,6 : p→p}
∪ {7 : i→ i+1,8 : i→p|1≤i≤k},
>={ai,0→ai,1> A0,0→A0,1|1≤i≤k}
∪ {A0,0→A0,1> 0→z, A0,1→A0,2> 0→ 1}
∪ {ai,i →ai,i+1 > Ai,i →Ai,i+1 |1≤i≤k}
∪ {Ai,i →Ai,i+1 > i→p, Ai,i+1 →Ai,i+2 > i→ i+1}.
Such sys em accep exac ly Nk∪ {0}. Indeed, a e fi s s ep, A0,0is p esen i all
inpu symbols we e absen , o he wise A0,1is p esen ins ead. Fo any i, 1 ≤i≤k,
a e s ep 1+i, objec Ai,i is p esen i inpu symbol ai,0was p esen in he inpu ,
and o he wise Ai,i+1 is p esen ins ead. These “decision symbols” a e used by i,
0≤i≤k, o build he “p esence pic u e”. We ecall ha i suffices o accep when
all inpu symbols a e p esen , o when none o hem is p esen . In he fi s case,
0becomes z, and he compu a ion only con inues by ules om g oups 1 and 2,
leading o hal ing. Le us assume ha he fi s so he inpu symbols a e p esen ,
s<k. Then, 0becomes 1, and hen ···, s, and hen he absence o s+1 will
change sin o p, leading o an infini e compu a ion. Finally, i all inpu symbols
a e p esen , hen he compu a ion will hal wi h k+1.
I emains o no ice ha accep ing Nk,k≥1, can be done by simply adding a
ule z→z.
3.3 P omo e s o inhibi o s o weigh 2
We s a om examples, illus a ing de e minis ic choice o ew i ing p, depending
on whe he objec ais absen , occu s exac ly once, o occu s mul iple imes.
Example 2. Symbols A,Ba e p imed i inpu is p esen (mul iple inpu symbols
a e p esen ). Then p imed and unp imed symbols o m mu ually exclusi e condi-
ions.
34 A. Alhazo , R. F eund
Π= (O={p, p′, p′′, p>, p1, p0, A, B, a}, Σ ={a}, pAB, R′, R),whe e
R′={1 : p→p′,2 : A→A′,3 : B→B′,
4 : p′→p>,5 : p′→p′′,6 : p′′ →p1,7 : p′′ →p0},
R′={1 : p→p′,2 : A→A′|a,3 : B→B′|aa,
4 : p′→p>|B,5 : p′→p′′|B′,6 : p′′ →p1|A,7 : p′′ →p0|A′}.
Example 3. No ice ha i we eplace all p omo e s by inhibi o s wi h he same
con ex , he effec o blocking ules will be e e sed, bu he esul will be he same.
Indeed, he ole o A′and B′will swi ch om ound aand ound aa, espec i ely,
o no ound aand no ound aa, espec i ely.
R′={1 : p→p′,2 : A→A′|¬a,3 : B→B′|¬aa,
4 : p′→p>|¬B,5 : p′→p′′|¬B′,6 : p′′ →p1|¬A,7 : p′′ →p0|¬A′}.
We now p oceed wi h cha ac e izing sys ems wi h con ex o weigh wo. No ice
ha we al eady know ha hei powe does no exceed NFIN ∪coNFIN.
Theo em 3. Nde aOPmaxpa
1(ncoo, p o2) =
Nde aOPmaxpa
1(ncoo, inh2) = NFIN ∪coNFIN.
P oo . We use he echnique om Example 2 o all inpu symbols and combine he
ex ac ed in o ma ion. Conside an a bi a y fini e se M, and le max(M) = n.
We will use he ollowing s a egy: o accep a numbe j∈M, we will accep an
inpu mul ise wi h exac ly jsymbols appea ing once, and no hing else. To accep
he complemen o M, we spli i in o se s M′′ ={j|j > n}and M′={j|j≤
n, j /∈M}. While M′is ea ed simila ly o M, i only emains o accep M′′,
which is co e ed by equi alence classes when all symbols a e p esen , and a leas
one is p esen mo e han once.
Π= (O, Σ ={ai|1≤i≤n}, A1· · · AnB1···Bn, R′, R),whe e
O={ i,j, Ti,j , ′
i,j, T ′
i,j |1≤i≤n+ 1,0≤j≤n}
∪ {Ai, A′
i, Bi, B′
i|1≤i≤n}∪{ , #},
R′={ i,j →Ti+1,j+1, Ti,j →Ti+1,j+1, i,j → ′
i,j, Ti,j →T′
i,j,
′
i,j → i+1,j+1, T′
i,j →Ti+1,j+1, ′
i,j → i+1,j, T ′
i,j →Ti+1,j,
Ai→A′
i, Bi→B′
i|1≤i≤n}∪{ → 1,0#→#}
∪ {Ti,n+1 →#|1≤i≤n}∪{ i,n+1 →#|i /∈M},
R={ i,j →Ti+1,j+1|Bi, Ti,j →Ti+1,j+1|Bi, i,j → ′
i,j|B′
i, Ti,j →T′
i,j|B′
i,
′
i,j → i+1,j+1|Ai, T′
i,j →Ti+1,j+1|Ai, ′
i,j → i+1,j|A′
i, T′
i,j →Ti+1,j|A′
i,
Ai→A′
i|ai, Bi→B′
i|aiai|1≤i≤n}∪{ → 1,0,#→#}
∪ {Ti,n+1 →#|1≤i≤n}∪{ i,n+1 →#|i /∈M}.
Con ols in De e minis ic Non-Coope a i e P Sys ems 35
The meaning o Ti,n+1 is ha exac ly iinpu symbols a e p esen , and a leas one
o hem is p esen mul iple imes. The meaning o i,n+1 is ha he inpu consis ed
o exac ly idiffe en symbols. This is how an a bi a y fini e se is accep ed. To
accep ins ead o Mi s complemen , eplace i /∈Mby i∈Mand emo e ule
Tn,n+1 →#. The e o e, de e minis ic P sys ems wi h p omo e s o weigh wo
accep exac ly NFIN ∪coNFIN.
Fo he inhibi o coun e pa , no ice ha he compu a ion o he numbe o
diffe en symbols p esen , as well as checking i any symbol is p esen mul iple
imes, s ays co ec by simply changing p omo e s o he inhibi o s wi h he same
condi ion, jus like in Example 3. Rules p ocessing objec s i,n+1 and Ti,n+1 will
ha e an opposi e effec , accep ing he complemen o he se accep ed by he
sys em wi h p omo e s, again yielding NFIN ∪coNFIN.
I is s ill open whe he only inhibi o s in he ules o only p omo e s in he
ules a e sufficien o yield NF IN ∪coNF IN wi h he asynch onuous mode, oo.
4 Conclusion
We ha e shown he cha ac e iza ions o de e minis ic non-coope a i e P sys ems
wi h inhibi o s o weigh 2, wi h p omo e s o weigh 2, and wi h p io i ies. The
fi s wo cases did no educe he accep ing powe wi h espec o un es ic ed
weigh .
Re e ences
1. A. Alhazo , R. F eund: Asynch onuous and Maximally Pa allel De e minis ic Con-
olled Non-Coope a i e P Sys ems Cha ac e ize N F IN and coN F IN .The Ten h
B ains o ming Week in Memb ane Compu ing, ol. 1, Se illa, 2012, 25–34, and Mem-
b ane Compu ing - 13 h In e na ional Con e ence, CMC13, Budapes (E. Csuhaj-
Va j´u, M. Gheo ghe, G. Rozenbe g, A. Salomaa, Gy. Vaszil, Eds.), Lec u e No es in
Compu e Science 7762, 2013, 101-111.
2. A. Alhazo , D. Sbu lan: Ul ima ely Confluen Rew i ing Sys ems. Pa allel Mul ise -
Rew i ing wi h Pe mi ing o Fo bidding Con ex s. In: G. Mau i, Gh. P˘aun, M.J.
P´e ez-Jim´enez, G. Rozenbe g, A. Salomaa: Memb ane Compu ing, 5 h In e na ional
Wo kshop, WMC 2004, Milano, Re ised Selec ed and In i ed Pape s, Lec u e No es
in Compu e Science 3365, Sp inge , 2005, 178–189.
3. R. F eund, L. Ka i, M. Oswald, P. Sos´ık: Compu a ionally Uni e sal P Sys ems
wi hou P io i ies: Two Ca alys s a e Sufficien , Theo e ical Compu e Science 330,
2, 2005, 251–266.
4. R. F eund, M. Kogle , M. Oswald, A Gene al F amewo k o Regula ed Rew i ing
Based on he Applicabili y o Rules. In: J. Kelemen, A. Kelemeno ´a, Compu a ion,
Coope a ion, and Li e, Sp inge , Lec u e No es in Compu e Science 6610, 2011,
35–53.