Asynch onous 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 ∪coN F IN
A iom Alhazo 1,2and Rudol F eund3
1Uni e si `a degli S udi di Milano-Bicocca
Dipa imen o di In o ma ica, Sis emis ica e Comunicazione
Viale Sa ca 336, 20126 Milano, I aly
[email p o ec ed]
2Ins 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]
3Facul 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. 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. In his pape
we show ha he powe o he de e minis ic subclass o such sys ems is compu a ionally
comple e in he sequen ial mode, bu only sub egula in he asynch onous mode and in
he maximally pa allel mode.
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 [2] and [4].
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, [1]. 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.
The pu pose o his pape is o o mally p o e ha compu a ional comple eness
canno be achie ed by de e minis ic sys ems when wo king in he asynch onous
o in he maximally pa allel mode.
26 A. Alhazo , R. F eund
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 NFIN (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. A ule wi h con ex condi ions ( , (P1, Q1),· · · ,(Pm, Qm)) is appli-
cable 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.
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.
A Cha ac e iza ion o N F IN ∪coN F IN 27
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 ), mul iple applicable ules may be chosen non-de e minis ically o be ap-
plied in pa allel o he unde lying configu a ion o disjoin submul ise s, possibly
lea ing some objec s idle, unde he condi ion ha no u he ule is applicable o
hem. In he asynch onous mode (asyn), any posi i e numbe 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. The compu a ion s ep be ween wo con-
figu 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 e 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.
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.
28 A. Alhazo , R. F eund
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).
Example 1. Conside an a bi a y fini e se Ho numbe s. Choose K= max (H)+
1; hen we cons uc he ollowing de e minis ic accep ing P sys em wi h p omo e s
and inhibi o s:
Π= (O, {a}, s0 0· · · K, R′, R),
O={a}∪{si, i|0≤i≤K},
R′={si→si+1 |0≤i≤K−1}∪{ i→ i|0≤i≤K},
R={si→si+1|ai+1 ,|0≤i≤K−1}
∪{ i→ i|si,¬ai+1 ,|0≤i < K, i /∈H}∪ { K→ K|sK}.
The sys em s ep by s ep, by he applica ion o he ule si→si+1|ai+1 , 0 ≤i < K,
checks i (a leas ) i+ 1 copies o he symbol aa e p esen . I he compu a ion
s ops a e is eps, i.e., i he inpu has consis ed o exac ly icopies o a, hen
his inpu is accep ed i and only i i∈H, as exac ly in his case he sys em does
no s a an infini e loop wi h using i→ i|si,¬ai+1 . I he inpu has con ained
mo e han max (H) copies o a, hen he sys em a i es in he s a e sKand will
loop o e e wi h K→ K|sK. The e o e, exac ly His accep ed. To accep he
complemen o Hins ead, we simply change i /∈H o i∈Hand as well omi he
ule K→ K|sK. I is easy o see ha o he maximally pa allel mode, we can
A Cha ac e iza ion o N F IN ∪coN F IN 29
eplace each ule i→ i|si,¬ai+1 by he co esponding ule i→ i|si; in his case,
his ule may be applied wi h s ill some abeing p esen while he sys em passes
h ough he s a e si, bu i will no ge in o an infini e loop in ha case.
In sum, we ha e shown ha
Nde aOPasyn
1(ncoo, (p o1,∗, inh1,∗)1)⊇FIN ∪coNF IN
and
Nde aOPmaxpa
1(ncoo, p o1,∗)⊇FIN ∪coNF IN.
Example 2. Fo P sys ems wo king in he maximally pa allel way we can e en
cons uc a sys em wi h inhibi o s only:
Π= (O, {a}, sK, R),
O={a, }∪{si|0≤i≤K},
R′={si→ si−1, si→si|1≤i≤K}∪{ →λ, s0→s0},
R={si→ si−1|¬ai|1≤i≤K}
∪ { →λ}∪{si→si|¬ |0≤i≤K, i /∈H}.
This cons uc ion does no ca y o e o he case o he asynch onous mode, as
he ule →λis applied in pa allel o he ules si→ si−1|¬aiun il he inpu ai
is eached. In his case, he sys em cano change he s a e sianymo e, and hen i
s a s o loop i and only i i /∈H. To accep he complemen o Hins ead, change
i∈H o i /∈H, i.e., in sum, we ha e p o ed ha
Nde aOPmaxpa
1(ncoo, inh1,∗)⊇FIN ∪coNF IN.
As we shall show la e , all he inclusions s a ed in Example 1 and Example 2
a e equali ies.
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 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).
2.1 Regis e machines
In wha ollows we will need o simula e egis e machines; he e we b iefly ecall
hei defini ion and some o hei compu a ional p ope ies. A egis e machine is
a uple M= (m, B, l0, lh, P), whe e mis he numbe o egis e s, Pis he se o
ins uc ions bijec i ely labeled by elemen s o B,l0∈Bis he ini ial label, and
lh∈Bis he final label. The ins uc ions o Mcan be o he ollowing o ms:

30 A. Alhazo , R. F eund
•l1: (ADD (j), l2, l3), wi h l1∈B {lh},l2, l3∈B, 1 ≤j≤m.
Inc ease he alue o egis e jby one, and non-de e minis ically jump o in-
s uc ion l2o l3. This ins uc ion is usually called inc emen .
•l1: (SUB (j), l2, l3), wi h l1∈B {lh},l2, l3∈B, 1 ≤j≤m.
I he alue o egis e jis ze o hen jump o ins uc ion l3, o he wise dec ease
he alue o egis e jby one and jump o ins uc ion l2. The wo cases o his
ins uc ion a e usually called ze o- es and dec emen , espec i ely.
•lh:HALT . S op he execu ion o he egis e machine.
A egis e machine is de e minis ic i l2=l3in all i s ADD ins uc ions. A
con igu a ion o a egis e machine is desc ibed by he con en s o each egis e
and by he alue o he p og am coun e , which indica es he nex ins uc ion o
be execu ed. Compu a ions s a by execu ing he fi s ins uc ion o P(labeled
wi h l0), and e mina e wi h eaching a HALT -ins uc ion.
Regis e machines p o ide a simple uni e sal compu a ional model [5]. We he e
conside egis e machines used as accep ing o as gene a ing de ices. In accep ing
egis e machines, a ec o o non-nega i e in ege s is accep ed i and only i he
egis e machine hal s ha ing i as inpu . Usually, wi hou loss o gene ali y, we
may assume ha he ins uc ion lh:HALT always appea s exac ly once in P,
wi h label lh. In he gene a i e case, we s a wi h emp y egis e s and ake he
esul s o all possible hal ing compu a ions.
3 Resul s
In his sec ion we mainly in es iga e de e minis ic accep ing P sys ems wi h con-
ex condi ions and p io i ies on he ules (de e minis ic P sys ems o sho ) using
only non-coope a i e ules and wo king in he sequen ial, he asynch onous, and
he maximally pa allel mode.
Rema k 4. We fi s no ice ha maximal pa allelism in sys ems wi h non-
coope a i e ules means he o al pa allelism o all symbols o which a leas
one ule is applicable, and de e minism gua an ees ha “a leas one” is “exac ly
one” o all eachable configu a ions and objec s. De e minism in he sequen ial
mode equi es ha a mos one symbol has an associa ed applicable ule o all
eachable configu a ions. Su p isingly enough, in he case o he asynch onous
mode we ace an e en wo se si ua ion han in he case o maximal pa allelism – i
mo e han one copy o a specific symbol is p esen in he configu a ion, hen no
ule can be applicable o such a symbol in o de no o iola e he condi ion o
de e minism.
We now define he bounding ope a ion o e mul ise s, wi h a pa ame e k∈N
as ollows:
o u∈O∗,bk(u) = wi h | |a= min(|u|a, k) o all a∈O.
A Cha ac e iza ion o N F IN ∪coN F IN 31
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. Con ex condi ions a e equi alen o p edica es de ined on boundings.
P oo . We s a by ep esen ing con ex condi ions by p edica es on boundings.
Conside a ule wi h a simple con ex condi ion ( , p, Q), and le he cu en con-
figu a ion be C. Then, i suffices o ake k≥max (|p|,max{|q| | q∈Q}), and
le C′=bk(C). The applicabili y condi ion o ( , p, Q) may be exp essed as
p⊆C′∧(∧q∈Qq⊆ C′). Indeed, x⊆C←→ x⊆C′ o e e y mul ise xwi h
|x| ≤ k, because o e e y a∈O,|x|a≤ |C|a←→ |x|a≤min (|C|a, k) holds i
|x|a≤k. Finally, we no ice ha con ex condi ions which a e no simple can be
ep esen ed by a disjunc ion o he co esponding p edica es.
Con e sely, we show ha any p edica e E⊆ {0,· · · , k}O o he bounding
mapping bk o ule can be ep esen ed by some con ex condi ions. Fo each
mul ise c∈E, we cons uc a simple con ex condi ion o he effec o “con ains
c, bu , o each acon ained in c o less han k imes, no mo e han |c|asymbols
a”: {( , c, {a|c|a+1 | |c|a< k}) |c∈E}.
Joining mul iple simple con ex condi ions o e he same ule in o one ule wi h
con ex condi ions concludes he p oo . 
The ollowing heo em is alid e en when he ules a e no es ic ed o non-
coope a i e ones, and when de e minism is no equi ed, in ei he de i a ion mode
(also see [3]).
Theo em 1. P io i ies a e subsumed by condi ional con ex s.
P oo . A ule is p ohibi ed om being applicable due o a p io i y ela ion i and
only i a leas one o he ules wi h highe p io i y migh be applied. Le be a
ule o a P sys em (O, Σ, w, R′, R, >), and le 1> , · · · , n> . Hence, he ule
is no blocked by he ules 1,· · · , ni and only i he le -hand sides o he ules
1,· · · , n,lhs ( 1),· · · , lhs ( n) a e no p esen in he cu en configu a ion o he
con ex condi ions gi en in hese ules a e no ulfilled. Acco ding o Lemma 1,
hese con ex condi ions can be o mula ed as p edica es on he bounding bkwhe e
kis he maximum o weigh s o all le -hand sides, p omo e s, and inhibi o s in he
ules wi h highe p io i y 1,· · · , n. Toge he wi h he con ex condi ions om
i sel , we finally ge con ex condi ions o a new ule ′simula ing , bu also in-
co po a ing he condi ions o he p io i y ela ion. Pe o ming his ans o ma ion
o all ules concludes he p oo . 
32 A. Alhazo , R. F eund
Rema k 5. F om [3] we al eady know ha in he case o ules wi hou con ex con-
di ions, he con ex condi ions in he new ules a e only se s o a omic inhibi o s,
which also ollows om he cons uc ion gi en abo e. A ca e ul in es iga ion o
he cons uc ion gi en in he p oo o Theo em 1 e eals he ac ha he maximal
weigh s o he p omo e s and inhibi o s o be used in he new sys em a e bounded
by he numbe kin he bounding bk.
3.1 Sequen ial Sys ems
Al hough h oughou he es o he pape we a e no dealing wi h sequen ial
sys ems anymo e, he p oo o he ollowing heo em gi es us some in ui ion why,
o de e minis ic non-coope a i e sys ems, he e a e se e e diffe ences be ween he
sequen ial mode and he asynch onous o he maximally pa allel mode.
Theo em 2. Nde aOP sequ
1(ncoo, p o1,1, inh1,1) = NRE.
P oo . Conside an a bi a y de e minis ic egis e machine M= (m, B, l0, lh, P).
We simula e Mby a de e minis ic P sys em Π= (O, {a1}, l0, R) whe e
O={aj|1≤j≤m}∪{l, l1, l2|l∈B},
R={l→ajl′|(l:ADD(j), l′)∈P}
∪ {l→l1|aj, aj→a′
j|l1,¬a′
j, l1→l2|a′
j, a′
j→λ|l2, l1→l′|¬a′
j,
l→l′′|¬aj|(l:SUB(j), l′, l′′)∈P}.
We claim ha Πis de e minis ic and non-coope a i e, and i accep s he same se
as M.
As can be seen in he cons uc ion o he de e minis ic P sys em in he p oo
abo e, he ule aj→a′
j|l1,¬a′
jused in he sequen ial mode can be applied ex-
ac ly once, p iming exac ly one symbol aj o be dele ed a e wa ds. In ui i ely, in
he asynch onous o he maximally pa allel mode, i is impossible o choose only
one symbol ou o an unbounded numbe o copies o be dele ed. The bounding
ope a ion defined abo e will allow us o pu his in ui ion in o a o mal p oo .
3.2 Asynch onous and Maximally Pa allel Sys ems
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 p oceed by showing ha bounding induces equi alence classes p ese ed by
any compu a ion.
Lemma 2. Assume u⇒xand ⇒y. Then bk(u) = bk( )implies bk(x) =
bk(y).
A Cha ac e iza ion o N F IN ∪coN F IN 33
P oo . Equali y bk(u) = bk( ) means ha o e e y symbol a∈O, i |u|a=| a|
hen |u|a≥kand | |a≥k, and we ha e a ew cases o be conside ed. I no
ule is applicable o a, hen he inequali y o symbols awill be indis inguishable
a e bounding also in he nex s ep (bo h wi h a leas kcopies o a). O he wise,
exac ly one ule is applicable o a(by de e minism, and bounding does no affec
applicabili y), hen he diffe ence o he mul iplici ies o he symbol amay only
lead o diffe ences o he mul iplici ies o symbols b o all b∈ hs ( ). Howe e ,
ei he all copies o aa e e ased by he ule a→λo else a leas one copy o a
symbol bwill be gene a ed om each copy o aby his ule alone, so |x|b≥ |u|a≥k
and |y|b≥ | |a≥k, so all diffe ences o mul iplici ies o an objec bin uand will
be indis inguishable a e bounding in his case, oo. 
Co olla y 1. I bk(u) = bk( ), hen uis accep ed i and only i is accep ed.
P oo . Le wbe he fixed pa o he ini ial configu a ion. Then we conside com-
pu a ions om uw and om w. Clea ly, bk(uw) = bk( w). Equali y o boundings
is p ese ed by one compu a ion s ep, and hence, by any numbe o compu a ion
s eps.
Assume he con a y o he claim: one o he compu a ions hal s a e ss eps,
while he o he one does no , i.e., le uw ⇒su′and w ⇒s ′. By he p e ious
pa ag aph, bk(u′) = bk( ′). Since bounding does no affec applicabili y o ules,
ei he bo h u′and ′a e hal ing, o none o hem. The con adic ion p o es he
claim. 
We should like o no ice ha he a gumen s in he p oo s o Lemma 2 and
Co olla y 1 a e gi en o he maximal pa allel mode; ollowing he obse a ion
s a ed a he end o Rema k 4, hese wo esul s can also be a gued o he asyn-
ch onous mode.
Theo em 3. Fo de e minis ic P sys ems wo king in he asynch onous o in he
maximally pa allel mode, we ha e he ollowing cha ac e iza ion:
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).
P oo . Each equi alence class induced by bounding is comple ely accep ed o com-
ple 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|). This p o es he “a mos NFIN ∪coNFIN” pa .
In Examples 1 and 2 we ha e al eady shown ha
Nde aOPα
1(ncoo, p o1,∗, inh1,∗)⊇FIN ∪coNF IN