Sel -cons uc ing Recognize P Sys ems
Daniel D´ıaz-Pe nil1, F ancisco Pe˜na-Can illana2,
Miguel A. Gu i´e ez-Na anjo2
1Resea ch G oup on Compu a ional Topology and Applied Ma hema ics
Depa men o Applied Ma hema ics - Uni e si y o Se illa, 41012, Spain
[email p o ec ed]
2Resea ch G oup on Na u al Compu ing
Depa men o Compu e Science and A ificial In elligence
Uni e si y o Se illa, 41012, Spain
[email p o ec ed], [email p o ec ed]
Summa y. Usually, he changes p oduced in he memb ane s uc u e o a P sys em a e
conside ed side effec s. The ou pu o he compu a ion is encoded as a mul ise placed in a
specific egion and he memb ane s uc u e in he hal ing configu a ion is no conside ed
impo an . In his pape we explo e P sys ems whe e he a ge o he compu a ion is he
cons uc ion o a new memb ane s uc u e acco ding i s se o ules. The new memb ane
s uc u e can be conside ed as he ini ial one o a new sel -cons uc ed P sys em. We
ocus on he sel -cons uc ion o ecognize P sys ems and illus a es he defini ion wi h
a s udy o he sel -cons uc ion P sys ems wo king as decision ees o sol ing Machine
Lea ning decision p oblems.
1 In oduc ion
In many Memb ane Compu ing models, changing he memb ane s uc u e o a P
sys em along he compu a ion is a common p ocess. The changes a e p oduced ia
di ision o memb anes (based on cellula mi osis), ia c ea ion o new memb anes
om objec s (based on cellula au opoiesis, see [7]) o dissolu ion o memb anes.
The ules p oducing such changes ha e been deeply s udied and he capabili y o
he P sys ems o sol ing ha d p oblems a e linked o he use o such ules (see,
e.g., [4, 5, 16]).
None heless, he changes o he memb ane s uc u e p oduced along a compu-
a ion a e no conside ed a a ge i sel . The changes a e usually p oduced in o de
o compu e an ou pu , which is usually encoded as a mul ise (o as a single dis-
inguished objec ) in he co esponding ou pu egion. The memb ane s uc u e
ob ained in he hal ing configu a ion is no impo an . I is me ely a colla e al
effec .
In his pape , we ocus on P sys ems whe e he a ge o he compu a ion
is exac ly he opposi e o he usual one. We s udy P sys ems whose aim is o
138 D´ıaz-Pe nil e al.
de elop a memb ane s uc u e. Such P sys ems will ake a mul ise as inpu and
hey will change hei memb ane s uc u e acco ding o such inpu , he se o
ules and he non-de e minis ic choices, i any. The memb ane s uc u e ob ained
in he hal ing configu a ion will be conside ed as he ou pu o he compu a ion.
This new memb ane s uc u e, oge he he emaining ing edien s o he P sys em
(alphabe , se o labels, se o ules, . . . ) can be conside ed as a new P sys em,
able o ecei e a new inpu and pe o m a new compu a ion. In his way, we will
conside ha his second P sys em (which is simila o he o iginal one, bu wi h
a new ini ial memb ane s uc u e) has been sel -cons uc ed, since a (po en ially)
complex memb ane s uc u e has been ob ained om a simple one (maybe om
an ini ial memb ane s uc u e wi h he skin as unique memb ane) acco ding o
he applica ion o hei own ules. O cou se, diffe en final memb ane s uc u es
may be ob ained om diffe en inpu s, bu also wi h he same inpu due o he
non-de e minism.
The sel -cons uc ion o a complex memb ane s uc u e can be a a ge by i sel ,
as shown in [3, 6], bu in his pape , he sel -cons uc ed P sys em is hough o
a second use. F om his gene al a ge , we ocus he e on he sel -cons uc ion o
ecognize P sys ems, i.e., he P sys em wi h his new memb ane s uc u e can
be now used as ecognize P sys ems o sol ing decision p oblems in he usual
way: An ins ance o he decision p oblem is p o ided o he P sys em as an inpu
encoded as an app op ia e mul ise and an objec yes o no (bu no bo h) is sen
o he en i onmen in he las s ep o he compu a ion.
In his way, wo diffe en uses o he P sys em a e conside ed:
•Fi s ly, gi en a P sys em, a mul ise is placed in he co esponding inpu mem-
b ane and he compu a ion s a s. Acco ding o he inpu and he non de e -
minis ic choice o applicable ules, he ini ial memb ane s uc u e is modified
along he compu a ion. As usual, a hal ing configu a ion is eached i no mo e
ules can be applied. The sel -cons uc ion o he ecognize P sys em is fin-
ished.
•Secondly, we conside a new compu a ion o he P sys em, bu in his s age,
he memb ane s uc u e ob ained in he hal ing configu a ion o he p e ious
s age is conside ed as he ini ial one. This new compu a ion also needs a new
inpu , which is placed in he co esponding inpu memb ane. In his s age, he
ou pu will be a specific objec (yes o no, bu no bo h) which is placed in he
ou pu egion in he hal ing configu a ion.
The pape is o ganized as ollows: Nex , we ecall he defini ion o ecognize
P sys em used in his pape . In Sec ion 3, ou case s udy is p esen ed, he sel -
cons uc ion o a P sys em om a aining se which wo ks as a decision ee and
he classifica ion (decision p oblem) o new ins ances as in Machine Lea ning he-
o y. We p o ide he o mal amewo k, he gene al cons uc ion o he P sys ems,
an example and some heo e ical conside a ions. Finally, Sec ion 4 finishes he
pape wi h some conclusions.
Sel -cons uc ing Recognize P Sys ems 139
2 Recognize P Sys ems
Recognize P sys ems we e in oduced in [11] and hey a e he na u al amewo k
o s udy and sol e decision p oblems, i.e., p oblems we e a Boolean o al unc ion
θXmus be defined on a se o ins ances IX. Recognize P sys ems a e associa ed
in a na u al way wi h P sys ems wi h inpu and wi h ex e nal ou pu , i.e., each
ins ance o he p oblem is codified by a mul ise placed in an inpu memb ane. The
ou pu o he compu a ion (yes o no) is sen o he en i onmen . Due o he non-
de e minism, he defini ion o ecognize P sys em claims ha he ou pu o all he
compu a ions mus be he same. Since one can find sligh ly diffe en app oaches
in he li e a u e (see [9, 15]), we ecall he defini ion used in his pape :
De ini ion 1. AP sys em wi h inpu is a uple (Π, Σ, iΠ), whe e: (a) Πis a
P sys em, wi h wo king alphabe Γ, wi h pmemb anes labelled by 1, . . . , p, and
ini ial mul ise s w1, . . . , wpassocia ed wi h hem; (b) Σis an (inpu ) alphabe
s ic ly con ained in Γ; he ini ial mul ise s a e o e Γ−Σ; and (c) iΠis he label
o a dis inguished (inpu ) memb ane.
Le mbe a mul ise o e Σ. The ini ial con igu a ion o (Π, Σ, iΠ)wi h inpu m
is (µ, w1, . . . , wiΠ∪m, . . . wp).
De ini ion 2. A ecognize P sys em is a P sys em wi h inpu , (Π, Σ, iΠ), and
wi h ex e nal ou pu such ha :
1. The wo king alphabe con ains wo dis inguished elemen s yes,no.
2. All i s compu a ions hal .
3. I Cis a compu a ion o Π, hen ei he some objec yes o some objec no (bu
no bo h) mus ha e been eleased in o he en i onmen , and only in he las
s ep o he compu a ion. We say ha Cis an accep ing compu a ion ( espec-
i ely, ejec ing compu a ion) i he objec yes ( espec i ely, no) appea s in he
ex e nal en i onmen associa ed o he co esponding hal ing con igu a ion o
C.
3 A Case S udy: Decision T ees
Decision ees is one o he mos widely used s uc u es in Compu e Science. They
a e used o classi y an inpu by so ing i down he ee om he oo o some
lea node, which p o ides he classifica ion o he ins ance. Ins ances a e usually
w i en as se s o pai s ⟨A ibu e, V alue⟩and each node in he ee de e mines a
es o some a ibu e. Each b anch descending om ha node co esponds o one
o he possible alue o his a ibu e. An ins ance is classified by s a ing a he
oo node o he ee, es ing he a ibu e specified in his node and mo ing down
he b anch co esponding o he alue o he ins ance in his a ibu e. The lea es
a e labelled wi h alues o he classifica ion and hey a e he ou pu associa ed
o he ins ances ha each hem. In his way, i he possible classifica ions a e
140 D´ıaz-Pe nil e al.
Table 1. A classic example o aining se adap ed om [14].
Day Ou look Tempe a u e Humidi y Wind PlayTennis
D1 Sunny Ho High Weak No
D2 Sunny Ho High S ong No
D3 O e cas Ho High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool No mal Weak Yes
D6 Rain Cool No mal S ong No
D7 O e cas Cool No mal S ong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool No mal Weak Yes
D10 Rain Mild No mal Weak Yes
D11 Sunny Mild No mal S ong Yes
D12 O e cas Mild High S ong Yes
D13 O e cas Ho No mal Weak Yes
D14 Rain Mild High S ong No
Y ES and NO, a decision ee can be hough as a Boolean mapping on he se o
ins ances which decides he classifica ion o he ins ance acco ding o he alues
o he a ibu es.
Le us illus a e he p ocess wi h a classic example adap ed om [14]. I consis s
on a da abase wi h ou een days. Each day is ep esen ed by he alues o he
a ibu es Ou look,Tempe a u e,Humidi y and Wind. Each day has also associa ed
i s classifica ion wi h espec o he a ibu e PlayTennis (see Table 1). F om a
lea ning poin o iew, he da abase can be seen as a aining se . The a ge is
o gene a e a decision ee om his da abase which can be used o classi y new
ins ances.
Figu e 1 shows a decision ee consis en wi h he aining se shown in Table 1,
i.e., a ee which classifies co ec ly all he examples in he aining se . Acco ding
o his ee, a day wi h Ou look =Sunny,T empe a u e =Cool,Humidi y =
No mal and W ind =S ong (which does no belong o he aining se ) will be
classified as Y ES.
3.1 The P Sys em Model
The defini ion o sel -cons uc ion in P sys em is independen o he P sys em
model, i.e., i can be conside ed in he amewo k o cell-like, issue-like o wha -
e e o he g aph s uc u e and i can be adap ed o diffe en seman ics. The unique
es ic ion ha he P sys em mus sa is y is he abili y o modi ying he ini ial
memb ane s uc u e acco ding o he inpu . In his way, he concep can be con-
side ed in many scena ios.
In his pape , we will illus a e he defini ion wi h a P sys em model we e he
da a a e encoded as s ings [1, 13] and he changes in he memb ane s uc u e a e
pe o med ia memb ane c ea ion [5, 10].
Sel -cons uc ing Recognize P Sys ems 141
Ou look
O e cas
Humidi y
No malHigh
No Yes
Wind
S ong Weak
No Yes
Yes
Rain
Sunny
Fig. 1. An example o ee ob ained om he aining se shown in 1. The image is a ail-
able om h p://www.cs.cmu.edu/a s/cs.cmu.edu/use /mi chell/ p/mlbook.h ml.
Fo mally, a sel -cons uc ing P sys em wi h s ings and memb ane c ea ion is
a cons uc o he o m Π= (O, H, L, R) whe e:
1. Ois he alphabe o objec s;
2. His a fini e se o labels;
3. Lis a fini e languages o e O;
4. Ris a fini e se o ules, o he ollowing o ms:
a) [wp+wq→∑kwk]hwhe e h∈H,wp,wqand wka e s ings o e O.
These a e 2-coope a i e e olu ion ules: The simul aneous occu ence o
he s ings wpand wqin he memb ane hp oduces a fini e se o s ings
in he same memb ane. As usual, wpand wqa e consumed.
b) wp[ ]h→[wq]hwhe e h∈H;wpand wqa e s ings o e O. These a e send-
in communica ion ules. A s ing is in oduced in he memb ane possibly
modified.
c) [wp]h→[ ]hwqwhe e h∈H;wpand wqa e s ings o e O. These a e send-
ou communica ion ules. A s ing is sen ou o he memb ane possibly
modified.
d) [a→[M]h2]h1whe e h1, h2∈H,a∈Oand Mis a fini e language o e O.
These a e c ea ion ules. An objec aplaced in a memb ane wi h label h1
c ea es a new memb ane wi h label h2. This new memb ane has associa ed
an ini ial fini e language M.
We will conside ha he sel -cons uc ing P sys em wi h s ings and mem-
b ane c ea ion always has a unique memb ane ( he skin) in he ini ial memb ane
s uc u e, such memb ane is he inpu memb ane and he ou pu egion is he en-
i onmen . The mul ise Lis placed in he skin a he ini ial configu a ion. Rules
a e applied acco ding o he ollowing p inciples:
•Rules a e used as usual in he amewo k o Memb ane Compu ing, ha is, in a
maximal pa allel way. In one s ep, each s ing in a memb ane can only be used

