Theory Diagnoses: A Concise Characterization of Faulty Systems

1 Introduction

Consistency-based diagnosis systems ([3]) seek for sets of assumptions about the behavior of components which are consistent with the system description and the obser­ vations . The concept of kernel diagnoses was introduced in [3] in order to characterize the set of all consistency­ based diagnoses . Kernel diagnoses are replacing the con­ cept of minimal diagnoses which are not adequate in the case where supersets of minimal diagnoses can be inconsistent. If all supersets of minimal diagnoses are consistent or if supersets of minimal diagnoses are very unlikely, focusing on minimal diagnoses is still a good choice for practical reasons. Firstly, there sometimes exist exponentially more kernel diagnoses than minimal diagnoses. Secondly, let us assume that supersets of a minimal diagnosis are much more unlikely than the mi­ nimal diagnosis itself (which is the case in most practical applications) . In this case further decisions like propo­ sing the best next measurement are hardly influenced at all by considering supersets of minimal diagnoses. The­ refore, minimal diagnoses or a subset of them are used as a starting point for the generation of non-minimal diagnoses if such diagnoses influence further decisions.

However, there is still the possibility of a combinato­ rial explosion although only minimal diagnoses are con­ sidered. Assume that there are several independent and faulty modules in a system, then every minimal diagno­ sis of the whole system is a combination of the minimal diagnoses of the modules.

It was argued by numerous researchers (e.g. [2, 7, 3, 9, 13]) that hierarchical diagnosis would avoid several problems of a flat approach to diagnosis. However, ex­ ploiting hierarchies is still based on heuristic arguments rather than on firm grounds, e.g. selecting the best next measurement using hierarchies. Until now there has been no theory of diagnosis in the sense of [3] which allows to exploit such hierarchical structures for a characterization of diagnoses. Therefore, as soon as a composite compo­ nent is broken up into its pieces, the descriptive power of hierarchies is lost.

Although kernel diagnoses provide a concise descrip­ tion of the set of all diagnoses, "this approach flattens out since there is no ability to enable hierarchical dia­ gnosis, so achieving reduction of complexity" ([10], page 466). We therefore developed a new concept for a concise description of the set of all diagnoses where we are able to exploit additional knowledge, e.g. hierarchical relations. The main idea of our approach is that such knowledge expressed by a theory is exceptional. A characterization of diagnoses is done with respect to such a theory, i.e. a conjunction of "abnormal" literals (which we will call theory diagnosis) unified with a theory (e.g. describing abstractions based on component hierarchies) serves as a description of sets of diagnoses.

Although we focus in this paper on a concise de­ scription of the set of minimal diagnoses (because of application-oriented reasons) our approach naturally ex­ tends to a concise description of the set of all diagnoses which is discussed in the longer version of this paper.

The paper is organized as follows: In Section 2 we present an example showing that hierarchies flatten out if the traditional definition of consistency-based diagno­ sis is used. In Section 3 we propose an extension of the consistency-based approach where we use theories as means for a concise description of diagnoses . Hierar­ chical theories are formally introduced in Section 4. We show that hierarchical theories and theory-based diagno­ ses provide a computationally cheap generator for mini­ mal diagnoses and how hierarchical theories can be ad­ apted to preserve the descriptive power.

2 Hierarchies and Minimal Diagnoses

Consider the system and the observations depicted in Fi­ gure 1. The system consists of two buffer chains which are connected to an or-gate. We assume the usual beha­ vior of these components. For the sake of simplicity we don't consider fault modes. The inputs of the circuit are observed to be 1 and the output of cl to be 0.

There is one minimal single fault diagnosis ab(cl) and 4 minimal double fault diagnoses ab( c2a) /1. ab( c3a), ab( c2a )!l.ab( c3b), ab( c2b )!l.ab( c3a), and ab( c2b )!l.ab( c3b) . 1 Note, that if there are n buffers in each chain then there are n 2 minimal double fault diagnoses.

