article which was just published in JAIR:
</bigger>Darwiche, A. (1998)
"Model-Based Diagnosis using Structured System Descriptions",
Volume 8, pages 165-222.
Available in PDF, PostScript and compressed PostScript.
For quick access via your WWW browser, use this URL:
http://www.jair.org/abstracts/darwiche98a.html
More detailed instructions are below.
Abstract: This paper presents a comprehensive approach for
model-based
diagnosis which includes proposals for characterizing and computing
preferred diagnoses, assuming that the system description is
augmented
with a system structure (a directed graph explicating the
interconnections between system components). Specifically, we first
introduce the notion of a consequence, which is a syntactically
unconstrained propositional sentence that characterizes all
consistency-based diagnoses and show that standard characterizations
of diagnoses, such as minimal conflicts, correspond to syntactic
variations on a consequence. Second, we propose a new syntactic
variation on the consequence known as negation normal form (NNF) and
discuss its merits compared to standard variations. Third, we
introduce a basic algorithm for computing consequences in NNF given
a
structured system description. We show that if the system structure
does not contain cycles, then there is always a linear-size
consequence in NNF which can be computed in linear time. For
arbitrary
system structures, we show a precise connection between the
complexity
of computing consequences and the topology of the underlying system
structure. Finally, we present an algorithm that enumerates the
preferred diagnoses characterized by a consequence. The algorithm is
shown to take linear time in the size of the consequence if the
preference criterion satisfies some general conditions.
The article is available via:
-- comp.ai.jair.papers (also see comp.ai.jair.announce)
-- World Wide Web: The URL for our World Wide Web server is
For direct access to this article and related files try:
http://www.jair.org/abstracts/darwiche98a.html
-- Anonymous FTP from either of the two sites below.
Carnegie-Mellon University (USA):
ftp://ftp.cs.cmu.edu/project/jair/volume8/darwiche98a.ps
The University of Genoa (Italy):
ftp://ftp.mrg.dist.unige.it/pub/jair/pub/volume8/darwiche98a.ps
The compressed PostScript file is named darwiche98a.ps.Z (327K)
-- automated email. Send mail to jair@cs.cmu.edu or
jair@ftp.mrg.dist.unige.it
with the subject AUTORESPOND and our automailer will respond. To
get the Postscript file, use the message body GET
volume8/darwiche98a.ps
(Note: Your mailer might find this file too large to handle.)
Only one can file be requested in each message.
For more information about JAIR, visit our WWW or FTP sites, or
send electronic mail to jair@cs.cmu.edu with the subject AUTORESPOND
and the message body HELP, or contact jair-ed@ptolemy.arc.nasa.gov.