Moreover, these modifications do not change the complexity of the algorithm. Thus, partial and total attributes behave very similarly from the subsumption point of view.

Second, and this is the more surprising result of this paper, the distinction between partial and total attributes does have a significant impact on the problem of computing the lcs. Previous results on sublanguages of CLASSIC show that if partial attributes are used, the lcs of two concept descriptions always exists, and can be computed in polynomial time.

If, however, only total attributes are involved, the situation is very different. The lcs need no longer even exist, and in case it exists its size may grow exponential in the size of the given concept descriptions. Nevertheless, the existence of the lcs of two concept descriptions can be decided in polynomial time.

Specifically, in previous work (Cohen et al., 1992; Cohen & Hirsh, 1994a; Frazier &
Pitt, 1996) concerning the lcs computation in CLASSIC, constructions and proofs have been made without realizing the difference between the two types of attributes. Without going into details here, the main problem for lcs is that merely finite graphs have been employed, making the constructions applicable only for the partial attribute case. In addition to fixing these problems, this paper also presents the proper handling of inconsistent concepts in the lcs algorithm for CLASSIC presented by Frazier and Pitt (1996).

Although our results about subsumption are not as intriguing, the proofs to show the results on the lcs make extensive use of the corresponding subsumption algorithms, which is one reason we present them beforehand in this paper.

Returning to the general differences between the cases of total and partial attributes, one could say that the fundamental cause for the differences lies in the same-as constructor, whose semantics normally requires that (i) the two chains of attributes each have a value, and (ii) that these values coincide. In the case of total attributes, same-as obeys the principle

## C ⊆ U ↓ V Implies C ⊆ U ⊙ W ↓ V ⊙ W

where u,v, and w are sequences of total attributes, e.g., (madeBy omodel), because condition
(i) is ensured by the total aspect of all the attributes. In the case of partial attributes, the above implication does not hold, because w, and hence u ow, is no longer guaranteed to have a value, implying that the same-as restriction may not hold.  Clearly, this implication affects the results of subsumption. As far as les is concerned, a certain graph (representing the les of the two given concepts) may be infinite in the case of total attributes, thus jeopardizing the existence of the lcs.

The more general significance of our result is that knowledge representation language designers and users need to explicitly check at the beginning whether they deal with total or partial attributes because the choice can have significant effects. Although in some situations total attributes are convenient, to guarantee the existence of attributes without having to resort to number restrictions, our results show that they can have drawbacks.

All things considered, requiring all attributes to be total appears to be less desirable. Concerning CLASSIC, the technical results in this paper support the use of partial attributes because these ensure the existence of the lcs and its computation in polynomial time as well as the efficient decision of subsumption. Moreover, the current implementation of the CLASSIC subsumption algorithm does not require major anges in order to handle partial attributes.