Clearly, there is a much more comprehensive descrip­ tion than stating all pairs of possibly faulty buffers: cl is abnormal or there is a double fault where one buffer of the upper and one buffer of the lower buffer chain are ab­ normal. In this case we have used an abstraction of the buffer chains where we don't care which buffer in a chain is faulty. There are many sources for such abstractions. E.g. assume that a buffer chain is a smallest replaceable unit. A further example is the case where multiple in­ dependent diagnosis problems are present in one system [5) (e.g. consider cl is correct). Under this circumstances the diagnosis system should have the ability to generate abstractions in order to avoid a combinatorial explosion resulting from computing the cross product .

For these (and other) reasons many researchers have proposed the usage of hierarchies (e.g. [2 , 7, 3, 9, 13)), i.e. the abstraction of components forming a composite component. Note, that they all use the usual definition of consistency-based diagnosis and therefore don't avoid the problem of flatting out the hierarchies. The abstrac­ tion of the buffer chains can be expressed very simply by the following equivalences forming a hierarchy of com­ ponents:

and the addition of the components c2 and c3 to the set of components COM PS. We call the theory consisting of these two equivalences Ea.

The circuit extended by such composite components is depicted in Fig. 2. The equivalences express that if a composite component is faulty then at least one of its subcomponents is faulty. Conversely, if a subcomponent is faulty then the composite component is faulty. Note, that a faulty component (e.g. the composite component) need not show its abnormal behavior in a given situa­ tion. The fault is latent. But, if a subcomponent is at variance then also its supercomponent (see also [6) for a discussion on faulty behavior versus failure). In this ex­ ample we use identities to express abstractions but our method allows arbitrary abstraction theories. The beha­ vior of the composite components c2 and c3 is the same as for the buffers, i.e. output and input of a composite component are equal if it works correctly.

1 We only mention the positive abnormal literals of mi­ nimal diagnoses, all other components are not abnormal by default . Furthermore, we assume that the reader is familiar with the basic definitions introduced in (3].

Extending the system (SD, COM PS, OBS) by these axioms and components will lead to the following mini­ mal conflicts and minimal diagnoses:

Minimal conflicts due to faulty behavior:

ab(cl) Vab(c2). ab(cl) V ab(c3).

ab(cl) V ab(c2a) V ab(c2b) . ab(cl) V ab(c3a) V ab(c3b) .

Minimal conflicts due to the hierarchical theory:

·ab( c2) V ab( c2a) V ab( c2b) .

ab(c2) V ·ab(c2a) . ab(c2) V ·ab(c2b) .

·ab( c3) V ab( c3a) V ab( c3b) .

ab(c3) V ·ab(c3a) . ab(c3) V ·ab(c3b) .

Minimal diagnoses:

Note, that by using minimal diagnoses we do not have the ability to take advantage of hierarchies . Intuitively it should be possible to describe the set of minimal dia­ gnoses and also the set of all diagnoses just by ab( cl) and ab(c2) /1. ab(c3) . Our basic idea is that the informa­ tion about hierarchies in a system has a special status . Describing the set of minimal diagnoses exploiting this information leads to a new definition of diagnosis .

3 Theory Diagnoses

In this section we define a new concept for the descrip­ tion of diagnoses which allows to take advantage of hier­ archical theories resulting in a concise characterization. Although we focus on hierarchical theories in this paper (which are described in Section 4) the new concept for the description of diagnoses we propose is independent of hierarchical theories .

We assume that abstractions are expressed in terms of ab-clauses . Such clauses are conflicts if they are regarded as elements of SD. Consequently, the number of kernel or minimal diagnoses as well as the number of (positive) literals mentioned in these diagnoses can grow or shrink depending on which ab-clauses are used for defining a (hierarchical) theory and the set of conflicts implied by the system description and the observations. Note, that in the example of Section 2 the introduction of the hier­ archies described by Ea does not reduce the number of minimal diagnoses but enlarges the number of positive literals of all but one of these diagnoses.

