Improving the determination of minimal hitting sets in model-based diagnosis using constraint databases

IMPROVING THE DETERMINATION OF MINIMAL HITTING SETS IN MODEL-BASED DIAGNOSIS USING CONSTRAINT DATABASES M. T. G´omez-L´opez, R. M. Gasca and C. del Valle ∗,1 ∗Escuela T´ecnica y Supe io de Ingenie ´ıa In o m´a ica de Se illa, Spain {may e, gasca, ca melo}@lsi.us.es Abs ac : In model-based diagnosis, minimal hi ing se s a e usually used o iden i y which componen s may ail in a sys em. This wo k p esen s a se o algo i hms o imp o e he de e mina ion o all Minimal Hi ing Se s. Ou p oposal uses he minimal conflic se s o ob ain, in an efficien way, he diagnosis o a sys em. The imp o emen consis s o h ee algo i hms which analyse only he ele an op ions. This p oposal builds an equi alen sys em in o de o ob ain all minimal hi ing se s depending on he loca ion o he senso s. A he same ime, all he in o ma ion o he p ocess is s o ed in a Cons ain Da abase, keeping he in o ma ion pe sis en and eco e able. Some empi ical esul s a e p esen ed in o de o show how he p oposal imp o es he p ocess in o de o ob ain all minimal hi ing se s.Copy igh Keywo ds: Model-based Diagnosis, Cons ain Da abases, minimal hi ing se s. 1. INTRODUCTION A lo o heo e ical and p ac ical p oblems can be pa ly educed o an ins ance o he minimal hi ing se p oblem, as in model-based diagnosis how i is explained in (Rei e , 1987). Model-based diagnosis allows he iden ifica ion o he pa s which may ail in a sys em using a model. The models a e based on he knowledge o he sys em o be diagnosed, and i can be ep esen ed by cons ain s associa ed o he componen s. Inpu s and ou pu s o componen s a e ep esen ed as a iables in he cons ain s, and hey can be obse able and non-obse able, depending on he alloca ion o he senso s. In unc ion o he alue o hese senso s, i is possible o know which 1This wo k has been unded by he Minis e io de Ciencia y Tecnolog´ıa o Spain (DPI2003-07146-C02-01) and he Eu opean Regional De elopmen Fund (ERDF/ FEDER). g oups o componen s a e ailing looking o he minimal hi ing se s. In his wo k, a new app oach is p oposed in o de o au oma e and o imp o e he de e mina ion o all minimal hi ing se s. The e a e a significan amoun o wo ks ha deals wi h minimal hi ing se s, bu mos o hem a e only in e es ed in finding single minimal hi ing se s and o special ypes o p oblems. Ou mo- i a ion is o find all minimal hi ing se s, single o mul iple. Ano he ad an age o ou echnique is he possibili y o s o e all he diagnosis p ocess in o ma ion using he ela ional calculus. One o ou p e ious wo ks (G´omez-L´opez e al., 2004) shows how o ob ain he possible minimal conflic se s in an efficien way. This pape s a s a his poin , and some algo i hms a e de eloped and implemen ed o ob ain he minimal diagnosis. In his pape , we p esen how some issues conce n- ing Cons ain Da abases (CDBs) can imp o e he efficiency in some s ages o he model-based diag- nosis. A no el me hodology is p esen ed in o de o p omo e he ad an ages o his echnology and i s usage in indus ial diagnosis p oblems. Mo eo e he ela ional model is no able o ep esen he scien ific and enginee ing da a. Fo his eason, we conside CDBs as a good ool o ou easoning p ocess. The e a e lo s o wo ks, as (Re esz, 2002) and (Kupe e al., 1998), ha u ilise CDBs, bu nei he o hem uses hem o diagnosis. CDBs pe mi o ea and s o e he con inuous in o ma ion, as he beha iou o a sys em. I allows he use o all he powe o ela ional da abases in model-based diagnosis. Ou pape has been o ganised as ollows: Sec- ion 2 p esen s o he ele an p oposals. Sec ion 3 e iews some defini ions in o de o in oduce he model-bases diagnosis. Sec ion 4 explains how i is possible o ake ad an age o CDBs in he de e mina ion o minimal hi ing se s. Sec ion 5 desc ibes he algo i hms o imp o e he diagno- sis, showing some empi ical esul s. Finally he conclusions a e p esen ed. 2. BACKGROUND Rei e (Rei e , 1987) p esen ed one o he fi s solu ions o he de e mina ion o minimal hi ing se s using he so-called HS- ees. The p oblem wi h comple e HS- ees is ha he size o he ee g ows exponen ially wi h he size o he collec ion o se s. Minimal hi ing se s can be efficien ly ob ained by a p uned HS- ee, bu he cons uc ion o p uned HS- ees is complex due o unnecessa y esul s a e gene a ed. The HS- ee was e ised by G eine (G eine e al., 1989) in o an HS-DAG using a g aph. Among he solu ions ha use ees, i is possible o find he BHS- ees ha compu e he hi ing se s wi h a bina y- ee, o he Wo awa’s p oposal (Wo awa, 2001), whe e he HST- ee algo i hm is p esen ed. The HST- ee algo i hm cons uc s he ee in a unique way, whe e nodes a e o de ed om le o igh depending on he size o hei edge labels. O he p e ious wo ks ha e been cen e ed in ci - cui s diagnosis, as (Hou, 1994) o (S ump ne and Wo awa, 1997). (Hou, 1994) shows how o a oid isi ing all subse s. The p oblem was ha his p oposal skips o e some possible solu ions, and i was co ec ed in (Han and Lee, 1999), whe e he numbe o subse s equi ed o be explo ed was also educed. The algo i hm called s uc u ed-based abduc ion (SAB) o (Fa ah and Dech e , 1995) is imp o ed in (S ump ne and Wo awa, 1997), descending in o he ee o find he possible com- bina ions which can be esponsible o an inco ec beha iou . The de e mina ion o minimal hi ing se s has also been app oached wi hou using ees. (de la Banda e al., 2003) p esen s algo i hms o he de e mina ion o all he minimal unsa isfiable sub- se o cons ain s. They use p ep ocessing s eps o educe he size o he se o cons ain s, allowing hem o sol e la ge p oblems han o he ech- niques. 3. DEFINITIONS In o de o ob ain he minimal hi ing se s, some defini ions a e necessa y: Defini ion 1. Con ex Se (CS): Any subse o componen s which compose he sys em. The e a e 2ncomp −1 possible CSs, whe e ncomp is he numbe o componen s o he sys em. Defini ion 2. Con ex Ne wo k (CN): A g aph o med by all he CSs acco ding o he way p oposed by ATMS (Klee , 1986). Defini ion 3. Con ex Analy ical Redundancy Cons ain (CARC): A cons ain de i ed om he sys em, in such a way ha only obse able a iables ( a iables wi h senso s) a e ela ed. Defini ion 4. Obse a ional Model (OM):Ase o alues o he obse able a iables. Defini ion 5. Possible Minimal Conflic Con ex s (PMCC):CSs which ha e one o mo e han one CARC associa ed, whe e i s subcon ex s a e no PMCCs. Defini ion 6. Minimal Conflic Con ex (MCC): APMCC whose CARCs a e unsa isfiable o an OM.TheMCCs help us o find ou which componen s a e ailing. Defini ion 7. Hi ing Se (HS) o a collec ion o se s Cis a se H⊆S∈C Ssuch ha Hcon ains a leas one elemen o each S∈C.AHS o C is minimal iff no p ope subse o i is a HS o C. The minimal HSs o a se o MCCs a e o med by {H1,H2,... Hn}, whe e Hiis a minimal HS o componen s. The ca dinali y o Hi(|Hi|)is he numbe o componen s o Hi. In o de o know he MCC, i is necessa y o ob ain he CARCs o he sys em. Ou p oposal uses G ¨obne Bases heo y (Buchbe ge , 1985), which is he o igin o many symbolic algo i hms used o manipula e mul iple a iable polynomials. The main idea is o ha e he se o equali y poly- nomial cons ain s o he o m P=0,G ¨obne bases heo y p oduces an equi alen sys em G=0 which has he same solu ion as he o iginal one, bu subs i u ing some a iables o o he s. In o de o unde s and he G ¨obne Bases’ ech- nique be e , Figu e 1 shows a well-know exam- ple, whe e Mia e mul iplie s, Aia e adde s, and {a, b, c, d, e, , g}a e he obse able a iables. In his case, using G ¨obne Bases, an equi alen se o cons ain s is ob ained: •CARC−1{ =a∗c+b∗d}: Gene a ed om he cons ain s o he componen s {M1,M 2,A 1} •CARC−2{g=b∗d+c∗e}: Gene a ed om he cons ain s o he componen s {M2,M 3,A 2} •CARC−3{ −g=a∗c−c∗e}: Gene a ed om he cons ain s o he componen s {M1,M 3,A 1,A 2} I a CARC is unsa isfiable o an OM, i means han one o mo e han one componen ela ed wi h his CARC is w ong. M 1 M 2 M 3 A 2 A 1 a b c d e x y z g Fig. 1. A Well-known example o Model-based Diagnosis 4. CONSTRAINT DATABASES One o he difficul ies in model-based diagnosis is handling all he in o ma ion, making he in o ma- ion pe sis en and eco e able. In his pape we p opose o s o e all he in o ma ion in a Rela ional CDB, acili a ing he diagnosis p ocess. I will allow us o s o e pa ial esul s and imp o e he diagnosis ask. Con ex Ne Wo k (k)IdCon ex : in IdComponen : in Componen (k)IdComponen : in Name: S ing E o P obabili y: in Cons ain Con ex (k)IdCon ex : in (k)IdCons ain : in CARC (k)IdCons ain : in Cons ain :Cons ain Obse a ionalModel (k)IdOM: in ObsModel: S ing Unsa is iableCARC (k)IdOM: in (k)IdCons ain : in 1..n 1..n 1..n 1..n 1..n 1..1 1..1 0..n 0..n 1..1 Hi ingSe (k)IdHi ingSe : in (k)IdComponen s: in IdMO: in 1..n 1..1 1..n 0..n Fig. 2. Tables o he Cons ain Da abase In he Figu e 2, he ables o he CDB a e shown, and how he in o ma ion is s o ed. The seman ics o hese ables a e: (1) Componen : This able con ains he names, he iden ifie s and he p obabili y o e o o each componen . (2) Con ex Ne wo k: This able ep esen s he CSs ela ing he Componen s. The able has po en ially 2ncomp −1 combina ions o elemen s, bu all o hem do no ha e o be s udied. (3) CARC: This able s o es all he cons ain s de i ed om he sys em. (4) Cons ain Ne wo k: This able ela es he CSs and he CARCs. Fo example, he con- ex {M1,M 2,A 1}has he CARC { =a∗ c−b∗d}associa ed. (5) Obse a ionalModel: This able con ains he alues o all he obse able a iables. (6) Unsa isfiableCARC: This able s o es wha CARCs ail o each OM. (7) Hi ingSe : This able s o es he compo- nen s ela ed o he minimal HSs o an OM. The use o CDBs in he diagnosis p ocess is a good decision because he e a e cha ac e is ics o model-based diagnosis ela ed o he ela ional calculus used in ela ional da abases. Fo exam- ple, he componen s a e ela ed among hem us- ing a iables, he CSs and he HSs a e o med by componen s, he CSs can ha e associa ed CARCs...All hese ela ions can be ep esen ed and ea ed in an easy way using CDBs. Also, i is possible o s o e all he possible ailu es o he CARCs. I means ha he de e mina ion o he minimal HSs will be linea in unc ion o he numbe o CARCs. Fis o all, we can hink ha i is necessa y o s o e all he possible alues o OMs. Bu i is no ue, because we only need o s o e he diffe en ypes o ailu es. Fo he example shown in Figu e 1, he e a e only h ee ypes o CARCs’ ailu es o wha e e OM: {CARC −1; CARC −3},{CARC −2; CARC −3}o {CARC −1; CARC −2; CARC −3}, o he op ions a e impossible. This p ocess can be off-line and he diagnosis o an OM can be on-line and immedi- a e. 5. THE IMPROVEMENTS In his Sec ion, we p opose some imp o emen s o a oid he s udy o all minimal HSs once we ha e he MCCs o an OM.ThePMCCs a e only c ea ed once and s o ed in he CDB. In o de o ob ain he MCCs, he algo i hms desc ibed in (G´omez-L´opez e al., 2004) a e used, whe e only he ele an con ex s a e analysed. In o de o de e mine all he minimal HSs in an efficien way, we build a bidimensional able ha ep esen s he ela ions be ween he componen s and he MCCs ( ableCompsMCCs). I he CDB had no been used, he ob aining o he in o ma- ion would be much mo e difficul . The ableCompsMCCs o he example o Figu e 1 is shown in Table 1, whe e he MCC-i is ela ed o he CARC-i. Fo his example, all he PMCC a e MCCs, i means ha all he CARCs a e unsa isfiable o an OM. The able has 1in he posi ion {i, j}i he MCC-iis ela ed o he componen j,and0in o he wise. M1M2M3A1A2 MCC-1 1 1 0 1 0 MCC-2 0 1 1 0 1 MCC-3 1 0 1 1 1 Table 1. Table o Figu e 1 5.1 Fi s Imp o emen : Sea ching he Rep esen a- i e Componen s In his subsec ion, we will s udy how o de e mine equi alen componen s, p oposing he ollowing defini ions: Defini ion 8. MCCs affec ed by a componen c (MCCsAffec (c)) a e he se o MCCs ha can ail when he beha iou o componen cis w ong. Lemma: I a componen Aaffec s he same MCCs han ano he one B, i means ha i he e exis s a minimal HS M such as M=A∪N(N is a se o componen s whe e nei he Ano Bis included in N) ano he minimal HS M=B∪N exis s. In his case, i is no necessa y o s udy bo h possibili ies, only one. P oo : Le us eason by con adic ion. I Mis a minimal HS, i means ha Aaffec s some MCCs which a e no affec ed by nei he componen o N. I Bdoes no affec he same componen s han A, i means ha Bcould affec mo e MCCs han A(Mwould no be minimal), less o diffe en MCCs han A(Mwould no be a HS). Con a- dic ion. Defini ion 9: G oup o Equi alen Componen s (GEC) is a se o componen s which affec s he same MCCs. The e o e, i is only necessa y o s udy one componen o each GEC. I all he possible minimal HSs a e s udied, i will be necessa y o analyse 2ncomp −1 possibili ies. Howe e , using his imp o emen , he numbe o possible minimal HSs can be educed. Figu e 3 shows o se e al andom examples, he pe cen - age o he possibili ies elimina ed, s udying only one componen o each GEC. 0 5 10 15 20 0 20 40 60 0 20 40 60 80 100 Numbe o MCCsNumbe o Componen s Pe cen age o possible Minimal Hi ing Se s elimina ed (%) Fig. 3. Pe cen age o possibili ies elimina ed When he pe cen age is ze o, i means ha all he GECs ha e only one componen , and he e a e no componen s which affec he same MCCs. Figu e 3 also shows how he pe cen age o elim- ina ions dec eases when he numbe o MCCs inc eases. I can be explained, due o i he e a e ew componen s and a lo o MCCs will be less p obable ha wo componen s affec he same MCCs. 5.2 Second Imp o emen : Sea ching Single Mini- mal HSs Be o e s a ing he analysis o he nex p oposal, a new case o s udy is going o be in oduced, because he example shown in Figu e 1 is no big enough o see all he ypes o p oblems ha can happen in eal sys ems. The Table 2 shows he Componen sMCCs able o he new example. The e a e 8 GECs:{{s0},{s1},{s2,s 3,s 7,s 8,s 11}, {s4},{s5,s 9,s 12,s 14},{s6},{s10,s 13},{s15}}. s0s1s2s3s4s5s6s7s8s9s10s11s12s13s14s15 MCC-1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 MCC-2 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 MCC-3 0 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 MCC-4 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 MCC-5 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 Table 2. Table Example The e is ano he solu ion (de la Banda e al., 2003), ha looks o minimal single HSs a he beginning o he HSs de e mina ion. This so- lu ion de e mines he HSs o one componen s udying i he e is a componen csuch as {C − c}is sa isfiable, whe e Cis he se o unsa isfi- able cons ain s. Ou solu ion does no need o s udy he sa isfiabili y o he cons ain s, only de e mines i he e is a componen which affec s all he MCCs. The eby i a column jonly has 1s, i means ha he componen ep esen ed by he column jaffec s e e y MCCs and i o ms a minimal HS o only one componen (single minimal HS). The e o e his componen will no be in ol ed in any o he minimal HSs.Inou example he e is a single minimal HS ({s15}). The e o e, ou p oblem has been educed om 16 o 7, and he ep esen a i e componen s a e: {s0,s 1,s 2,s 4,s 5,s 6,s 10}. 5.3 Thi d imp o emen : To a oid s udying edun- dan o unp omising combina ions o componen s Be o e con inuing he s udy o minimal HSs, i is possible o know he g ea es numbe o componen s o he minimal HSs o a sys em (Max (|Hi|)). Using he example o Table 2 again, i is possible o know ha he bigges size o any minimal HS o he example is 3, because he componen s ha less affec he MCCs a e s0,s1 and s6. Fo example s0does no affec MCC-1 o MCC-3, meaning ha in he wo s case only wo componen s mo e would be necessa y. Fo his eason, i is possible o gua an ee ha : Le H={h1,...,h x}be hi ing se s and C={c1,...,c n}be componen s hen Max(|hi|)= Numbe o MCCs−Min(|MCCsAffec ed(cj)|)+1 o iin 1 ... x, jin 1 ... n S a ing wi h he ep esen a i e componen s o each GEC, we need o combine hese componen s o know i hey make up a minimal HS, bu hese combina ions will no be a blind sea ch. Le { 1, 2,..., n}be he ep esen a i e componen s, he ollowing pseudo-code helps o s o e in he a iable Hall he minimal HSs o wo compo- nen s, and in he queue Q he couples o p omising componen s which a e no HSs will be s o ed. Fo each couple o componen s { i, j}|i<j. I { i, j}is a minimal HS hen H:= H∪{ i, j} else I ¬(MCCsAffec ( i)⊂MCCsAffec ( j)) AND ¬(MCCsAffec ( j)⊂MCCsAffec ( i)) hen Q:= Q∪{ i, j} endi endi end o each I { i, j}is no a minimal HS, bu hese wo componen s could pa icipa e in a minimal HS wi h mo e componen s, hey will be included in Q o u u e sea ches. Bu i he MCCs affec ed by a componen a e included in he influenced MCCs o ano he componen , i means ha hese wo componen s will ne e pa icipa e in a minimal HS oge he , and hey will no be added o Q. I (MCCsAffec ( i)⊂MCCsAffec ( j)) o (MCCsAffec ( j)⊂MCCsAffec ( i)), i means ha he beha iou o he componen iis included in j. In o de o gene alise his idea, i is neces- sa y he ollowing defini ion. Defini ion 10: Beha iou o a Componen In- cluded in o he componen s C={ci,...,c j}(Be- ha iou Included( ,C)) iff he beha iou o he componen is included in he componen s cio ... o cj. In o de o know i MCCsAffec ( ) is included in MCCsAffec (ci), we use he bina y AND ope a o be ween he columns and ci.I ( AND ci)= , i means ha he beha iou o is a subse o he cibeha iou . Fo example, he s0beha iou is included in s2, so hese componen s a e ne e going o be oge he in a minimal HS. In ou example, some o he minimal HSs o wo componen s a e: {(s0,s 4),(s0,s 5),(s1,s 4),(s1,s 5), (s1,s 10),(s2,s 4),(s2,s 5),(s2,s 6),(s2,s 10),(s4,s 5),(s4,s 6), (s4,s 10),(s5,s 6),(s5,s 10)}. The es o combina ions o wo componen s a e added o he queue Q, because pe haps hey can o m minimal HSs combining hem wi h o he componen s. Fo ou example, he couples added o he queue a e: {(s0,s 1),(s0,s 6),(s1,s 6)}. The sea ch will no end un il Qis emp y. Wi h he se o componen s aken ou om Q,we y o c ea e minimal HSs o n+1 componen s, whe e nis he numbe o componen s ob ained om Q. I hese n+ 1 componen s a e no a minimal HS and (n+1)=(Max (|Hi|)), hese will no be added o Q. In o de o a oid possible non minimal HSs, he algo i hm combines he componen s C aken ou om he queue C={ci,...,c j}wi h ano he {ck} i and only i k>j. The ollowing algo i hm is execu ed o each o he men ioned possibili ies and he componen s ob ained om he queue. I (¬Beha iou Included(ck,C)) I (MinimalHi ingSe (C,ck)) H:= H∪{C∪ck} else Q:= Q∪{C∪ck} endi endi In o de o unde s and he abo e algo i hm, i is necessa y o explain he ollowing me hod: The MinimalHi ingSe (Componen s C, Compo- nen c) me hod e u ns ue i C∪cis a mini- mal HS, a oiding n- uples like {s0,s 1,s 4}. These h ee componen s a e a HS, bu no a minimal HS. The idea o he me hod is o de e mine i all he componen s o a se Ca e essen ial o o m a minimal HS analysing each MCC.I means ha i we se aside a componen , he se o emaining componen s would no be a HS. Fo example, i we wan o know i {s0,s 1,s 4}is a minimal HS, he Table 3 will be s udied. s0s1s4 MCC-1 0 0 1 MCC-2 1 1 1 MCC-3 0 1 1 MCC-4 1 1 0 MCC-5 1 0 1 Table 3. Example o minimal HS In o de o s o e he indispensable componen s, we will use a se I={I1,...,In}, such ha i Iihas one componen , i means ha his com- ponen is indispensable. Bu i Iihas se e al componen s, i means ha one o hese com- ponen s a e indispensable. In gene al he se I ={{si...s j},{sk...s h},...,{sl...s m}} means ha he indispensable componen s a e {(si∨...∨ sj)∧(sk∨...∨sh)∧(sl∨...∨sm)}.Fo each MCC,Iwill be modified as ollow: •I MCC-i is affec ed only by one componen c: I means ha his componen is indispensable o ob ain a minimal HS. And Iis upda ed as I:=I∪{c}, whe e cis he indispensable componen . •I MCC-i is affec ed by a se o mo e han one componen called C: ·I ∀Ii:i:1...n Ii∩C =∅⇒I i:= Ii∩C  ·I ∃Ii:i:1...n Ii∩C =∅⇒I:= I∪C  •MCC-i is affec ed by all he componen s C:Nei he o hem a e indispensable. I a e he s udy o all MCCs,I=C, i means ha Cis a minimal HS. In o he cases Cwould no be a minimal HS. The ace o he example shown in Table 3 is: o MCC-1 : I={s4} o MCC-2 : I={s4}nei he componen is added because MCC-2 is affec ed by all componen s o MCC-3 : I={s4} o MCC-4 : I={s4},{s0,s 1} o MCC-5 : I={s4},{s0} As Idoes no ha e {s0,s 1,s 4},i means ha no all componen s a e indispensable, he e o e {s0,s 1,s 4}is no a minimal HS. Wi h all hese imp o emen s he numbe o pos- sible minimal HSs is educed in an impo an way. Figu e 4 shows he pe cen age o he pos- sibili ies elimina ed wi h his echnique, ela ed o he fi s imp o emen . And Figu e 5 shows he compu a ional ime o se e al andom examples, wi h diffe en numbe o componen s and MCCs. 0 5 10 15 20 0 10 20 30 40 50 20 30 40 50 60 70 80 90 100 Numbe o MCCs Numbe o Componen s Pe cen age o possible Minimal Hi ing Se s elimina ed(%) Fig. 4. Pe cen age o possibili ies elimina ed 0 5 10 15 2 0 0 10 20 30 40 50 0 200 400 600 800 1000 1200 1400 1600 1800 Numbe o MCCs Numbe o Componen s Running Time (ms) Fig. 5. Execu ion ime(Pen . IV, 512 M memo y) 6. CONCLUSIONS Ou wo k p oposes o build an equi alen sys em wi h obse able a iables, which will be gene - a ed once o each sys em and alida ed o each OM. Mo eo e , h ee imp o emen s ha e been p esen ed in o de o a oid he s udy o unp omis- ing combina ions o componen s. In o de o s o e all he in o ma ion, we use a CDB. I allows us o ob ain and s o e he pa ial da a and all he possible combina ion o MPCCs and he minimal HSs. I makes possible o ob ain a diagnosis in linea ime in unc ion o he numbe o CARCs, because he ob aining o he minimal HSs can be an off-line p ocess. In un ime only will be necessa y o alida e each CARC o know wha MCCs a e ailing, and o que y he da abase abou he minimal HSs. REFERENCES Buchbe ge , B. (1985). G ¨obne bases: An algo- i hmic me hod in polynomial ideal heo y. D. Reidel Publishing Co.. pp. 184–232. de la Banda, M. G., P. J. S uckey and J. Wazny (2003). Finding all minimal unsa isfiable sub- se s. In: PPDP ’03. ACM P ess. pp. 32–43. Fa ah, Yous i El and Rina Dech e (1995). Di- agnosing ee-decomposable ci cui s.. In: IJ- CAI. pp. 1742–1749. G´omez-L´opez, M. T., R. Ceballos, R. M. Gasca and C. Del Valle (2004). Cons ain da abases echnology o polynomial models diagnosis.. In: 15 h In e na ional Wo kshop on P inci- ples o Diagnosis. pp. 215–220. G eine , R., B. A. Smi h and R. W. Wilke son (1989). A co ec ion o he algo i hm in e- i e ’s heo y o diagnosis. Vol. 41. Else ie Science Publishe s L d. pp. 79–88. Han, B. and S. Lee (1999). De i ing minimal conflic se s by cs- ees wi h ma k se in diagnosis om fi s p inciples. Vol. 29-2. Hou, Aimin (1994). A heo y o measu emen in diagnosis om fi s p inciples. Vol. 65. Else ie Science Publishe s L d.. pp. 281–328. Klee , J. De (1986). An assump ion-based u h main enance sys em. Vol. 2. pp. 127–161. Kupe , G., L. Libkin and J. Pa edaes (1998). Cons ain Da abases. Sp inge . Rei e , R. (1987). A heo y o diagnosis om fi s p inciples. Vol. 1. pp. 57–96. Re esz, P. (2002). In oduc ion o cons ain da abases. Sp inge -Ve lag New Yo k, Inc.. New Yo k, NY, USA. S ump ne , Ma kus and F anz Wo awa (1997). Diagnosing T ee-S uc u ed Sys ems. Nagoya, Japan. Wo awa, F anz (2001). A a ian o ei e ’s hi ing-se algo i hm.. Vol. 79. pp. 45–51.