Ontology type: schema:ScholarlyArticle
1994-03
AUTHORSIgor Mozetič, Christian Holzbaur
ABSTRACTWe 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... »
PAGES297-314
http://scigraph.springernature.com/pub.10.1007/bf01530747
DOIhttp://dx.doi.org/10.1007/bf01530747
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1044866488
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
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 |