142 D´ıaz-Pe nil e al.
o one ule (non de e minis ically chosen when he e a e se e al possibili ies),
bu any s ing which can e ol e by a ule o any o m mus do i (wi h he
es ic ions below indica ed).
•All he s ings which a e no in ol ed in any o he ope a ions o be applied
emain unchanged.
•The ules associa ed wi h he label ha e used o all memb anes wi h his
label, i espec i e o whe he o no he memb ane is an ini ial one o i was
ob ained by c ea ion.
•Se e al ules can be applied o diffe en objec s in he same memb ane simul-
aneously.
3.2 Sel -cons uc ing P Sys ems o Decision T ees Lea ning
Nex , we will p o ide a amily o sel -cons uc ing P sys em wi h s ings and mem-
b ane c ea ion o Decision T ees Lea ning. Such sel -cons uc ed P sys em will
ecei e ins ances o he p oblem and will ou pu yes o no, i.e., hey a e ools o
sol ing decision p oblems.
In a fi s s age, he P sys em akes a fini e language, codi ying a aining se ,
as inpu . Each example in he aining se will be encoded as a s ing. The se
o hese s ings will be he ini ial language Land i will be placed in he unique
ini ial memb ane o he P sys em, as defined abo e. A e a fini e numbe o s eps,
he compu a ion hal s and he memb ane s uc u e has been (p obably) modified.
The P sys em wi h his hal ing memb ane s uc u e is he ecognize P sys em
which has been sel -cons uc ed acco ding wi h he aining se p o ided as inpu .
The sel -cons uc ed ecognize P sys em wi h he memb ane s uc u e ob ained
in he hal ing configu a ion is now p epa ed o ecei e an ins ance o he decision
p oblem and will p o ide an answe yes o no .
Le us s a by conside ing a aining se D={( 1, c1), . . . , ( n, cn)}whe e, o
each i∈ {1, . . . , n}, iis a uple o pai s ⟨A ibu e, V alue⟩and ci={Y ES, NO}
is he classifica ion o a concep 1. We will conside a se o a ibu es ATR =
{A1, . . . , Ak}and, o each i∈ {1, . . . , k},V ALi={ 1
i, . . . , ji
i}is he se o alues
o he a ibu e Ai. We will conside ha he se s V ALia e disjoin pai wise.
We will also conside V AL =V AL1∪... ∪V ALkand Γ=AT R ∪V AL ∪
{Y ES, NO}. The se Γwill be called a aining se alphabe . No ice ha many
diffe en aining se s can ha e he same alphabe Γ.
By using his no a ion, we will ep esen each example ( i, ci) as a s ing
o e he se Γand a aining se can be conside ed as a fini e language o e
his se . The example ( i, ci) will be ep esen ed by he s ing o 2k+ 1 symbols
A1 i
1A2 i
2. . . Ak i
kci, whe e i
jis he alue o he a ibu e Ajin he i− h exam-
ple o he aining se and ci∈ {Y ES, NO}is he alue o he classifica ion. Fo
example, he s ing
1A o mal desc ip ion o he p inciples o Machine Lea ning is ou o he scope o his
pape . A de ailed in oduc ion can be ound in, e.g., [8].
Sel -cons uc ing Recognize P Sys ems 143
Ou look Sunny Tempe a u e Ho Humidi y High Wind Weak NO
is he ep esen a ion o he fi s example o Table 1.
In he fi s s age, he fini e language codi ying he aining se is placed in
he skin and he sel -cons uc ion s a s. When i finishes, he hal ing memb ane
s uc u e is p epa ed o accep ing new inpu s and deciding on i . The new inpu
will be simila o he encoding o an example, bu he las objec o he s ing will
be ? ins ead o Y ES o NO. Fo example, in o de o know he classifica ion o a
day no wi h Ou look =Sunny,T empe a u e =Cool,Humidi y =No mal and
Wind =S ong, he s ing
Ou look Sunny T empe a u e Cool Humidi y No mal Wind S ong ?
will be placed in he inpu memb ane ( he skin) and a new compu a ion will s a .
Nex we p o ide he o mal defini ion o a sel -cons uc ing P sys em wi h
s ings and memb ane c ea ion associa ed o a aining se Γ. The P sys em is a
4-uple Π= (O, H, L, R) whe e:
1. O=Γ∪ {Y ESaux, Y ESac ,?, NOaux, NOac , new}is he alphabe o ob-
jec s;
2. H={skin} ∪ V AL. The possible labels a e he alues o he a ibu es plus
he ini ial label skin;
3. L={Y ESaux, NOaux}Two s ings, each o hem wi h only one objec , a e
placed in he skin in he ini ial configu a ion;
4. We spli he se Ro ules in o wo g oups, he ules used in he sel -
cons uc ion s age and he ules used in he decision s age:
Rules o he sel -cons uc ion s age.
R1.[xY ES +Y ESaux →xY ES +Y ESac ]h
[xNO +NOaux →xNO +NOac ]h} o h∈H.
whe e xis a s ing o e Γcomposed by pai s (A ibu e, V alue). I he s ing
xY ES and Y ESaux occu simul aneously in he same memb ane, hen xY ES
emains unchanged, bu Y ESaux is consumed and Y ESac is p oduced.
Analogously o he NO case.
R2.[Y ESac +NOac →new]h o h∈H.
I he s ings Y ESac and NOac a e placed simul aneously in he same
memb ane, bo h a e consumed and he s ing new is p oduced.
R3.[new +xAiy→xAiy+ 1+. . . + s]h o h∈H.
I he s ings new and xAiyoccu in he same memb ane (whe e xAiyis a
s ing including he objec Ai, which deno es an a ibu e), hen he s ing
new is consumed, he s ing xAiy emains unchanged and all he s ings i
j
om V ALia e p oduced. Le us no ice ha his se o ules p oduces a high
144 D´ıaz-Pe nil e al.
deg ee o non-de e minism. On he one hand, many diffe en s ings xAiycan
simul aneously occu in he same memb ane and, on he o he hand, se e al
Aimay be chosen om he same s ing. None heless, since he e can exis s a
mos only one s ing new in each memb ane a each ime uni , only one o
hese ules will be applied.
R4.[ →[Y ESaux NOaux] ]h o h∈H
Each s ing ∈V AL c ea es a new memb ane. Such memb ane will ha e
as a label and i will con ain he s ings Y ESaux and NOaux.
R5. xAi y [ ] →[xy ] o Ai∈AT R and ∈V ALi
Each s ing xAi y (whe e Aiis an objec which deno es an a ibu e and
is he nex symbol in he s ing, deno ing one o he alues o Ai) ou o a
memb ane wi h label will be sen in o he memb ane. The applica ion o
he ule will ans o m he s ing in o xy, which is xAi y a e dele ing he
subs ing Ai . These ules a e applied in pa allel and se e al s ings can c oss
ou he same memb ane simul aneously.
Rules o he decision s age.
R6. xA y? [ ] →[xy? ] o ∈V AL.
I a s ing ended wi h ? and con aining an objec ∈V AL is ou o a
memb ane wi h label , hen he s ing is sen in o he memb ane. The
applica ion o he ule also p oduces a change in he s ing since he objec
and he p e ious objec in he s ing ( he objec Adeno ing he co esponding
a ibu e) a e dele ed.
R7.[x? + Y ESac →Y ESou +Y ESac ]h
[x? + NOac →NOou +NOac ]h} o h∈H.
whe e xis a s ing o e Γcomposed by pai s (A ibu e, V alue). I he s ing
x? and Y ESac occu simul aneously in he same memb ane, hen Y ESac
emains unchanged, bu x? is consumed and Y ESou is p oduced. Analogously
o he NO case.
R8.[Y ESou ]h→[ ]hY ESou
[NOou ]h→[ ]hNOou } o h∈H.
when an objec Y ESou ( esp. NOou ) is p oduced, he decision is made. This
se o ules sends such objec om he memb ane whe e is p oduced o he
en i onmen . Such objec s a e he answe s o he decision p oblem
Sel -cons uc ing Recognize P Sys ems 145
Ou look sunny T empe a u e ho Humidi y high W ind weak NO
Ou look sunny T empe a u e ho Humidi y high W ind s ong NO
Ou look o e cas T empe a u e ho Humidi y high W ind weak Y ES
Ou look ain T empe a u e mild Humidi y high W ind weak Y ES
Ou look ain T empe a u e cool Humidi y no mal W ind weak Y ES
Ou look ain T empe a u e cool Humidi y no mal W ind s ong NO
Ou look o e cas T empe a u e cool Humidi y no mal W ind s ong Y ES
Ou look sunny T empe a u e mild Humidi y high W ind weak NO
Ou look sunny T empe a u e cool Humidi y no mal W ind weak Y ES
Ou look ain T empe a u e mild Humidi y no mal W ind weak Y ES
Ou look sunny T empe a u e mild Humidi y no mal W ind s ong Y ES
Ou look o e cas T empe a u e mild Humidi y high W ind s ong Y ES
Ou look o e cas T empe a u e ho Humidi y no mal W ind weak Y ES
Ou look ain T empe a u e mild Humidi y high W ind s ong NO
Fig. 2. Fini e language encoding he aining se om Table 1.
3.3 An example
As an example o sel -cons uc ion P sys ems o Decision T ee Lea ning, le us
conside he aining se om Table 1. Acco ding o he encoding p e iously de-
sc ibed, such aining se can be w i en as shown in Fig. 2.
Le us conside an ini ial configu a ion C0which has only one memb ane wi h
label skin. Such memb ane con ains he language codi ying he aining se om
Fig. 2, oge he wi h Y ESaux and NOaux. F om his ini ial configu a ion only wo
ules om R1 a e applied. The applica ion o such ules consumes Y ESaux and
NOaux and p oduces Y ESac and NOac . In he second s ep o he compu a ion,
only he ule om R2 is applied. The objec s Y ESac and NOac a e consumed and
new appea s in he skin. In his way, he configu a ion C2has only one memb ane,
he skin, whe e he codifica ion o he aining se and he objec new a e placed.
F om his configu a ion C2, one and only one o he ules om R3 is non-
de e minis ically chosen and applied. In he choice, one o he s ings encoding
an example om he aining se is aken and in his s ing, one o he objec s
encoding an a ibu e is also selec ed. Le us suppose ha he s ing
Ou look sunny T empe a u e ho Humidi y high Wind weak NO
is chosen and he objec Ou look is selec ed. The applica ion o he ule consumes
he objec new, keeps unchanged he s ing encoding he example and h ee new
objec s ain,sunny and o e cas appea . The e o e, he configu a ion C3has only
one memb ane, he skin, whe e he codifica ion o he aining se and he objec s
ain,sunny and o e cas a e placed.
In he nex s ep, he changes in he memb ane s uc u e s a . The objec s
ain,sunny and o e cas c ea e new memb anes. Each memb ane has he objec s
Y ESaux and NOaux inside and he co esponding alue ain,sunny o o e cas
as label, i.e.,
152 D´ıaz-Pe nil e al.
Lemma 1. Le us conside an elemen a y memb ane a he s ep nsuch ha he e
a e no s ings in i s a he memb ane (i can also be he skin in he ini ial con igu-
a ion) and i s con en is Y ESaux,NOaux, and a non-emp y se o examples such
ha all o hem end wi h Y ES o all o hem end wi h NO. Then, he compu a ion
in his memb ane inishes a s ep n+ 1.
P oo . Le us conside ha all he examples end wi h Y ES ( he case NO is
analogous). In he desc ibed condi ions, only one ule can be applied ( om R1)
and in he s ep n+ 1, he memb ane con ains he same se o examples and
Y ESac and NOaux. I is easy o check ha no mo e ules can be applied and he
compu a ion finishes a his s ep.
F om his lemma, we ob ain ha i all he examples in he ini ial se p o ided o
he skin in he ini ial configu a ion end wi h Y ES o NO, hen he compu a ion
o he sel -cons uc ing s age end a e one compu a ion s ep.
Lemma 2. All he examples inside a memb ane ha e he same leng h.
P oo . I is i ial o check ha i is ue in he ini ial configu a ion, since i he
aining se has ka ibu es, hen, all he ini ial examples ha e leng h 2k+ 1. Fo
he nex s eps, we only need o conside ha he ules which sends examples om
one memb ane in o o he belongs ho he se R5, he applica ion o hese ules
always dec eases he leng h o he example in wo uni s and all he examples a i e
o he memb ane simul aneously.
Lemma 3. Le us conside an ini ial aining se wi hou noise. I in a memb ane
he e is a leas one example o leng h 1, hen all o hem a e Y ES o all o hem
a e NO.
P oo . By, Lemma 2, we can conside ha all he examples in he memb ane ha e
leng h 1. I he aining se has ka ibu es, hen all he examples in he ini ial
configu a ion ha e leng h 2k+ 1 and, by cons uc ion, hese examples o leng h 1
came om hese o iginal one a e dele ing wo objec s k imes. In his p ocess, i
wo examples a e sen o he same memb ane, hen bo h sha e he same alue o
one a ibu e. I bo h examples a e in he same memb ane a e kdele ions, hen
hey sha e he alues o he ka ibu es and, since hei no noise, he classifica ion
mus be he same.
Lemma 4. Le us conside an elemen a y memb ane ha he s ep nsuch ha
he e a e no s ings in i s a he memb ane (i can also be he skin in he ini ial
con igu a ion) and i s con en is Y ESaux,NOaux, and a non-emp y se o examples
o leng h lsuch ha a leas one o hem ends wi h Y ES and a leas one o hem
ends wi h NO. Then, a s ep n+ 5, he memb ane hdoes no con ains s ings.
I only con ains elemen a y memb anes such ha con ain Y ESaux,NOaux and
examples o leng h l−2.