Since clauses like hierarchical theories play a special role , they have to be treated differently. Therefore, we define diagnosis with respect to an ab-theory :E.

3.1 Characterizing Minimal Diagnoses

In this section we define a concept for the description of minimal diagnoses. We describe the set of all minimal diagnoses by a set of theory diagnoses and an ab-theory. D(Cp, Cn) denotes 1\cECp ab(c) /1. 1\cECn ·ab(c). SD, the system description, and OBS, a set of observations, are sets of first-order sentences; COM PS, the system components, is a finite set of constants .

Definition 1 (Theory Diagnosis for Minimal Diagno­ ses) A conjunction T of ab-literals is called a theory dia­ gnosis for minimal diagnoses of (SD, COM PS, OBS) and a set of ab-clauses I; ~ SD (called an ab-theory) iff for every minimal diagnosis D(fi,COMPS- fl.) of ( {T} U I:, COM PS, 0) follows that D(£1, COM PS- fl.) is a minimal diagnosis for (SD, COM PS, OBS) .

We call a theory diagnosis for minimal diagnoses a M(inimal)T(heory)-diagnosis. Note, that such MT­ diagnoses are not necessarily irreducible but are a con­ cept for describing minimal diagnoses of a system.

Given an ab-theory, an MT-diagnosis contains all the necessary information for describing a set of minimal dia­ gnoses for the complete system (SD, COM PS, OBS). The ab-theory and the MT-diagnosis serve as a generator for a set of minimal diagnoses. The ab-theory describes how an MT-diagnosis has to be extended in order to provide minimal diagnoses for (SD, COM PS, OBS).

Example 1 Consider Fig. 2. ab( cl) and ab( c2) /1. ab( c3) are MT-diagnoses for the given hierarchical theory I:a. Every minimal diagnosis for { ab( cl)} U I: a and { ab( c2) /1. ab( c3)} U I: a is a minimal diagnosis for this circuit.

Let M DIAGS(T) be the set of minimal diagnoses of ( {T} U I:, COM PS, 0) where Tis an MT-diagnosis. We call this set the induced set of minimal diagnoses. In our example the set of all minimal diagnoses is equal to the union of the induced minimal diagnoses of ab(cl) and ab(c2)/\ab(c3), i.e. MDI AGS(cl) U MDI AGS(ab(c2) /1. ab( c:3)). As a consequence, we have achieved a reduction of the number of diagnoses necessary for the description of all minimal diagnoses.

Irreducible MT-diagnoses are defined as follows. We use the function ATOMS( C) to denote the set of atoms of a logical sentence C.

Definition 2 (Irreducible MT-Diagnosis) An irreduci­ ble MT-diagnosis T is an MT-diagnosis with the pro­ perty that the only MT-diagnosis T' which is a subcon­ junction ofT, i.e. ATOMS(T') ~ ATOMS(T), is the MT-diagnosis T itself.

The following theorem 2 is a simple consequence of the definition of an MT-diagnosis. It states that MT­ diagnoses describe the set of all minimal diagnoses. Fur­ thermore, this is also true if we only consider MT­ diagnoses which contain only positive ab-literals. In this case we say, this theory diagnosis is positive.

Theorem 1 Let I: ~ SD be an ab-theory for a system (SD, COM PS, OBS).

2 The proof of this theorem and all other proofs can be found in the longer version of this paper.

If D is a minimal diagnosis for (SD, COM PS, OBS) then there is a (positive) MT-diagnosis T for (SD, COMPS, OBS) and I:, and ATOMS(T) ~ ATOMS(D).

Conversely, if Tis a (positive) MT-diagnosis for (SD, COM PS, OBS) and I; then there is a minimal dia­ gnosis D for (SD, COM PS, OBS) and ATOMS(T) ~ ATOMS( D).

Similar to the relation between minimal diagnoses and positive minimal conflicts, MT-diagnoses and positive conflicts can be related .

