Self-constructing Recognizer P Systems

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 .