As an aside, we note that it has been pointed out by Cohen et al. (1992) that concept descriptions in S correspond to a finitely generated right congruence. Furthermore, in this context the lcs of two concept descriptions is the intersection of right congruences. Thus, the results presented in this paper also show that the intersection of finitely generated right congruences is not always a finitely generated right congruence, and that there is a polynomial algorithm for deciding this question. Finally, if the intersection can be finitely generated, then the generating system may be exponential and can be computed with an exponential time algorithm in the size of the generating systems of the given right cngruences.

The results in this paper therefore lay out the scope of the effect of making attributes be total or partial functions in a description logic that supports the same-as constructor.

Moreover, we correct some problems and extend results in the previous literature.

We believe that the disparity between the results in the two cases should serve as a warning to other researchers in knowledge representation and reasoning, concerning the importance of explicitly considering the difference between total and partial attributes.

## Acknowledgments

The authors wish to thank the anonymous reviewers for their helpful comments. This research was supported in part by NSF Grant IRI-9619979. It was carried out while the first author was at the Rutgers University and the RWTH Aachen.

## References

Artale, A., Franconi, E., Guarino, N., & Pazzi, L. (1996). Part-Whole Relations in Object-
Centered Systems: An Overview. Data & Knowledge Engineering, 20 (3), 347–383.

Baader, F. (1996). A Formal Definition for the Expressive Power of Terminological Knowledge Representation Languages. Journal of Logic and Computation, 6 (1), 33–54.

Baader, F., & Küsters, R. (1998). Computing the Least Common Subsumer and the Most Specific Concept in the Presence of Cyclic ALN -Concept Descriptions. In Herzog, O, & Günter, A. (Eds.), Proceedings of the 22nd Annual German Conference on Artificial Intelligence, KI-98, Vol. 1504 of Lecture Notes in Computer Science, pp.

129–140 Bremen, Germany, Springer–Verlag.

Baader, F., Küsters, R., & Molitor, R. (1999). Computing Least Common Subsumers in Description Logics with Existential Restrictions. In Dean, T. (Ed.), Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI'99), pp. 96–101 Stockholm, Sweden. Morgan Kaufmann Publishers.

Baader, F., & Sattler, U. (2000). Tableaux Algorithms for Description Logics. In Proceedings of the International Conference on Automated Reasoning with Analytic Tableaux and Related Methods (TABLEAUX 2000), Vol. 1847 of Lecture Notes in Artifical Intelligence, pp. 1-18 University of St. Andrews, Scotland.