Theorem 2 T is an MT-diagnosis for a system (SD, COM PS, OBS) and an ab-theory I: ~ SD iff {T} U I: implies each positive (minimal) conflict of (SD, COM PS, OBS).

The following corollary is a simple consequence of the above theorem and relates irreducible MT-diagnoses and positive minimal conflicts.

Corollary 1 T is an irreducible MT-diagnosis for a sy­ stem (SD, COM PS, OBS) and an ab-theory I: ~ SD iff {T} U I: implies each positive (minimal) conflict of (SD, COM PS, OBS) but for each subconjunction T' of T {T'} U I: does not imply each positive (minimal) conflict of (SD, COM PS, OBS).

Example 2 Consider the circuit and the hierarchical theory presented in Section 2. Let the hierarchical theory I:a be the theory used for generating MT-diagnoses. For the given observations there are several MT-diagnoses. Let us consider ab(cl) and ab(c2) 1\ ab(c3). Since { ab( c1)} U I: a as well as { ab( c2) /1. ab( c3)} U I: a implies all minimal positive conflicts, both ab( cl) and ab( c2) 1\ ab(c3) are MT-diagnoses. As they cannot be reduced without losing this property, they are irreducible MT­ diagnoses. Note, that we have achieved a reduction of the number of positive literals compared to minimal dia­ gnoses. However, in our example there also exist several other MT-diagnoses:

ab(c2a) /1. ab(c3a). ab( c2a) /1. ab( c3b). ab(c2b) /1. ab(c3a) . ab(c2b) /1. ab(c3b).

Note, that these MT-diagnoses are more specific than the MT-diagnosis ab(c2) /1. ab(c3) since the hierarchical theory joined with such a more specific theory diagnosis implies ab(c2) /1. ab(c3).

The following corollary states that such specific MT­ diagnoses can be pruned from the set of MT-diagnoses. It holds for positive MT-diagnoses.

Corollary 2 Let {Tl, .. . , Tn} be a set of different po­ sitive MT-diagnoses for (SD, COM PS, OBS) and an ab- theory I: ~ S D .

{Tl} U I; I= T2 V ... V Tn (the diagnoses T2, ... , Tn are at least as general as Tl) iff every conjunc­ tion D(£1, COM PS - fl.) which is a minimal dia­ gnosis for ( {Tl} U I:, COM PS, 0) is also a minimal diagnosis for one of ( {T2} U I:, COM PS, 0) or ... or ( {Tn} u I:, COM PS, 0).

Stating it differently, the positive MT-diagnoses T2, ... , Tn are at least as general as the positive MT­ diagnosis Tl iff the set of minimal diagnoses described by T2, .. . , Tn is a superset (not necessarily proper) of the set of minimal diagnoses described by Tl. Therefore, Tl is redundant .

Example 3 Consider the MT-diagnoses of our example:

Each of these MT-diagnoses joined with the theory I: a implies the positive MT-diagnosis ab( c2) 1\ ab( c3) and therefore all these MT-diagnoses are redundant.

Since the set of all MT-diagnoses is larger than nee­ ded for the description of all minimal diagnoses we are interested in a set of MT-diagnoses which is as small as possible.

Definition 3 (Irredundant set of MT-diagnoses) A set of MT-diagnoses MTS for (SD, COM PS, OBS) and an ab-theory I: ~ SD is irredundant iff it is a smal­ lest cardinality set with the property that every mini­ mal diagnosis D for (SD, COM PS, OBS) is an ele­ ment of the induced minimal diagnoses of MTS, i.e. DE UTEMTS M DIAGS(T) .

Stating it differently, if an element (i.e. an MT­ diagnosis) of an irredundant set of MT-diagnoses is ex­ cluded then the remaining set of MT-diagnoses cannot describe the set of all minimal diagnoses of a system.

The following theorem states that it is possible to de­ scribe the set of all minimal diagnoses with a smaller (or at most equally large) set of MT-diagnoses .

