Skip to main content
SpringerLink
Log in

Structural Subsumption and Least Common Subsumers in a Description Logic with Existential and Number Restrictions

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

The least common subsumer (lcs) of a set of concept descriptions is the most specific concept description that subsumes all of the concept descriptions in the given set. By computing the lcs, commonalities between concept descriptions can be made explicit. This is an important inference task useful in several applications, including, for instance, the bottom-up construction of description logic knowledge bases.

Previous work on the lcs has concentrated on description logics that either allow for number restrictions or for existential restrictions. Many applications, however, require to combine these constructors. In this work, we present an algorithm for computing the lcs in the description logic ALEN which comprises both constructors—number and existential restrictions—as well as concept conjunction, primitive negation, and value restrictions. To prove correctness of our lcs algorithm, we develop a structural characterization of subsumption in ALEN.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Baader, F., ‘Using Automata Theory for Characterizing the Semantics of Terminological Cycles’. Annals of Mathematics and Artificial Intelligence 18(2–4):175–219, 1996.

    Article  Google Scholar 

  2. Baader, F., ‘Computing the least common subsumer in the description logic EL w.r.t. terminological cycles with descriptive semantics’, in Proceedings of the 11th International Conference on Conceptual Structures (ICCS 2003), vol. 2746 of Lecture Notes in Artificial Intelligence, Springer-Verlag, 2003, pp. 117–130.

  3. Baader, F., ‘Least common subsumers and most specific concepts in a description logic with existential restrictions and terminological cycles’, in G. Gottlob and T. Walsh, (eds.), Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI 2003), Morgan Kaufmann, 2003, pp. 319–324. Structural Subsumption and Least Common Subsumers. 257

  4. Baader, F., D. Calvanese, D. McGuinness, D. Nardi, and P. F. Patel- Schneider, (eds.), The Description Logic Handbook: Theory, Implementation, and Applications, Cambridge University Press, 2003.

  5. Baader, F., and R. Küsters, ‘Computing the Least Common Subsumer and the Most Specific Concept in the Presence of Cyclic ALN -Concept Descriptions’, in O. Herzog and A. Günter, (eds.), Proceedings of the 22nd Annual German Conference on Artificial Intelligence, KI-98, volume 1504 of Lecture Notes in Computer Science, Bremen, Germany, Springer–Verlag, 1998, pp. 129–140,

  6. Baader, F., R. Küsters, A. Borgida, and D. McGuinness, ‘Matching in Description Logics’, Journal of Logic and Computation 9(3):411–447, 1999.

    Article  Google Scholar 

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

  8. Baader, F., B. Sertkaya, and A.-Y. Turhan, ‘Computing the least common subsumer w.r.t. a background terminology' in José Júlio Alferes and João Alexandre Leite, (eds.), Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004), volume 3229 of Lecture Notes in Computer Science, Springer-Verlag, 2004, pp. 400–412.

  9. Baader, F., and A.-Y. Turhan, ‘On the Problem of Computing Small Representations of Least Common Subsumers’, in Proceedings of the 25th German Conference on Artificial Intelligence (KI 2002), Lecture Notes in Artificial Intelligence, Aachen, Germany, Springer–Verlag, 2002, pp. 99–113.

  10. Brandt, S., R. Küsters, and A.-Y. Turhan, ‘Approximating ALEN Concept Descriptions’, in Proceedings of the International Workshop on Description Logics 2002 (DL 2002), 2002. Available from http://sunsite.informatik.rwthaachen. de/Publications/CEUR-WS/.

  11. Brandt, S., R. Küsters, and A.-Y. Turhan, ‘Approximation and Difierence in Description Logics’, in D. Fensel, F. Guinchiglia, D. McGuiness, and M. A. Williams, (eds.), Proceedings of the Eight International Conference on Knowledge Representation and Reasoning (KR2002), Morgan Kaufmann Publishers, 2002, pp. 203–214.

  12. Brandt, S., and A.-Y. Turhan, ‘Using Non-standard Inferences in Description Logics — what does it buy me?’, in Proceedings of the KI-2001 Workshop on Applications of Description Logics (KIDLWS'01), number 44 in CEUR-WS, Vienna, Austria, September 2001. RWTH Aachen. Proceedings online available from http://SunSITE.Informatik.RWTH-Aachen.DE/Publications/CEUR-WS/Vol-44/.

  13. Calvanese, D. and G. De Giacomo, Expressive Description Logics. In, 2003, pp. 178–218.

  14. Cohen, W.W., and H. Hirsh, ‘Learnability of description logics with equality constraints’, Machine Learning 17(2/3):169–199, 1994.

    Google Scholar 

  15. Cohen, W. W., and H. Hirsh, ‘Learning the CLASSIC Description Logic: Theoretical and Experimental Results’, in J. Doyle, E. Sandewall, and P. Torasso, (eds.), Proceedings of the Fourth International Conference on Principles of Knowledge Representation and Reasoning (KR'94), Bonn, Germany, Morgan Kaufmann Publishers, 1994, pp. 121–133.

  16. Cohen, W.W., A. Borgida, and H. Hirsh, ‘Computing Least Common Subsumers in Description Logics’, in William Swartout, (ed.), Proceedings of the 10th National Conference on Artificial Intelligence, San Jose, CA, MIT Press, July 1992. pp. 754–760.

  17. Donini, F.M., Complexity of Reasoning, in [4], 2003, pp. 96–136.

  18. Frazier, M. and L. Pitt, ‘Classic Learning’, Machine Learning Journal, 25:151–193, 1996.

    Article  Google Scholar 

  19. Haarslev, V., and R. Möller, ‘RACER systemdescription’, in R. Gor, A. Leitsch, and T. Nipkow, (eds.), First International Joint Conference on Automated Reasoning (IJCAR 2001), vol. 2083 of Lecture Notes in Computer Science, Springer, 2001, pp. 701–706.

  20. Hemaspaandra, E., ‘The complexity of poor man's logic’, in J. Gerbrandy, M. Marx, M. de Rijke, and Y. Venema, (eds.), Essays Dedicated to Johan van Benthem on the Occasion of his 50th birthday, Amsterdam University Press, 1999.

  21. Hollunder, B., and F. Baader, ‘Qualifying Number Restrictions in Concept Languages’, in J.F. Allen, R. Fikes, and E. Sandewall, (eds.), Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, KR-91, Boston (USA), 1991. Morgan Kaufmann Publishers, pp. 335–346.

  22. Horrocks, I., ‘The FaCT system’, in Proceedings of the International Conference on Automated Reasoning with Analytic Tableaux and Related Methods (Tableaux'98), vol. 1397 of Lecture Notes in Artificial Intelligence, Berlin, Springer-Verlag, 1998, pp. 307–312.

  23. Horrocks, I., ‘Using an Expressive Description Logic: FaCT or Fiction?’, in A.G. Cohn, L. Schubert, and S.C. Shapiro, (eds.), Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98), Trento, Italy, Morgan Kaufmann Publishers, 1998, pp. 636–647.

  24. Horrocks, I., ‘Implementation and optimization techniques’, in 2003, pp. 306–346.

  25. Horrocks, I., P.F. Patel-Schneider, and F. van Harmelen, From SHIQ and RDF to OWL: The making of a web ontology language. Journal of Web Semantics 1(1):7–26, 2003.

    Google Scholar 

  26. Küsters, R., Non-Standard Inferences in Description Logics, Ph.D. thesis, volume 2100 of Lecture Notes in Artificial Intelligence, Springer-Verlag, 2001.

  27. Küsters, R., and A. Borgida, What's in an Attribute? Consequences for the Least Common Subsumer, Journal of Artificial Intelligence Research 14:167–203, 2001. Structural Subsumption and Least Common Subsumers 259

    Google Scholar 

  28. Küsters, R., and R. Molitor, ‘Computing Least Common Subsumers in ALEN ’, in B. Nebel, (ed.), Proceedings of the 17th International Joint Conference on Arti- ficial Intelligence (IJCAI 2001), Seattle, USA, Morgan Kaufmann Publishers, 2001, pp. 219–224.

  29. Mantay, T., ‘Computing Least Common Subsumers in Expressive Description Logics’, in N.Y. Foo, (ed.), Advanced Topics in Artificial Intelligence, 12th Australian Joint Conference on Artificial Intelligence (AI'99), vol. 1747 of Lecture Notes in Computer Science, Sydney, Australia, Springer-Verlag, 1999, pp. 218–230.

  30. Mantay, T., R. Möller, and A. Kaplunova, ‘Computing Probabilistic Least Common Subsumers in Description Logics’, in W. Burgard, T. Christaller, and A.B. Cremers, (eds.), Advances in Artificial Intelligence, 23rd Annual German Conference on Artificial Intelligence (KI-99), number 1701 in Lecture Notes in Computer Science, Bonn, Germany, Springer–Verlag, 1999, pp. 89–100.

  31. Möller, R., and V. Haarslev, Description Logic Systems, in [4], 2003, pp. 282–305.

  32. Möller, R., V. Haarslev, and B. Neumann, ‘Semantics-Based Information Retrieval’, in Proceedings of the International Conference on Information Technology and Knowledge Systems (IT&KNOWS-98), Vienna, Budapest, 1998, pp. 48–61.

  33. Nebel, B., ‘Terminological cycles: Semantics and computational properties’, in J. Sowa, (ed.), Formal Aspects of Semantic Networks, Morgan Kaufmann Publishers, San Mateo, 1991, pp. 331–361.

  34. Sattler, U., Terminological Knowledge Representation Systems in a Process Engineering Application, PhD thesis, LuFG Theoretical Computer Science, RWTHAachen, Germany, 1998.

  35. Turhan, A.-Y., and C. Kissig, ‘Sonic—non-standard inferences go oiled’, in D. Basin and M. Rusinowitch, (eds.), Proceedings of the 2nd International Joint Conference on Automated Reasoning (IJCAR 2004), vol. 3097 of Lecture Notes in Artificial Intelligence, Springer, 2004, pp. 321–325.

  36. von Wedel, L., and W. Marquardt, ‘ROME: A Repository to Support the Integration of Models over the Lifecycle of Model-based Engineering Processes’, in Proceedings of the 10th European Symposium on Computer Aided Process Engineering (ESCAPE-10), 2000.

Download references

Author information

Authors and Affiliations

  1. Christian-Albrechts-Universität zu Kiel, Institut für Informatik, 24098, Kiel, Germany

    Ralf Küsters

  2. Swiss Life, P.O. Box, General-Guisan-Quai 40, CH-8022, Zürich, Switzerland

    Ralf Molitor

Authors
  1. Ralf Küsters
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ralf Molitor
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ralf Küsters.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Küsters, R., Molitor, R. Structural Subsumption and Least Common Subsumers in a Description Logic with Existential and Number Restrictions. Stud Logica 81, 227–259 (2005). https://doi.org/10.1007/s11225-005-3705-5

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11225-005-3705-5

Keywords

Search

Navigation