Computing approximate diagnoses by using approximate entailment

Annette ten Teije
Frank van Harmelen

The most widely accepted models of diagnostic reasoning are all phrased in terms of the logical consequence relations. In work in recent years, Schaerf and Cadoli have proposed efficient approximations of the classical consequence relation. The central idea of this paper is to parameterise the notion of diagnosis over different approximations of the consequence relation. This yields a number of different approximations of classical notions of diagnosis. We derive results about the relation between approximate and classical notions of diagnosis. Our results are attractive for a number of reasons. We obtain more flexible notions of diagnosis, which can be adjusted to particular situations. Furthermore, we obtain efficient anytime algorithms for computing both approximate and classical diagnoses.

(PDF paper, 185Kb)

A shorter version of this paper (basically without the proofs) has appeared in the proceedings of the Dutch National Conference on AI (NAIC'96).
An earlier version has appeared in the proceedings of the ECAI'96 workshop on Advances in Propositional Reasoning. This version has some slight technical mistakes in it (and no proofs), but presents additional results on an extended notion of diagnosis which includes both an abductive and a consistency-based component.

@InProceedings{KR96,
  author =       "A. ten Teije and F. van Harmelen",
  title =        "Computing approximate diagnoses by using approximate
                  entailment",
  booktitle = 	 "Proceedings of the Fifth International Conference on
                  Principles of Knowledge Representation and Reasoning
		  ({KR'96})",
  year = 	 1996,
  address = 	 "Boston, Massachusetts",
  month = 	 "November",
  pages = 	 "265-256",
  keywords = {Approximate Reasoning, Diagnostic Reasoning},
  urlPaper = "http://www.cs.vu.nl/~frankh/postscript/KR96.pdf"
}

Back to list of papers