Theorem 3 If MIN DIAGS is the set of minimal dia­ gnoses for (SD, COM PS, OBS) and I: ~ SD an ab-theory then there exists an irredundant set of MT­ diagnoses MTDIAGS for (SD, COM PS, OBS) and I: s.t . IMTDIAGSI ~ IMINDIAGSI .

The following theorem characterizes an irred undan t set of positive MT-diagnoses:

Theorem 4 A set of positive MT-diagnoses MTS = {Tl, ... , Tn} for (SD, COM PS, OBS) and an ab­ theory I: ~ SD is irredundant iff for all Ti, Tj E MTS and Ti "I Tj follows that {Ti} U I:~ Tj and every mini­ mal diagnosis D for (SD, COM PS, OBS) is an element of the induced minimal diagnoses of MTS .

Example 4 The set of MT-diagnoses {ab(cl),ab(c2) 1\ ab(c3)} is irredundant. No MT-diagnosis of this set ent­ ails the other using the theory I: a .

Consequent ly, we need only two MT-diagnoses to de­ scribe the set of all minimal diagnoses of the example circuit. These two MT-diagnoses are sti ll sufficient if the buffer chains are arbitrarily long.

4 Hierarchical Theories

In the previous section we developed the concept of MT­ diagnoses, describing minimal diagnoses using an ab­ theory. Until now we have not imposed any constraint on such an ab-theory. Note, that the set of all conflicts of a system may also be considered as an ab-theory for MT-diagnoses. In this case the empty set is the only irre­ ducible MT-diagnosis. However, such an MT-diagnosis and ab-theory would not be accepted as a diagnosis be­ cause from this description one cannot easily determine the minimal diagnoses. Even asking whether an additio­ nal minimal diagnosis exists is NP-complete. Therefore, we are interested in abstraction theories which allow the efficient generation of diagnoses as it is the case for kernel diagnoses.

In this section we introduce hierarchical theories which together with MT-diagnoses serve as a generator for all minimal diagnoses. Note, that the decision which mi­ nimal diagnoses should be constructed depends on the goals of the diagnosis process. Based on the properties of hierarchical theories we show that all minimal diagnoses can be efficiently computed, given an irredundant set of positive MT-diagnoses. Additionally, the test needed to show that a set of MT-diagnoses is irredundant can be done easily.

Definition 4 (Hierarchical Theory) A hierarchical theory is a set of ab-clauses of the form

where all literals contained in such an identity are uni­ que. The left hand side contains exactly one literal. The right hand side at least one literal.

There are no two equivalences having a same literal on the left hand side, and there are no two equivalences having a same literal on the right hand side.

Note, that such an equivalence corresponds to a set of clauses of the form:

Such a hierarchical theory defines a set of directed trees where ab( c;) is the direct predecessor of each ab( c,) E { ab( Cj ), ... , ab( ck)} . Each identity uniquely de­ fines all successors of an ab( c;) . The nodes are labeled by these literals.

4.1 Testing for lrredundancy

In order to show that a set of positive MT-diagnoses is irredundant, we have to perform tests of the form {Tl} UI: f= T2 where Tl, T2 are positive MT-diagnoses and I: is a hierarchical theory. For this test we have to compute the set of positive ab-literals entailed by {Tl}UI:.

Corollary 3 Let Tl, T2 be positive MT-diagnoses and I: a hierarchical theory. For testing if {Tl} U I: f= T2 only the Horn-clauses of I: have to be considered.

As a consequence, the test whether {Tl} U I: f= T2 can be carried out in linear time.

4.2 Generating Minimal Diagnoses

Since hierarchical theories serve as a generator for mi­ nimal diagnoses we have to show how minimal diagno­ ses can be computed, given a conjunction of ab-literals (e.g. an MT-diagnosis). Since an irredundant set of MT­ diagnoses can be easily computed using only positive MT-diagnoses we focus on the generation of minimal dia­ gnoses given a positive MT-diagnosis.

