The problem of rewriting a concept given a 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 FL0, 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 obtained as least common subsumers by almost two orders of magnitude. / Please download the revised version LTCS-00-04 containing revised proofs of the technical results. / An abridged version of this report appeared in the Proceedings of the International Conference on Knowledge Representation and Reasoning (KR'2000).

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).