The problem of rewriting a concept given terminology can informally be stated as follows: given a terminology T (i.e., a set of concept definitions) and a concept description C that does not contain concept names defined in T, can this description be rewritten into a 'related better' description E by using (some of) the names defined in T? In this paper, we first introduce a general framework for the rewriting problem in description logics, and then concentrate on one specific instance of the framework, namely the minimal rewriting problem (where 'better' means shorter, and 'related' means equivalent). We investigate the complexity of the decision problem induced by the minimal rewriting problem for the languages FL₀, ALN, ALE and ALC, and then introduce an algorithm for computing (minimal) rewritings for the languages ALE and ALN. Finally, we sketch other interesting instances of the framework. Our interest for the minimal rewriting problem stems from the fact that algorithms for non-standard inferences, such as computing least common subsumers and matchers, usually produce concept descriptions not containing defined names. Consequently, these descriptions are rather large and hard to read and comprehend. First experiments in a chemical process engineering application show that rewriting can reduce the size of concept descriptions optained as least common subsumers by almost two orders of magnitude. / This is a revised version of LTCS-Report 99-12 containing revised proofs of the technical results. / An abridged version of the original report appeared in the Procedings of the International Conference on Knowledge Representation and Reasoning (KR'2000).
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:78905 |
| Date | 20 May 2022 |
| Creators | Baader, Franz, Küsters, Ralf, 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.0024 seconds