For the construction we use the following properties of hierarchical theories: Each positive ab-literal implies that all predecessor literals are positive. Stating it diffe­ rently, if a component is assumed to be abnormal then e\·cry super-component is also assumed to be abnormal. Therefore, given a positive MT-diagnosis, every prede­ cessor of a literal in this diagnosis can be pruned since it is implied by the hierarchical theory unified with ano­ ther literal of the diagnosis. We call such a positive MT­ diagnosis a pruned positive MT-diagnosis .

Let p1·ed( ab( ci)) be the set of predecessors of a lite­ ral ab(ci). Let path(ab(ci), ab(cj)) be the set of literals between ab(ci) and ab(cj) including these literals. The components mentioned by a set of ab-literals (or a logi­ cal sentence) S are denoted by comp(S). The following corollary describes how minimal diagnoses can be com­ puted.

Corollary 4 Let T be a pruned positive MT-diagnosis.

where ab(cj) is a leaf node connected to ab(ci) (i .e. ab( cj) is a successor of ab( ci) and ab( cj) has no succes­ sor) iff D(comp(~), COM PS- camp(~)) is a minimal diagnosis for ( {T} U I;, COM PS, 0) and therefore it is a minimal diagnosis for (SD, COM PS, OBS) .

Stating it differently, minimal diagnoses can be simply generated from a pruned positive MT-diagnosis T and a hierarchical theory in the following way: For each literal/ in T all predecessors have to be included plus the literals along the path from / to a leaf connected to /. This defines all components to be assumed as abnormal.

Example 5 Consider the MT-diagnosis ab( c2) 1\ ab( c3) of our example and the hierarchical theory I; a . From this MT-diagnosis and I;a the following minimal diagnoses can be computed according to the above corollary:

4.3 Translating Non-positive MT-Diagnoses

In the previous sections we showed that positive MT­ diagnoses have extreme good properties with respect to the irredundancy test and the generation of minimal diagnoses. However, one can argue that positive MT­ diagnoses tend to flatten out if components are exonera­ ted 3 .

Example 6 Consider a slight extension of our example, where the buffer chains consist of n buffers and let us assume that some buffers, e.g. the first k (k < n) buffers of each chain are known to be not faulty.

The corresponding hierarchical theory I;a is:

In this case the MT-diagnosis ab(c2)/\ab(c3) w.r .t . I;a is not longer an MT-diagnosis . One way to deal with this problem is to consider I;a as fixed and to break up this MT-diagnosis into a set of positive MT-diagnoses using the subcomponents of c2 and c3. Another possibility is to use non-positive MT-diagnoses. The conjunction ab( c2)/\ ab( c3)/\ ....,ab( c2a)/\ ... 1\ --,ab( c2k )/\ ....,ab( c3a )A .. . 1\ --,ab(c3k) is an MT-diagnosis w.r.t. I;a ·

3 Note, that this is not possible if the unknown fault mode is included in the behavior description of every component .

But since we model the abstraction hierarchy expli­ citly, we are able to reconstruct this hierarchy accordin­ gly to our needs. Therefore, there exists another op­ tion where the hierarchical theory is changed. We in­ troduce two additional abstract components c2' and c3' and change the subcomponents of c2 and c3 accordingly. This leads to the following new abstraction theory I;new:

The corresponding MT-diagnosis is still ab( c2) t\ ab(c3) . Again, we avoided the combinato~ial explosion leading to an O(n 2 ) description.

This example can be generalized in order to convert a set of MT-diagnoses MTS (including non-positive ones) and a hierarchical theory I; into a set of positive MT­ diagnoses MT Snew and I;new where the set of minimal diagnoses described stays the same. The complete algo­ rithm is given in the extended version of this paper .

