Abstract
Description Logics (DLs) are a well-investigated family of logic-based knowledge representation formalisms, which can be used to represent the conceptual knowledge of an application domain in a structured and formally well-understood way. They are employed in various application domains, such as natural language processing, configuration, and databases, but their most notable success so far is the adoption of the DL-based language OWL as standard ontology language for the semantic web.
This article concentrates on the problem of designing reasoning procedures for DLs. After a short introduction and a brief overview of the research in this area of the last 20 years, it will on the one hand present approaches for reasoning in expressive DLs, which are the foundation for reasoning in the Web ontology language OWL DL. On the other hand, it will consider tractable reasoning in the more light-weight DL \(\mathcal{EL}\), which is employed in bio-medical ontologies, and which is the foundation for the OWL 2 profile OWL 2 EL.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Acciarri, A., Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Palmieri, M., Rosati, R.: Quonto: Querying ontologies. In: Veloso, M.M., Kambhampati, S. (eds.) Proc. of the 20th Nat. Conf. on Artificial Intelligence (AAAI 2005), pp. 1670–1671. AAAI Press/The MIT Press (2005)
Areces, C., de Rijke, M., de Nivelle, H.: Resolution in modal, description and hybrid logic. J. of Logic and Computation 11(5), 717–736 (2001)
Baader., F.: Augmenting concept languages by transitive closure of roles: An alternative to terminological cycles. In: Proc. of the 12th Int. Joint Conf. on Artificial Intelligence, IJCAI 1991 (1991)
Baader, F.: Using automata theory for characterizing the semantics of terminological cycles. Ann. of Mathematics and Artificial Intelligence 18, 175–219 (1996)
Baader, F.: Description logic terminology. In: [11], pp. 485–495 (2003)
Baader, F.: Terminological cycles in a description logic with existential restrictions. In: Gottlob, G., Walsh, T. (eds.) Proc. of the 18th Int. Joint Conf. on Artificial Intelligence (IJCAI 2003), Acapulco, Mexico, pp. 325–330. Morgan Kaufmann, Los Altos (2003)
Baader, F., Brandt, S., Lutz, C.: Pushing the \(\mathcal{EL}\) envelope. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI 2005), Edinburgh, UK, pp. 364–369. Morgan Kaufmann, Los Altos (2005)
Baader, F., Brandt, S., Lutz, C.: Pushing the \(\mathcal{EL}\) envelope further. In: Clark, K., Patel-Schneider, P.F. (eds.) Proceedings of the Fifth International Workshop on OWL: Experiences and Directions (OWLED 2008), Karlsruhe, Germany (2008)
Baader, F., Buchheit, M., Hollunder, B.: Cardinality restrictions on concepts. Artificial Intelligence 88(1–2), 195–213 (1996)
Baader, F., Bürckert, H.-J., Nebel, B., Nutt, W., Smolka, G.: On the expressivity of feature logics with negation, functional uncertainty, and sort equations. J. of Logic, Language and Information 2, 1–18 (1993)
Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, Cambridge (2003)
Baader, F., Franconi, E., Hollunder, B., Nebel, B., Profitlich, H.-J.: An empirical analysis of optimization techniques for terminological representation systems or: Making KRIS get a move on. Applied Artificial Intelligence. Special Issue on Knowledge Base Management 4, 109–132 (1994)
Baader, F., Hladik, J., Lutz, C., Wolter, F.: From tableaux to automata for description logics. Fundamenta Informaticae 57(2–4), 247–279 (2003)
Baader, F., Hollunder, B.: A terminological knowledge representation system with complete inference algorithm. In: Boley, H., Richter, M.M. (eds.) PDK 1991. LNCS (LNAI), vol. 567, pp. 67–86. Springer, Heidelberg (1991)
Baader, F., Horrocks, I., Sattler, U.: Description logics. In: Staab, S., Studer, R. (eds.) Handbook on Ontologies. International Handbooks in Information Systems, pp. 3–28. Springer, Berlin (2003)
Baader, F., Horrocks, I., Sattler, U.: Description logics. In: van Harmelen, F., Lifschitz, V., Porter, B. (eds.) Handbook of Knowledge Representation, pp. 135–179. Elsevier, Amsterdam (2007)
Baader, F., Küsters, R., Molitor, R.: Structural subsumption considered from an automata theoretic point of view. In: Proc. of the 1998 Description Logic Workshop (DL 1998). CEUR Electronic Workshop Proceedings (1998), http://ceur-ws.org/Vol-11/
Baader, F., Lutz, C.: Description logic. In: Blackburn, P., van Benthem, J., Wolter, F. (eds.) The Handbook of Modal Logic, pp. 757–820. Elsevier, Amsterdam (2006)
Baader, F., Lutz, C., Suntisrivaraporn, B.: CEL—a polynomial-time reasoner for life science ontologies. In: Furbach, U., Shankar, N. (eds.) IJCAR 2006. LNCS, vol. 4130, pp. 287–291. Springer, Heidelberg (2006)
Baader, F., Narendran, P.: Unification of concepts terms in description logics. J. of Symbolic Computation 31(3), 277–305 (2001)
Baader, F., Nutt, W.: Basic description logics. In: [11], pp. 43–95 (2003)
Baader, F., Peñaloza, R., Suntisrivaraporn, B.: Pinpointing in the description logic \({{\mathcal{EL}}^+}\). In: Hertzberg, J., Beetz, M., Englert, R. (eds.) KI 2007. LNCS, vol. 4667, pp. 52–67. Springer, Heidelberg (2007)
Baader, F., Sattler, U.: An overview of tableau algorithms for description logics. Studia Logica 69, 5–40 (2001)
Baader, F., Suntisrivaraporn, B.: Debugging SNOMED CT using axiom pinpointing in the description logic \(\mathcal{EL}^+\). In: Proceedings of the International Conference on Representing and Sharing Knowledge Using SNOMED (KR-MED 2008), Phoenix, Arizona (2008)
Baader, F., Tobies, S.: The inverse method implements the automata approach for modal satisfiability. In: Goré, R.P., Leitsch, A., Nipkow, T. (eds.) IJCAR 2001. LNCS, vol. 2083, pp. 92–106. Springer, Heidelberg (2001)
Bernholtz, O., Grumberg, O.: Branching time temporal logic and amorphous tree automata. In: Best, E. (ed.) CONCUR 1993. LNCS, vol. 715, pp. 262–277. Springer, Heidelberg (1993)
Blackburn, P., de Rijke, M., de Venema, Y.: Modal Logic. Cambridge Tracts in Theoretical Computer Science, vol. 53. Cambridge University Press, Cambridge (2001)
Borgida, A.: On the relative expressiveness of description logics and predicate logics. Artificial Intelligence 82(1–2), 353–367 (1996)
Brachman, R.J.: “Reducing” CLASSIC to practice: Knowledge representation meets reality. In: Proc. of the 3rd Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 1992), pp. 247–258. Morgan Kaufmann, Los Altos (1992)
Brachman, R.J., Levesque, H.J.: The tractability of subsumption in frame-based description languages. In: Proc. of the 4th Nat. Conf. on Artificial Intelligence (AAAI 1984), pp. 34–37 (1984)
Brachman, R.J., Levesque, H.J.: Readings in Knowledge Representation. Morgan Kaufmann, Los Altos (1985)
Brachman, R.J., Nardi, D.: An introduction to description logics. In: [11], pp. 1–40 (2003)
Brachman, R.J., Schmolze, J.G.: An overview of the KL-ONE knowledge representation system. Cognitive Science 9(2), 171–216 (1985)
Brandt., S.: Polynomial time reasoning in a description logic with existential restrictions, GCI axioms, and—what else? In: de Mántaras, R.L., Saitta, L. (eds.) Proc. of the 16th Eur. Conf. on Artificial Intelligence (ECAI 2004), pp. 298–302 (2004)
Bresciani, P., Franconi, E., Tessaris, S.: Implementing and testing expressive description logics: Preliminary report. In: Proc. of the 1995 Description Logic Workshop (DL 1995), pp. 131–139 (1995)
Buchheit, M., Donini, F.M., Nutt, W., Schaerf, A.: A refined architecture for terminological systems: Terminology = schema + views. Artificial Intelligence 99(2), 209–260 (1998)
Buchheit, M., Donini, F.M., Schaerf, A.: Decidable reasoning in terminological knowledge representation systems. J. of Artificial Intelligence Research 1, 109–138 (1993)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: DL-Lite: Tractable description logics for ontologies. In: Veloso, M.M., Kambhampati, S. (eds.) Proc. of the 20th Nat. Conf. on Artificial Intelligence (AAAI 2005), pp. 602–607. AAAI Press/The MIT Press (2005)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. of Automated Reasoning 39(3), 385–429 (2007)
Calvanese, D., De Giacomo, G., Lenzerini, M.: On the decidability of query containment under constraints. In: Proc. of the 17th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS 1998), pp. 149–158 (1998)
Calvanese, D., De Giacomo, G., Lenzerini, M.: Reasoning in expressive description logics with fixpoints based on automata on infinite trees. In: Proc. of the 16th Int. Joint Conf. on Artificial Intelligence (IJCAI 1999), pp. 84–89 (1999)
Calvanese, D., De Giacomo, G., Lenzerini, M., Nardi, D., Rosati, R.: Description logic framework for information integration. In: Proc. of the 6th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 1998), pp. 2–13 (1998)
De Giacomo, G.: Decidability of Class-Based Knowledge Representation Formalisms. PhD thesis, Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza” (1995)
De Giacomo, G., Lenzerini, M.: Boosting the correspondence between description logics and propositional dynamic logics. In: Proc. of the 12th Nat. Conf. on Artificial Intelligence (AAAI 1994), pp. 205–212. AAAI Press/The MIT Press (1994)
De Giacomo, G., Lenzerini, M.: Concept language with number restrictions and fixpoints, and its relationship with μ-calculus. In: Proc. of the 11th Eur. Conf. on Artificial Intelligence (ECAI 1994), pp. 411–415 (1994)
De Giacomo, G., Lenzerini, M.: TBox and ABox reasoning in expressive description logics. In: Aiello, L.C., Doyle, J., Shapiro, S.C. (eds.) ECAI-WS 1992, pp. 316–327. Morgan Kaufmann, Los Altos (1996)
Donini, F.: Complexity of reasoning. In: [11], pp. 96–136 (2003)
Donini, F., Massacci, F.: EXPTIME tableaux for \(\mathcal{ALC}\). Acta Informatica 124(1), 87–138 (2000)
Donini, F.M., Hollunder, B., Lenzerini, M., Spaccamela, A.M., Nardi, D., Nutt, W.: The complexity of existential quantification in concept languages. Artificial Intelligence 2–3, 309–327 (1992)
Donini, F.M., Lenzerini, M., Nardi, D., Nutt, W.: The complexity of concept languages. In: Allen, J., Fikes, R., Sandewall, E. (eds.) Proc. of the 2nd Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 1991), pp. 151–162. Morgan Kaufmann, Los Altos (1991)
Donini, F.M., Lenzerini, M., Nardi, D., Nutt, W.: Tractable concept languages. In: Proc. of the 12th Int. Joint Conf. on Artificial Intelligence (IJCAI 1991), Sydney, Australia, pp. 458–463 (1991)
Fischer, M.J., Ladner, R.E.: Propositional dynamic logic of regular programs. J. of Computer and System Sciences 18, 194–211 (1979)
Fitting, M.: Tableau methods of proof for modal logics. Notre Dame J. of Formal Logic 13(2), 237–247 (1972)
Garey, M.R., Johnson, D.S.: Computers and Intractability — A guide to NP-completeness. W. H. Freeman and Company, San Francisco (1979)
Glimm, B., Horrocks, I., Lutz, C., Sattler, U.: Conjunctive query answering for the description logic \({\mathcal{SHIQ}}\). In: Veloso, M.M. (ed.) Proc. of the 20th Int. Joint Conf. on Artificial Intelligence (IJCAI 2007), Hyderabad, India, pp. 399–404 (2007)
Goré, R., Nguyen, L.A.: Exptime tableaux for \(\mathcal{ALC}\) using sound global caching. In: Proc. of the 2007 Description Logic Workshop (DL 2007), Brixen-Bressanone, Italy (2007)
Grädel, E.: Guarded fragments of first-order logic: A perspective for new description logics? In: Proc. of the 1998 Description Logic Workshop (DL 1998). CEUR Electronic Workshop Proceedings (1998), http://ceur-ws.org/Vol-11/
Grädel, E.: On the restraining power of guards. J. of Symbolic Logic 64, 1719–1742 (1999)
Grädel, E., Kolaitis, P.G., Vardi, M.Y.: On the decision problem for two-variable first-order logic. Bulletin of Symbolic Logic 3(1), 53–69 (1997)
Grau, B.C., Horrocks, I., Kazakov, Y., Sattler, U.: A logical framework for modularity of ontologies. In: Veloso, M.M. (ed.) Proc. of the 20th Int. Joint Conf. on Artificial Intelligence (IJCAI 2007), Hyderabad, India, pp. 298–303 (2007)
Haarslev, V., Möller, R.: RACE system description. In: Proc. of the 1999 Description Logic Workshop (DL 1999). CEUR Electronic Workshop Proceedings, pp. 130–132 (1999), http://ceur-ws.org/Vol-22/
Haarslev, V., Möller, R.: RACER system description. In: Goré, R.P., Leitsch, A., Nipkow, T. (eds.) IJCAR 2001. LNCS (LNAI), vol. 2083, pp. 701–706. Springer, Heidelberg (2001)
Hofmann, M.: Proof-theoretic approach to description-logic. In: Panangaden, P. (ed.) Proc. of the 20th IEEE Symp. on Logic in Computer Science (LICS 2005), pp. 229–237. IEEE Computer Society Press, Los Alamitos (2005)
Hollunder, B.: Consistency checking reduced to satisfiability of concepts in terminological systems. Ann. of Mathematics and Artificial Intelligence 18(2–4), 133–157 (1996)
Hollunder, B., Baader, F.: Qualifying number restrictions in concept languages. In: Proc. of the 2nd Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 1991), pp. 335–346 (1991)
Hollunder, B., Nutt, W., Schmidt-Schauß, M.: Subsumption algorithms for concept description languages. In: Proc. of the 9th Eur. Conf. on Artificial Intelligence (ECAI 1990), London, United Kingdom, Pitman, pp. 348–353 (1990)
Horrocks, I.: Using an expressive description logic: FaCT or fiction? In: Proc. of the 6th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 1998), pp. 636–647 (1998)
Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible \({\mathcal{SROIQ}}\). In: Doherty, P., Mylopoulos, J., Welty, C.A. (eds.) Proc. of the 10th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 2006), Lake District, UK, pp. 57–67. AAAI Press/The MIT Press (2006)
Horrocks, I., Patel-Schneider, P.F., van Harmelen, F.: From SHIQ and RDF to OWL: The making of a web ontology language. Journal of Web Semantics 1(1), 7–26 (2003)
Horrocks, I., Sattler, U.: A description logic with transitive and inverse roles and role hierarchies. J. of Logic and Computation 9(3), 385–410 (1999)
Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for expressive description logics. In: Ganzinger, H., McAllester, D., Voronkov, A. (eds.) LPAR 1999. LNCS (LNAI), vol. 1705, pp. 161–180. Springer, Heidelberg (1999)
Hustadt, U., Motik, B., Sattler, U.: Reducing SHIQ-description logic to disjunctive datalog programs. In: Dubois, D., Welty, C.A., Williams, M.-A. (eds.) Proc. of the 9th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 2004), pp. 152–162. Morgan Kaufmann, Los Altos (2004)
Hustadt, U., Schmidt., R.A.: On the relation of resolution and tableaux proof systems for description logics. In: Proc. of the 16th Int. Joint Conf. on Artificial Intelligence (IJCAI 1999), pp. 110–117 (1999)
Hustadt, U., Schmidt, R.A.: Issues of decidability for description logics in the framework of resolution. In: Caferra, R., Salzer, G. (eds.) FTP 1998. LNCS (LNAI), vol. 1761, pp. 191–205. Springer, Heidelberg (2000)
Hustadt, U., Schmidt, R.A., Georgieva, L.: A survey of decidable first-order fragments and description logics. Journal of Relational Methods in Computer Science 1, 251–276 (2004)
Janin, D., Walukiewicz, I.: Automata for the modal mu-calculus and related results. In: Hájek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol. 969, pp. 552–562. Springer, Heidelberg (1995)
Kazakov, Y., de Nivelle, H.: Subsumption of concepts in \(\mathcal{FL}_0\) for (cyclic) terminologies with respect to descriptive semantics is PSPACE-complete. In: Proc. of the 2003 Description Logic Workshop (DL 2003). CEUR Electronic Workshop Proceedings (2003), http://CEUR-WS.org/Vol-81/
Kazakov, Y., Motik, B.: A resolution-based decision procedure for \(\mathcal{SHOIQ}\). In: Furbach, U., Shankar, N. (eds.) IJCAR 2006. LNCS, vol. 4130, pp. 662–677. Springer, Heidelberg (2006)
Konev, B., Lutz, C., Walther, D., Wolter, F.: Semantic modularity and module extraction in description logics. In: Ghallab, M., Spyropoulos, C.D., Fakotakis, N., Avouris, N. (eds.) Proc. of the 18th Eur. Conf. on Artificial Intelligence (ECAI 2008), pp. 55–59. IOS Press, Amsterdam (2008)
Kurtonina, N., de Rijke, M.: Expressiveness of concept expressions in first-order description logics. Artificial Intelligence 107(2), 303–333 (1999)
Lawley., M.: Exploiting fast classification of SNOMED CT for query and integration of health data. In: Cornet, R., Spackman, K. (eds.) Proc. of the 3rd Int. Conf. on Knowledge Representation in Medicine (KR-MED 2008), Phoenix, Arizona, USA (2008)
Levesque, H.J., Brachman, R.J.: Expressiveness and tractability in knowledge representation and reasoning. Computational Intelligence 3, 78–93 (1987)
Lutz., C.: Complexity of terminological reasoning revisited. In: Ganzinger, H., McAllester, D., Voronkov, A. (eds.) LPAR 1999. LNCS (LNAI), vol. 1705, pp. 181–200. Springer, Heidelberg (1999)
Lutz, C.: Interval-based temporal reasoning with general TBoxes. In: Proc. of the 17th Int. Joint Conf. on Artificial Intelligence (IJCAI 2001), pp. 89–94 (2001)
Lutz, C.: The complexity of conjunctive query answering in expressive description logics. In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS, vol. 5195, pp. 179–193. Springer, Heidelberg (2008)
Lutz, C., Sattler, U.: Mary likes all cats. In: Proc. of the 2000 Description Logic Workshop (DL 2000). CEUR Electronic Workshop Proceedings, pp. 213–226 (2000), http://ceur-ws.org/Vol-33/
MacGregor, R.: The evolving technology of classification-based knowledge representation systems. In: Sowa, J.F. (ed.) Principles of Semantic Networks, pp. 385–400. Morgan Kaufmann, Los Altos (1991)
Mays, E., Dionne, R., Weida, R.: K-REP system overview. SIGART Bull. 2(3) (1991)
Meyer, T., Lee, K., Booth, R., Pan, J.Z.: Finding maximally satisfiable terminologies for the description logic \(\mathcal{{ALC}}\). In: Proc. of the 21st Nat. Conf. on Artificial Intelligence (AAAI 2006), AAAI Press/The MIT Press (2006)
Minsky, M.: A framework for representing knowledge. In: Haugeland, J. (ed.) Mind Design. The MIT Press, Cambridge (1981); A longer version appeared in The Psychology of Computer Vision (1975), Republished in [31]
Mortimer, M.: On languages with two variables. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 21, 135–140 (1975)
Muller, D.E., Schupp, P.E.: Alternating automata on infinite trees. Theoretical Computer Science 54, 267–276 (1987)
Nebel, B.: Reasoning and Revision in Hybrid Representation Systems. LNCS (LNAI), vol. 422. Springer, Heidelberg (1990)
Nebel, B.: Terminological reasoning is inherently intractable. Artificial Intelligence 43, 235–249 (1990)
Ortiz, M., Calvanese, D., Eiter, T.: Data complexity of query answering in expressive description logics via tableaux. J. of Automated Reasoning 41(1), 61–98 (2008)
Pacholski, L., Szwast, W., Tendera, L.: Complexity of two-variable logic with counting. In: Proc. of the 12th IEEE Symp. on Logic in Computer Science (LICS 1997), pp. 318–327. IEEE Computer Society Press, Los Alamitos (1997)
Parsia, B., Sirin, E., Kalyanpur, A.: Debugging OWL ontologies. In: Ellis, A., Hagino, T. (eds.) Proc. of the 14th International Conference on World Wide Web (WWW 2005), pp. 633–640. ACM, New York (2005)
Patel-Schneider, P.F.: DLP. In: Proc. of the 1999 Description Logic Workshop (DL 1999). CEUR Electronic Workshop Proceedings, pp. 9–13 (1999), http://ceur-ws.org/Vol-22/
Patel-Schneider, P.F., McGuiness, D.L., Brachman, R.J., Resnick, L.A., Borgida, A.: The CLASSIC knowledge representation system: Guiding principles and implementation rational. SIGART Bull. 2(3), 108–113 (1991)
Peltason, C.: The BACK system — an overview. SIGART Bull. 2(3), 114–119 (1991)
Ross Quillian, M.: Semantic memory. In: Minsky, M. (ed.) Semantic Information Processing, pp. 216–270. The MIT Press, Cambridge (1968)
Rector, A., Horrocks, I.: Experience building a large, re-usable medical ontology using a description logic with transitivity and concept inclusions. In: Proceedings of the Workshop on Ontological Engineering, AAAI Spring Symposium (AAAI 1997), Stanford, CA. AAAI Press, Menlo Park (1997)
Schild., K.: A correspondence theory for terminological logics: Preliminary report. In: Proc. of the 12th Int. Joint Conf. on Artificial Intelligence (IJCAI 1991), pp. 466–471 (1991)
Schild, K.: Querying Knowledge and Data Bases by a Universal Description Logic with Recursion. PhD thesis, Universität des Saarlandes, Germany (1995)
Schlobach, S., Cornet, R.: Non-standard reasoning services for the debugging of description logic terminologies. In: Gottlob, G., Walsh, T. (eds.) Proc. of the 18th Int. Joint Conf. on Artificial Intelligence (IJCAI 2003), Acapulco, Mexico, pp. 355–362. Morgan Kaufmann, Los Altos (2003)
Schmidt-Schauß, M.: Subsumption in KL-ONE is undecidable. In: Brachman, R.J., Levesque, H.J., Reiter, R. (eds.) Proc. of the 1st Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 1989), pp. 421–431. Morgan Kaufmann, Los Altos (1989)
Schmidt-Schauß, M., Smolka, G.: Attributive concept descriptions with unions and complements. Technical Report SR-88-21, Fachbereich Informatik, Universität Kaiserslautern, Kaiserslautern, Germany (1988)
Schmidt-Schauß, M., Smolka, G.: Attributive concept descriptions with complements. Artificial Intelligence 48(1), 1–26 (1991)
Sirin, E., Parsia, B.: Pellet: An OWL DL reasoner. In: Proc. of the 2004 Description Logic Workshop (DL 2004), pp. 212–213 (2004)
Suntisrivaraporn, B.: Module extraction and incremental classification: A pragmatic approach for \(\mathcal{EL}^+\) ontologies. In: Bechhofer, S., Hauswirth, M., Hoffmann, J., Koubarakis, M. (eds.) ESWC 2008. LNCS, vol. 5021, pp. 230–244. Springer, Heidelberg (2008)
Suntisrivaraporn, B.: Polynomial-Time Reasoning Support for Design and Maintenance of Large-Scale Biomedical Ontologies. PhD thesis, Fakultät Informatik, TU Dresden (2009), http://lat.inf.tu-dresden.de/research/phd/#Sun-PhD-2008
Thomas, W.: Automata on infinite objects. In: Handbook of Theoretical Computer Science, ch. 4, vol. B, pp. 134–189. Elsevier Science Publishers, Amsterdam (1990)
Tobies, S.: A PSPACE algorithm for graded modal logic. In: Ganzinger, H. (ed.) CADE 1999. LNCS (LNAI), vol. 1632, pp. 52–66. Springer, Heidelberg (1999)
Tobies, S.: Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD thesis, LuFG Theoretical Computer Science, RWTH-Aachen, Germany (2001)
Tsarkov, D., Horrocks, I.: faCT++ description logic reasoner: System description. In: Furbach, U., Shankar, N. (eds.) IJCAR 2006. LNCS (LNAI), vol. 4130, pp. 292–297. Springer, Heidelberg (2006)
Vardi, M.Y., Wolper, P.: Reasoning about infinite computations. Information and Computation 115(1), 1–37 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Baader, F. (2009). Description Logics. In: Tessaris, S., et al. Reasoning Web. Semantic Technologies for Information Systems. Reasoning Web 2009. Lecture Notes in Computer Science, vol 5689. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03754-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-03754-2_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03753-5
Online ISBN: 978-3-642-03754-2
eBook Packages: Computer ScienceComputer Science (R0)