Controlling the complexity in model-based diagnosis View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1994-03

AUTHORS

Igor Mozetič, Christian Holzbaur

ABSTRACT

We present IDA — an incrementaldiagnosticalgorithm which computes minimal diagnoses from diagnoses, and not from conflicts. As a consequence of this, and by using different models, one can control the computational complexity. In particular, we show that by using a model of the normal behavior, the worst-case complexity of the algorithm to compute thek+1st minimal diagnosis isO(n2k), wheren is the number of components. On the practical side, an experimental evaluation indicates that the algorithm can efficiently diagnose devices consisting of a few thousand components. We propose to use a hierarchy of models: first a structural model to compute all minimal diagnoses, then a normal behavior model to find the additional diagnoses if needed, and only then a fault model for their verification. IDA separates model interpretation from the search for minimal diagnoses in the sense that the model interpreter is replaceable. In particular, we show that in some domains it is advantageous to use the constraint logic programming system CLP(ß) instead of a logic programming system like Prolog. More... »

PAGES

297-314

References to SciGraph publications

  • 1993-11. Enhancing design-for-test for active analog filters by using CLP(ℜ) in ANALOG INTEGRATED CIRCUITS AND SIGNAL PROCESSING
  • 1991. Model-Based Analogue Circuit Diagnosis with CLP(R) in VERTEILTE KÜNSTLICHE INTELLIGENZ UND KOOPERATIVES ARBEITEN
  • 1986. Unification in boolean rings in 8TH INTERNATIONAL CONFERENCE ON AUTOMATED DEDUCTION
  • 1987. Foundations of Logic Programming in NONE
  • 1990. Characterizing diagnoses in EXPERT SYSTEMS IN ENGINEERING PRINCIPLES AND APPLICATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01530747

    DOI

    http://dx.doi.org/10.1007/bf01530747

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1044866488


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Information Systems, Technical University of Vienna, and Austrian Research Institute for Artificial Intelligence, Schottengasse 3, A-1010, Vienna, Austria", 
              "id": "http://www.grid.ac/institutes/grid.5329.d", 
              "name": [
                "Department of Information Systems, Technical University of Vienna, and Austrian Research Institute for Artificial Intelligence, Schottengasse 3, A-1010, Vienna, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mozeti\u010d", 
            "givenName": "Igor", 
            "id": "sg:person.01340706300.17", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01340706300.17"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Austrian Research Institute for Artificial Intelligence, and Department of Medical Cybernetics and Artificial Intelligence, University of Vienna, Freyung 6, A-1010, Vienna, Austria", 
              "id": "http://www.grid.ac/institutes/grid.10420.37", 
              "name": [
                "Austrian Research Institute for Artificial Intelligence, and Department of Medical Cybernetics and Artificial Intelligence, University of Vienna, Freyung 6, A-1010, Vienna, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Holzbaur", 
            "givenName": "Christian", 
            "id": "sg:person.015052747435.75", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015052747435.75"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01239075", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023257228", 
              "https://doi.org/10.1007/bf01239075"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-76980-1_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028685768", 
              "https://doi.org/10.1007/978-3-642-76980-1_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-16780-3_115", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006880236", 
              "https://doi.org/10.1007/3-540-16780-3_115"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-53104-1_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024441309", 
              "https://doi.org/10.1007/3-540-53104-1_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-83189-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016029570", 
              "https://doi.org/10.1007/978-3-642-83189-8"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1994-03", 
        "datePublishedReg": "1994-03-01", 
        "description": "We present IDA \u2014 an incrementaldiagnosticalgorithm which computes minimal diagnoses from diagnoses, and not from conflicts. As a consequence of this, and by using different models, one can control the computational complexity. In particular, we show that by using a model of the normal behavior, the worst-case complexity of the algorithm to compute thek+1st minimal diagnosis isO(n2k), wheren is the number of components. On the practical side, an experimental evaluation indicates that the algorithm can efficiently diagnose devices consisting of a few thousand components. We propose to use a hierarchy of models: first a structural model to compute all minimal diagnoses, then a normal behavior model to find the additional diagnoses if needed, and only then a fault model for their verification. IDA separates model interpretation from the search for minimal diagnoses in the sense that the model interpreter is replaceable. In particular, we show that in some domains it is advantageous to use the constraint logic programming system CLP(\u00df) instead of a logic programming system like Prolog.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01530747", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1043955", 
            "issn": [
              "1012-2443", 
              "1573-7470"
            ], 
            "name": "Annals of Mathematics and Artificial Intelligence", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "11"
          }
        ], 
        "keywords": [
          "logic programming system", 
          "minimal diagnosis", 
          "programming system", 
          "constraint logic programming system", 
          "normal behavior model", 
          "model-based diagnosis", 
          "worst-case complexity", 
          "model interpreter", 
          "computational complexity", 
          "experimental evaluation", 
          "behavior model", 
          "normal behavior", 
          "algorithm", 
          "complexity", 
          "practical side", 
          "model interpretation", 
          "fault model", 
          "number of components", 
          "hierarchy of models", 
          "Prolog", 
          "verification", 
          "system", 
          "different models", 
          "model", 
          "interpreters", 
          "search", 
          "hierarchy", 
          "devices", 
          "domain", 
          "wheren", 
          "IDA", 
          "components", 
          "evaluation", 
          "number", 
          "sense", 
          "behavior", 
          "structural model", 
          "interpretation", 
          "conflict", 
          "diagnosis", 
          "side", 
          "consequences", 
          "additional diagnosis"
        ], 
        "name": "Controlling the complexity in model-based diagnosis", 
        "pagination": "297-314", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1044866488"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01530747"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01530747", 
          "https://app.dimensions.ai/details/publication/pub.1044866488"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:19", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_227.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01530747"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf01530747'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf01530747'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01530747'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01530747'


     

    This table displays all metadata directly associated to this object as RDF triples.

    131 TRIPLES      22 PREDICATES      74 URIs      61 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01530747 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Na6a1040e95544155a1b6434de43ea60a
    4 schema:citation sg:pub.10.1007/3-540-16780-3_115
    5 sg:pub.10.1007/3-540-53104-1_27
    6 sg:pub.10.1007/978-3-642-76980-1_31
    7 sg:pub.10.1007/978-3-642-83189-8
    8 sg:pub.10.1007/bf01239075
    9 schema:datePublished 1994-03
    10 schema:datePublishedReg 1994-03-01
    11 schema:description We present IDA — an incrementaldiagnosticalgorithm which computes minimal diagnoses from diagnoses, and not from conflicts. As a consequence of this, and by using different models, one can control the computational complexity. In particular, we show that by using a model of the normal behavior, the worst-case complexity of the algorithm to compute thek+1st minimal diagnosis isO(n2k), wheren is the number of components. On the practical side, an experimental evaluation indicates that the algorithm can efficiently diagnose devices consisting of a few thousand components. We propose to use a hierarchy of models: first a structural model to compute all minimal diagnoses, then a normal behavior model to find the additional diagnoses if needed, and only then a fault model for their verification. IDA separates model interpretation from the search for minimal diagnoses in the sense that the model interpreter is replaceable. In particular, we show that in some domains it is advantageous to use the constraint logic programming system CLP(ß) instead of a logic programming system like Prolog.
    12 schema:genre article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N7239036015544defacb749c3cae28adf
    16 Nc627c25083064fe19274f7444130eb03
    17 sg:journal.1043955
    18 schema:keywords IDA
    19 Prolog
    20 additional diagnosis
    21 algorithm
    22 behavior
    23 behavior model
    24 complexity
    25 components
    26 computational complexity
    27 conflict
    28 consequences
    29 constraint logic programming system
    30 devices
    31 diagnosis
    32 different models
    33 domain
    34 evaluation
    35 experimental evaluation
    36 fault model
    37 hierarchy
    38 hierarchy of models
    39 interpretation
    40 interpreters
    41 logic programming system
    42 minimal diagnosis
    43 model
    44 model interpretation
    45 model interpreter
    46 model-based diagnosis
    47 normal behavior
    48 normal behavior model
    49 number
    50 number of components
    51 practical side
    52 programming system
    53 search
    54 sense
    55 side
    56 structural model
    57 system
    58 verification
    59 wheren
    60 worst-case complexity
    61 schema:name Controlling the complexity in model-based diagnosis
    62 schema:pagination 297-314
    63 schema:productId N22342dc3226d4805a4fa928de8b80357
    64 N61451554b2fe4b4487942d42d244fce3
    65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044866488
    66 https://doi.org/10.1007/bf01530747
    67 schema:sdDatePublished 2022-05-20T07:19
    68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    69 schema:sdPublisher N3b59bd2af3ac495297c9e8cde9c5dd05
    70 schema:url https://doi.org/10.1007/bf01530747
    71 sgo:license sg:explorer/license/
    72 sgo:sdDataset articles
    73 rdf:type schema:ScholarlyArticle
    74 N22342dc3226d4805a4fa928de8b80357 schema:name dimensions_id
    75 schema:value pub.1044866488
    76 rdf:type schema:PropertyValue
    77 N3b59bd2af3ac495297c9e8cde9c5dd05 schema:name Springer Nature - SN SciGraph project
    78 rdf:type schema:Organization
    79 N61451554b2fe4b4487942d42d244fce3 schema:name doi
    80 schema:value 10.1007/bf01530747
    81 rdf:type schema:PropertyValue
    82 N706bb8637ee74ee3b1c6ba612de328b9 rdf:first sg:person.015052747435.75
    83 rdf:rest rdf:nil
    84 N7239036015544defacb749c3cae28adf schema:volumeNumber 11
    85 rdf:type schema:PublicationVolume
    86 Na6a1040e95544155a1b6434de43ea60a rdf:first sg:person.01340706300.17
    87 rdf:rest N706bb8637ee74ee3b1c6ba612de328b9
    88 Nc627c25083064fe19274f7444130eb03 schema:issueNumber 1-4
    89 rdf:type schema:PublicationIssue
    90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Information and Computing Sciences
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Computation Theory and Mathematics
    95 rdf:type schema:DefinedTerm
    96 sg:journal.1043955 schema:issn 1012-2443
    97 1573-7470
    98 schema:name Annals of Mathematics and Artificial Intelligence
    99 schema:publisher Springer Nature
    100 rdf:type schema:Periodical
    101 sg:person.01340706300.17 schema:affiliation grid-institutes:grid.5329.d
    102 schema:familyName Mozetič
    103 schema:givenName Igor
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01340706300.17
    105 rdf:type schema:Person
    106 sg:person.015052747435.75 schema:affiliation grid-institutes:grid.10420.37
    107 schema:familyName Holzbaur
    108 schema:givenName Christian
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015052747435.75
    110 rdf:type schema:Person
    111 sg:pub.10.1007/3-540-16780-3_115 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006880236
    112 https://doi.org/10.1007/3-540-16780-3_115
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/3-540-53104-1_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024441309
    115 https://doi.org/10.1007/3-540-53104-1_27
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/978-3-642-76980-1_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028685768
    118 https://doi.org/10.1007/978-3-642-76980-1_31
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-642-83189-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016029570
    121 https://doi.org/10.1007/978-3-642-83189-8
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/bf01239075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023257228
    124 https://doi.org/10.1007/bf01239075
    125 rdf:type schema:CreativeWork
    126 grid-institutes:grid.10420.37 schema:alternateName Austrian Research Institute for Artificial Intelligence, and Department of Medical Cybernetics and Artificial Intelligence, University of Vienna, Freyung 6, A-1010, Vienna, Austria
    127 schema:name Austrian Research Institute for Artificial Intelligence, and Department of Medical Cybernetics and Artificial Intelligence, University of Vienna, Freyung 6, A-1010, Vienna, Austria
    128 rdf:type schema:Organization
    129 grid-institutes:grid.5329.d schema:alternateName Department of Information Systems, Technical University of Vienna, and Austrian Research Institute for Artificial Intelligence, Schottengasse 3, A-1010, Vienna, Austria
    130 schema:name Department of Information Systems, Technical University of Vienna, and Austrian Research Institute for Artificial Intelligence, Schottengasse 3, A-1010, Vienna, Austria
    131 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...