DESCRIPTION LOGICS course

warning: the course material has been recently completely revised. The bibliography and the reference material have been updated; most slides were rewritten. Slides of modules 5 and 6 are still to be revised. (March 2002)

lecturer: Enrico Franconi, Faculty of Computer Science, Free University of Bozen-Bolzano, Italy

prerequisites: basic Mathematical Logics course

course description:

The main effort of the research in knowledge representation is providing theories and systems for expressing structured knowledge and for accessing and reasoning with it in a principled way. In this course we will study Description Logics (DL), an important powerful class of logic-based knowledge representation languages (see www.dl.kr.org). The emphasis will be on a rigorous approach to knowledge representation and building ontologies. After an original review of the relevant concepts on computational logics, the course will start with an introduction to Object-Oriented representations in Information Systems and Artificial Intelligence, which serve as the main motivations for studying DL. DL will be introduced with its simplest formalization; the computational properties and algorithms of the so called structural DL will be analyzed. Then, the course considers propositional DL: we will study the computational properties and the reasoning with tableaux calculus. In the second part of the course, we will consider advanced topics such as the representation of knowledge bases and ontologies, and the connections of DL with Modal Logics and First Order Logic. The last module of the course will analyze the connections of DL with database theory.

course material:

Students are expected to read and study during the course all the material marked as basic reading; the rest of the material is optional but recommended anyway. Most papers can be downloaded from this page. Students without a strong background in classical logic are warmly suggested to review before the beginning of the course the basic concepts of classical logic in one of the books suggested for module 1.

• part A: basics
  • module 1: A review of Computational Logics
    • slides:
      • Introduction
      • Foundations of Propositional Logics
      • Deduction in Propositional Logics
      • Foundations of First Order Logic
      • Using First Order Logic
    • material:
      • [basic reading] Any basic handbook on mathematical logic:
        • J. Kelly. The Essence of Logic. Prentice Hall, 1997. (The simplest book to learn the basics of logic; chapters 1, 2, (4), 6, (7) and 8)
        • A. Galton. Logic for Information Technology. Wiley, 1990. (Simple but too verbose; chapters 1 to 6)
        • H. Enderton. A Mathematical Introduction to Logic. Academic Press, 2001. (A rigorous book; chapters 1 and 2 up to 2.6)
        • H. D. Ebbinghaus, J. Flum, W. Thomas. Mathematical Logic. Springer-Verlag, 1984. (A rigorous book; chapters 1, 2 and 3)
        • E. Mendelson. Introduction to Mathematical Logic. Chapman and Hall, 1997. (Not my favourite; chapters 1 and 2)
  • module 2: Structural Description Logics
    • slides:
      • The need for a Logic in conceptual modelling
      • Motivations from Object-Oriented languages
      • The simplest Structural Description Logic: FL-
    • material:
      • [basic reading] D. Nardi, R. J. Brachman. An Introduction to Description Logics. In the Description Logic Handbook, edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider, Cambridge University Press, 2002, pages 5-44.
      • [basic reading] H. J. Levesque and R. J. Brachman. Expressiveness and tractability in knowledge representation and reasoning. Computational Intelligence journal 3, 78-93 (1987).
      • [strongly recommended] B. Nebel. Reasoning and Revision in Hybrid Representation Systems. Lecture Notes in Artificial Intelligence 422, Springer-Verlag, 1990. Chapters 1 - 6.
  • module 3: Propositional Description Logics
    • slides:
      • Propositional Description Logics
    • material:
      • [strongly recommended] F. Baader, W. Nutt. Basic Description Logics. In the Description Logic Handbook, edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider, Cambridge University Press, 2002, pages 47-100.
      • [basic reading] Donini, F., Lenzerini, M., Nardi, D., Schaerf, A., `Reasoning in Description Logics', in: Principles of Knowledge Representation and Reasoning, edited by G. Brewka; Studies in Logic, Language and Information, CLSI Publications, pp 193-238, 1996.
      • [basic reading] F. Baader and U. Sattler. An Overview of Tableau Algorithms for Description Logics. Studia Logica, 69:5-40, 2001
      • [strongly recommended] D. Calvanese, G. De Giacomo, M. Lenzerini, and D. Nardi, `Reasoning in expressive description logics', in: A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning. Elsevier Science Publishers (North-Holland), Amsterdam, 2001, pages 1581-1634.
      • [recommended] Hollunder, B., Nutt, W., `Subsumption Algorithms for Concept Languages', DFKI report, RR-90-04, Saarbruecken Germany, 1990; extended version of a previously published paper in proc. ECAI'90, pp 348-353.
      • [recommended] Schaerf, A., `Reasoning with individuals in concept languages', Data and Knowledge Engineering, Vol 13(2), pp 141-176, 1994.
      • [advanced] F. Donini. Complexity of Reasoning. In the Description Logic Handbook, edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider, Cambridge University Press, 2002, pages 101-141.