Sel -cons uc ing Recognize P Sys ems 153
P oo . In he desc ibed condi ions, a he s ep n+ 1 he memb ane con ains he
se o examples plus Y ESac and NOac (by R1); a he s ep n+ 2, i con ains
he se o examples and new (by R2); a n+ 3, i con ains he se o examples
plus 1,. . . , s, whe e 1,. . . , sa e he alues o one o he a ibu es (by R3).
By applica ion o ules om R4, a he s ep n+ 4, he memb ane con ains he
se o examples plus selemen a y memb anes, one o each alue. Each o hese
memb anes con ains he s ings Y ESaux and NOaux. Finally, ules om R5 a e
applied and all he examples om he memb ane ha e sen in o he elemen a y
memb anes by dele ing wo objec s.
Finally, he S a emen 1, can be p o ed om hese lemmas.
P oo . P oo o he S a emen 1. I he aining se has ka ibu es, hen he
examples placed in he skin in he ini ial configu a ion ha e leng h 2k+ 1. Two
cases a e possible:
•I all o hem ha e he same classifica ion, i.e., all o hem end wi h Y ES o
all o hem end wi h NO, hen, by Lemma 1, he compu a ion finishes in he
configu a ion C1.
•I all o hem do no ha e he same classifica ion, hen he condi ions o Lemma
2 hold and he configu a ion C5has elemen a y memb anes wi h Y ESaux,
NOaux and examples o leng h 2(k−1) −1. Each o hese memb anes is in he
same condi ions ha he skin in he ini ial configu a ion, bu he leng h o he
examples has dec eased in wo uni s. This p ocess goes on and each elemen a y
memb ane s ops a e 1 + 5ps eps wi h p∈ {0, . . . , k}. Lemma 3 is conside ed
o ensu e ha all he examples in he elemen a y memb ane end in Y ES o
NO and hen, he compu a ion hal s as shown in Lemma 1.
Nex , we will p o e he second s a emen o he heo em. Now he P sys em
has been sel -cons uc ed. Only elemen a y memb anes ha e s ings. As shown in
Lemma 1, in he hal ing configu a ion, hese memb ane ha e a se o examples and
he pai Y ESaux and NOac o Y ESac and NOaux, depending o he classifica ion
o he examples. Any compu a ion in he decision s age s a s by placing a s ing
x? as inpu in he skin, whe e is a s ing o pai s A ibu e Value. Since all he
examples in each memb ane ha e he same classifica ion and no mo e examples
a e supplied, hen he ules om se s R1 o R5 canno be applied. Only ules
om R6,R7 and R8 mus be conside ed. The s a emen is he ollowing
Any compu a ion in he decision s age gi es 2p+ 2 s eps wi h
p∈ {0, . . . , k}and sends o he en i onmen Y ESac o NOac
(bu no bo h) in he las s ep o compu a ion.
(C2)
P oo . Fi s o all, le us no ice ha ules om R6,R7 and R8 canno be applied
simul aneously, because he condi ions o applicabili y a e disjoin and only one
s ing x? is p o ided as inpu in he skin in each compu a ion. F om his obse -
a ion, ules om R7 a e fi s ly applied p imes wi h p∈ {0, . . . , k}. A e hese
ps eps, he elemen a y memb ane whe e Y ESac o NOac is placed and in he
154 D´ıaz-Pe nil e al.
s ep p+ 1, he objec Y ESac o NOac (bu no bo h) is p oduced. A e ps eps
mo e, in he s ep 2p+ 1, Y ESac o NOac a i es o he skin by applica ion o
ules om R8. In he ollowing s ep, 2p+ 2, he objec Y ESac o NOac is sen
ou o he en i onmen and he compu a ion hal s.
In he hi d s a emen , we conside he sel -cons uc ed P sys em and ake an
example om he aining se xC, wi h C∈ {Y ES, NO}and eplace Cby ?. The
s a emen claims ha i we p o ide x? o he P sys em in he decision s age, we
ob ain he same classifica ion ha he o iginal one. The s a emen is
The ecognize P sys em ob ained a he end o any compu a ion
o he sel -cons uc ing s age is consis en wi h he aining se . (C3)
P oo . In o de o fix ideas, le us conside ha he o iginal example was xY ES.
The o he case is analogous. By ules om R6,x? will be sen o an elemen a y
memb ane whe e all he examples ha e he same classifica ion. One o hese exam-
ples was o iginally he xY ES and Y ESac occu s in his elemen a y memb ane.
Then, by applica ion o one ule om R7 and la e wi h ules om R8, he objec
Y ESou is sen o he en i onmen .