By this method we are able to change a set of MT­ diagnoses (containing negative literals) and its corre­ sponding hierarchical theory in a set of positive MT­ diagnoses and a new hierarchical theory. Thus preser­ ving the good properties of positive MT-diagnoses . Note, that the cardinality of an irredundant set of positive MT­ diagnoses is always less or equal to the number of mini­ mal diagnoses. In this method the given structure of the device (usually corresponding to the structure of a designer's mental view of the device) is preserved.

5 Comparison

The use of abstractions of devices for a more efficient dia­ gnosis process was proposed by many researchers, e.g. [2, 7, 3, 9, 13]. Broadly speaking, their aim is to ex­ ploit abstractions like component hierarchies or behavior abstractions to make candidate generation and verifica­ tion more efficient. However, in all theses approaches no concise description of at least the minimal diagnoses is achieved. The works of [4], (14], and (12] are exceptional because they aim at characterizing sets of diagnoses .

The approach of [4] deals mainly with the integration of working hypotheses which are made by a diagnostic reasoner during the process of diagnosis. However, the combinatorial explosion of characterizing the minimal diagnoses of our example is not avoided. The description of diagnoses in [14] uses a two-level and/or graph for the description of diagnoses and can therefore be seen as a special case of our approach.

A further interesting approach is proposed in [12] . They introduce the concepts of abstract and concrete diagnosis. Abstract diagnoses are defined as ab-theories and no further syntactical constraints are required . Con­ sequently, the set of all minimal conflicts is the unique maximally abstract diagnosis. However, generating mi­ nimal diagnoses from this description is NP-hard. The same property holds for abductive diagnoses as defined by [1, 8] if these diagnoses have to be extended to consi­ stency based (e.g. minimal) diagnoses in order to assign probabilities. Since in our approach the underlying ab­ straction theory is explicit, we can restrict this theory (as it is the case for hierarchical theories) in order to provide efficient generators for minimal diagnoses. Concrete dia­ gnoses force a mode assignment to all components and therefore they also flatten out.

In the most recent work by [11] combinatorial explo­ sion is avoided by identifying critical conflicts. In op­ posite to our approach not all minimal diagnoses are characterized which can lead to suboptimal probes as it is the case for our example depending on the relation between the failure probability of buffers and or-gate.

6 Conclusions

Although the concepts of minimal diagnoses and ker­ nel diagnoses provide a concise description of the set of all diagnoses, we pointed out that within this formalism there is no ability to exploit knowledge about abstrac­ tions in order to achieve a concise characterization of all diagnoses . Consequently, hierarchies of components (forming composite components) flatten out. We propo­ sed a new approach for the characterization of diagnoses exploiting the descriptive power of theories, e.g. hierar­ chical theories. We call these diagnoses theory diagnoses because they are defined with respect to a theory. By such a descriptive characterization we can separate very clearly problem description from problem solving follo­ wing the approach taken in model-based diagnosis ([3]) .

In this paper we focused on theory diagnoses for the description of minimal diagnoses (called MT-diagnoses) . However, our approach can be easily adapted to theory diagnoses for the description of all diagnoses, which is discussed in the longer version of this paper . We showed that MT-diagnoses always provide a concise description of the set of all minimal diagnoses by reducing the num­ ber of diagnoses and literals needed for a complete cha­ racterization. Furthermore, we stated the relation bet­ ween conflicts and MT-diagnoses and gave a condition whether or not a set of positive MT-diagnoses is irred­ undant. We proceeded by discussing hierarchical theo­ ries in detail, showing how minimal diagnoses can be easily generated given a set of positive MT-diagnoses . Additionally, we stated that the test whether a set of MT-diagnoses is irredundant or not as well as detecting which MT-diagnosis is redundant can be carried out ef­ ficiently. Finally, we pointed out how the hierarchical theory can be automatically rewritten in order to pre­ serve these good properties of positive MT-diagnoses on one hand arid to avoid hierarchies to flatten out in case of exoneration on the other hand.

Based on a clear definition of diagnosis where it is possible to exploit (hierarchical) theories, several further research issues can be investigated such as the dynamic generation of abstractions.

Acknowledgments

We would like to thank Philippe Dague, Walter Ham­ scher, and anonymous referees for valuable comments on this work.