Aus der Einleitung:
„In this paper, we reuse the representation formalism `description graph' in order to characterize subsumption of ALN-concepts. The description logic ALN allows for conjunction, valuerestrictions, number restrictions, and primitive negation. Since Classic allows for more constructors than ALN, e.g., equality restrictions an attribute chains by the constructor SAME-AS,we can confine the notion of description graphs from [BP94].
On the other hand, ALN explicitly allows for primitive negation which yields another possibility { besides conflicting number restrictions { to express inconsistency. Thus, we have to modify the notion of canonical description graphs in order to cope with inconsistent concepts in the structural characterization of subsumption.
It turns out that the description graphs obtained from ALN-concepts are in fact trees. A canonical graph is a deterministic tree. The conditions required by the structural characterization of subsumption on these trees can be tested by an eficient algorithm, i.e., we obtain an algorithm deciding subsumption of C and D in time polynomial in the size of C and D.
The report is structured as follows. In the preliminaries, we define syntax and semantics of the description logic ALN as well as the inference problem of subsumption. In Section 3, we introduce description graphs, the data structure our structural subsumption algorithm is working on.
Besides syntax and semantics also an algorithm for translating ALN-concepts into description graphs is given.
Thereafter, we present the main result of this report in Section 6, a characterization of subsumption of ALN-concepts by a structural comparison of corresponding description graphs. Furthermore, a structural subsumption algorithm can be found in Section 6.2.
In the last section we summarize our results and give an outlook to further applications of structural subsumption in terminological knowledge representation systems.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:78822 |
| Date | 19 May 2022 |
| Creators | Molitor, Ralf |
| Publisher | Aachen University of Technology |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/acceptedVersion, doc-type:report, info:eu-repo/semantics/report, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | urn:nbn:de:bsz:14-qucosa2-785040, qucosa:78504 |
Page generated in 0.0105 seconds