• part B: advanced topics
  • module 4: Description Logics and Knowledge Bases
    • slides:
      • Formalising Knowledge Bases
      • Using Knowledge Bases and Ontology Engineering
    • material:
      • [basic reading] Brachman, R., McGuinness, D., Patel-Schneider, P., Resnick, L., Borgida, A.. Living with CLASSIC: When and how to use a KL-ONE-like language. In: Principles of Semantic Networks, edited by John Sowa, Morgan Kaufmann, 1991, pages 401-456.
      • [basic reading] A. Borgida, R. J. Brachman. Conceptual Modelling with Description Logics. In the Description Logic Handbook, edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider, Cambridge University Press, 2002, pages 359-381.
  • module 5: Description Logics and Logics
    • slides:
      • Description Logics and Logics
    • material:
      • [basic reading] A. Borgida, `On the relative expressive power of Description Logics and Predicate Calculus', Artificial Intelligence 82 (1996) 353-367.
      • [basic reading] K. Schild, `A correspondence theory for terminological logics: preliminary report', IJCAI-91, pp 466-471, October 1991.
      • [strongly recommended] B. Nebel and G. Smolka. Attributive Description Formalisms... and the rest of the world. In C. Rollinger O. Herzog, editor, Text Understanding in LILOG, LNAI 546. Springer-Verlag, Berlin, Germany, 1991, pages 439-452.
      • [strongly recommended] D. Nardi, U. Sattler, D. Calvanese, R. Molitor. Relationships with other formalisms. In the Description Logic Handbook, edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider, Cambridge University Press, 2002, pages 142-183.
  • module 6: Description Logics and Databases
    • slides:
      • Description Logics and Databases
    • material:
      • [basic reading] A. Borgida, M. Lenzerini, R. Rosati. Description Logics for Databases. In the Description Logic Handbook, edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider, Cambridge University Press, 2002, pages 472-494.
      • [basic reading] A. Borgida, `Description Logics in Data Management', IEEE Transactions on Knowledge and Data Engineering vol.7, No. 5, October 1995, pages 671-682.
      • [strongly recommended] D. Calvanese, M. Lenzerini, D. Nardi, `Description Logics for Conceptual Data Modeling', Logics for Databases and Information Systems, J. Chomicki and G. Saake eds., Kluwer, 1998, pages 229-263.
      • [recommended] K. Schild, `Tractable reasoning in a universal description logic', Proceedings of 1st Workshop KRDB'94, Saarbrücken, Germany, September 20-22, 1994.
      • [recommended] Buchheit, M., Jeusfeld, M., Nutt, W., Staudt, M., `Subsumption between Queries to Object-Oriented Databases', Information Systems, pp 33-54, January 1994.

useful links:

• The official Description Logics page
• The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, 2002. ISBN 0521781760. Edited by F. Baader, D. Calvanese, D. McGuinness, D. Nardi, P. F. Patel-Schneider. Contributors: D. Nardi, R.J. Brachman, F. Baader, W. Nutt, F.M. Donini, U. Sattler, D. Calvanese, R. Molitor, G. De Giacomo, R. Kuesters, F. Wolter, D.L. McGuinness, P.F. Patel-Schneider, R. Moeller, V. Haarslev, I. Horrocks, A. Borgida, C. Welty, A. Rector, E. Franconi, M. Lenzerini, R. Rosati.

Course version 2 ( Last modified: Mon Dec 23 23:41:13 GMT 2002 )

---

Diplom, Formale Methoden, Informatik, Künstliche Intelligenz, Logik, Europäischer Master, Fachlaureat, Internationaler Master, Master, master, Spezialisierung, Stipendium, Studienplatz, Studium, Universität Bozen, borsa di studio, informatica, intelligenza artificiale, logica, borse di studio, corsi specialistici postlaurea, degree, artificial intelligence, formal methods, logic, logics, diploma, european master, european masters, grant, grants, informatikstudium, laurea, master europeo, scienze informazione, master universitari, masters, masterstudiengang, masterstudiengänge, scholarship, specializzazione, studi, università bolzano, university bolzano, university bozen, universität bozen, erasmus mundus, european studies, freie universität bozen, studiengang, studiengänge, studieren, studium, international students, lauree specialistiche, laurea specialistica, libera università di bolzano, wirtschaftsinformatik, studienführer, technische informatik, universitäten informatik, DESCRIPTION LOGICS, DESCRIPTION LOGICS course, DESCRIPTION LOGICS tutorial