Institut für Informatik, Universität Freiburg

Main Page

Slides

1. Introduction
   • 1.1 Organization (scaled down ps file) [15.10./rev: 18.10.]
   • 1.2 Motivation (scaled down ps file) [15.10./rev: 18.10.]

2. Reminder: Classical Logic
   • 2.1 Propositional Logic (scaled down ps file) [22.10.]
   • 2.2 First-Order Predicate Logic (scaled down ps file) [24.10.]

3. Qualitative Representation and Reasoning
   • 3.1 Introduction (scaled down ps file) [29.10./31.10.]
   • 3.2 Allen's Calculus (scaled down ps file)[12.11.]
   • 3.3 Reasoning in Allen's Calculus (scaled down ps file) [12.11.]
   • 3.4 A Maximal Tracatable Subalgebra (scaled down ps file) [14.11.]
   • 3.5 Modal Logic (scaled down ps file) [19.11./21.11.]
   • 3.6 Spatial Representation and Reasoning: RCC8 and Topology (scaled down ps file) [26.11.]
   • 3.7 Spatial Representation and Reasoning: Reasoning with RCC8 (scaled down ps file) [28.11.]
   • 3.8 The Double-Cross: A Calculus for Spatial Navigation(scaled down ps file) [10.12.]

4. Nonmonotonic Logics
   • 4.1 Introduction (scaled down ps file) [12.12.]
   • 4.2 Basics of Default Logic (scaled down ps file) [12.12.]
   • 4.3 Formal Properties of Default Logics (scaled down ps file) [17.12./19.12./7.1.]
   • 4.4 Argumention Theoretic Approaches (compl. 9.1.) (scaled down ps file) [7.1./9.1./14.1.]
   • 4.5 Introduction to Cumulative Logics (scaled down ps file)[14.1.]
   • 4.6 Cumulativity: Undesirable Propteries, Cumulative Closure and Models Logics (scaled down ps file) [16.1.]
   • 4.7 Cumulative and Preferential Logics (scaled down ps file) [21.1.]
   • 4.8 Belief Revision (scaled down ps file) [23.1.]

5. Semantic Networks and Description Logics
   • 5.1 Introduction (scaled down ps file) [28.1]
   • 5.2 Simple, Strict Inheritance Networks (scaled down ps file) [28.1]
   • 5.3 Description Logics: Terminology and Notation (scaled down ps file) [30.1]
   • 5.4 Reasoning Services and Reductions (scaled down ps file) [4.2]
   • 5.5 Reasoning Algorithms (scaled down ps file)[6.2.]
   • 5.6 Computational Complexity (scaled down ps file)[11.2.]

Bibliography

Section 1.1

• R. J. Brachman and Hector J. Levesque, Knowledge Representation and Reasoning, unpublished manuscript.
• C. Beierle and G. Kern-Isberner, Methoden wissensbasierter Systeme, Vieweg, 2000.
• G. Brewka, ed., Principles of Knowledge Representation, CSLI Publications, 1996.
• G. Lakemeyer and B. Nebel (eds.), Foundations of Knowledge Representation and Reasoning, Springer-Verlag, 1994
• W. Bibel, S. Hölldobler, and T. Schaub Wissensrepräsentation und Inferenz, Logics for Knowledge Representation, in: N. J. Smelser and P. B. Baltes (eds.), International Encyclopedia of the Social and Behavioral Sciences, Kluwer, Dordrecht, to appear.
• B. Nebel, Artificial Intelligence: A Computational Perspective in G. Brewka, ed., Principles of Knowledge Representation, CSLI Publications, 1996, 237-266.

Sections 2.1 and 2.2

• U. Schöning. Logik für Informatiker. Spektrum-Verlag. 2000, 5th edition.
• Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, NJ, 1981 (Chapters 8-9).
• Volker Sperschneider and Grigorios Antoniou. Logic - A Foundation for Computer Science. Addison-Wesley, Reading, MA, 1991 (Chapters 1-3).
• H.-P. Ebbinghaus, J. Flum, and W. Thomas. Einführung in die mathematische Logik. Wissenschaftliche Buchgesellschaft, Darmstadt, 1986.

Section 3.1

• Alan K. Mackworth. Constraint satisfaction. In S. C. Shapiro, editor, Encyclopedia of Artificial Intelligence, pages 205--211. Wiley, Chichester, England, 1987.
• Alan K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99--118, 1977.
• Peter B. Ladkin and Roger Maddux. On binary constraint networks. Journal of the ACM, 41:435--469, 1994.
• Ugo Montanari. Networks of constraints: fundamental properties and applications to picture processing. Information Science, 7:95--132, 1974.
• R. Hirsch, Tractable approximations for temporal constraint handling, Artificial Intelligence, 116: 287-295, 2000.

Sections 3.2, 3.3, and 3.4

• J. F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11):832--843, November 1983. Also in Readings in Knowledge Representation.
• P. van Beek and R. Cohen. Exact and approximate reasoning about temporal relations. Computational Intelligence, 6:132--144, 1990.
• B. Nebel and H.-J. Bürckert. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra, in: Journal of the ACM, 42(1): 43-66, 1995.
• B. Nebel, Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class, CONSTRAINTS, 1(3): 175-190, 1997.
• A. Krokhin, P. Jeavons and P. Jonsson: A Complete Classification of Complexity in Allen's Algebra in the Presence of a Non-Trivial Basic Relation. In Proc. 17th Int. Joint Conf. on AI (IJCAI-01), 83-88, Seattle, WA, 2001.

Section 3.5

• A. Nerode. Some lectures on modal logic. In F. L. Bauer, editor, Logic, Algebra, and Computation, volume 79 of NATO ASI Series on Computer and System Sciences, pages 281--334. Springer-Verlag, Berlin, Heidelberg, New York, 1991.
• M. Fitting. Basic Modal Logic. In D. M. Gabbay and C. J. Hogger and J. A. Robinson, eds., Handbook of Logic in Artificial Intelligence and Logic Programming -- Vol. 1: Logical Foundations, Oxford University Press, Oxford, UK, 1993.
• M. Fitting. Proof Methods for Modal and Intuitionistic Logic. Reidel, Dordrecht, Holland, 1983.
• R. Goldblatt. Logics of Time and Computation. Number 7 in Lecture Notes. Center for the Study of Language and Information, Stanford University, Stanford, CA, 2nd edition, 1992.
• B. F. Chellas. Modal Logic: An Introduction. Cambridge University Press, Cambridge, UK, 1980.

Sections 3.6-3.7

• D. A. Randell, Z. Cui and A. G. Cohn, A Spatial Logic Based on Regions and Connection, in: Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference, Morgan Kaufmann, San Mateo, 1992, 165-176.
• B. Bennett, Spatial Reasoning with Propositional Logic, in: Principles of Knowledge Representation and Reasoning: Proceedings of the 4th International Conference (KR-94), 1994, 51-62.
• Werner Nutt, On the Translation of Qualitative Spatial Reasoning Problems into Modal Logics, Advances in Artificial Intelligence, Proc. 23rd Annual German Conference on Artificial Intelligence, KI'99, Bonn (Germany), September 1999.
• J. Renz and B. Nebel, On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus, Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI'97), August 1997, 522-527.
• J. Renz, B. Nebel, Efficient Methods for Qualitative Spatial Reasoning, Proceedings of the 13th European Conference on Artificial Intelligence (ECAI'98), August 1998, 562-566.

Sections 3.8

• Christian Freksa. Using orientation information for qualitative spatial reasoning. In A. U. Frank, I Campari, and U. Formentini, editors, Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, pages 162--178. Springer-Verlag, Berlin, Heidelberg, New York, 1992.
• Alexander Scivos and Bernhard Nebel. Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation. In D. Montello, ed., Proc. COSIT-2001, Springer, 2001.
• Amar Isli and Anthony G. Cohn. An algebra for cyclic ordering of 2D orientation. In Proceedings of the 15th National Conference of the American Association for Artificial Intelligence (AAAI-98), pages 643--649, Madison, WI, July 1998. MIT Press. There exists also a revised version published in Artificial Intelligence.
• Longin Latecki and Ralf Röhrig. Orientation and qualitative angle for spatial reasoning. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93), pages 1544--1549, Chambery, France, August 1993. Morgan Kaufmann.
• James Renegar. On the computational complexity and geometry of the first order theory of the reals. Part I--III. Journal of Symbolic Computation, 13(3):255--300, 301--328, 329--352, 1992.

Sections 4.1-4.3

• Raymond Reiter. A logic for default reasoning. Artificial Intelligence, 13(1):81--132, April 1980.
• Georg Gottlob. Complexity Results for Nonmonotonic Logics. Journal for Logic and Computation, 2(3): 397-425, 1992.
• Marco Cadoli and Marco Schaerf. A Survey of Complexity Results for Non-monotonic Logics. The Journal of Logic Programming, 17: 127-160, 1993.
• Gerhard Brewka. Nonmonotonic Reasoning: Logical Foundations of Commonsense. Cambridge University Press, Cambridge, UK, 1991.
• Franz Baader and Bernhard Hollunder. Embedding defaults into terminological representation systems. Journal of Automated Reasoning, 14:149-180, 1995.

Sections 4.4

• Yannis Dimopoulos, Bernhard Nebel, and Francesca Toni. Preferred arguments are harder to compute than stable extensions. In Proc IJCAI-99, Stockholm, Sweden, August 1999. Morgan Kaufmann.
• Yannis Dimopoulos, Bernhard Nebel, and Francesca Toni. Finding Admissible and Preferred Arguments Can be Very Hard, in: Principles of Knowledge Representation and Reasoning, Proceedings of the 7th International Conference (KR'2000), Breckenridge, CO, 2000, p. 53-61
• Andrei Bondarenko, Phan Minh Dung, Robert A. Kowalski, and Francesca Toni. An abstract, argumentation-theoretic framework for default reasoning. Artificial Intelligence, 93(1--2):63--101, 1997.
• R. Kowalski, F. Toni, Abstract Argumentation, Artificial Intelligence and Law Journal 4(3-4): 275-296, 1996.

Sections 4.5-4.7

• Sarit Kraus, Daniel Lehmann, and Menachem Magidor. Nonmonotonic reasoning, preferential models and cumulative logics, Artifical Intelligence, 44(1-2): 167-207, 1990.
• Daniel Lehman and Menachem Magidor. What does a conditional knowledge base entail?, Artificial Intelligence, 55: 1-60, 1992.
• Dov M. Gabbay. Theoretical foundations for non-monotonic reasoning in expert systems. In K. R. Apt, editor, Proceedings NATO Advanced Study Institute on Logics and Models of Concurrent Systems, pages 439--457. Springer-Verlag, Berlin, Heidelberg, New York, 1985.
  Introduced the notion of cumulativity
• Yoav Shoham. Reasoning about Change. MIT Press, Cambridge, MA, 1988.
  Introduced the idea of preferential models

Section 4.8

• D. Makinson. How to give it up: A survey of some formal aspects of theory change. Synthese, 62:347--363, 1985.
  Very good introduction to the topic
• B. Nebel. Belief revision and default reasoning: Syntax-based approaches. In Proc. KR-91, 417--428, Cambridge, MA, Apr. 1991.
• C. E. Alchourrón, P. Gärdenfors, and D. Makinson. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 50(2):510--530, 1985.
  Introduces the so-called AGM approaches: Characterizing belief revision operations by postulates.
• P. Gärdenfors. Knowledge in Flux - Modeling the Dynamics of Epistemic States. MIT Press, Cambridge, MA, 1988.
• B. Nebel. How Hard is it to Revise a Belief Base?, in D. Dubois and H. Prade (eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, Vol. 3: Belief Change, Kluwer Academic, Dordrecht, The Netherlands, 1998, 77-145.
• P. Gärdenfors, Belief Revision and Nonmonotonic Logic: Two Sides of the Same Coin?, In Proc. ECAI-90, 1990, 768-773.
• H. Rott, Change, choice and inference : a study of belief revision and nonmonotonic reasoning, Clarendon, Oxford, 2001.

Section 5.1

• Quillian, M. R., Word Concepts: A Theory and Simulation of Some Basic Semantic Capabilities, Behavioral Science 12: 410-430, 1967.
  Appears also in Readings in Knowledge Representation
• Minsky, M., A Framework for Representing Knowledge, in: J. Haugeland (ed.), Mind Design, The MIT Press, Cambridge, MA, 1981, 95-128.
  Appears also in Readings in Knowledge Representation
• B. Nebel, Frame-Based Systems, in: Robert A. Wilson and Frank Keil (eds.), MIT Encyclopedia of the Cognitive Sciences, MIT Press, Cambridge, MA, 1999.
• Sowa, J., Principles of Semantic Networks, Morgan Kaufmann, San Mateo, CA, 1991.
• Brachman, R. J. and Levesque, H. J. (ed.), Readings in Knowledge Representation, Morgan Kaufmann, Los Altos, 1985.
• Findler, N. V., Associative Networks: Representation and Use of Knowledge by Computers, Academic Press, New York, 1979.

Section 5.2

• P. Atzeni, D. S. Parker, Set Containment Inference and Syllogisms, Theoretical Computer Science, 62: 39-65, 1988.

Section 5.3-5.4

• Ronald J. Brachman and James G. Schmolze. An overview of the KL-ONE knowledge representation system. Cognitive Science, 9(2):171-216, April 1985.
• Franz Baader, Hans-Jürgen Bürckert, Jochen Heinsohn, Bernhard Hollunder, Jürgen Müller, Bernhard Nebel, Werner Nutt, and Hans-Jürgen Profitlich. Terminological Knowledge Representation: A proposal for a terminological logic. Published in Proc. International Workshop on Terminological Logics, 1991, DFKI Document D-91-13.
• Bernhard Nebel. Reasoning and Revision in Hybrid Representation Systems, volume 422 of Lecture Notes in Artificial Intelligence. Springer-Verlag, Berlin, Heidelberg, New York, 1990.

Section 5.5-5.6

• Hector J. Levesque and Ronald J. Brachman. Expressiveness and tractability in knowledge representation and reasoning. Computational Intelligence, 3:78--93, 1987.
• Manfred Schmidt-Schauß and Gert Smolka. Attributive concept descriptions with complements. Artificial Intelligence, 48:1--26, 1991.
• Bernhard Hollunder and Werner Nutt. Subsumption Algorithms for Concept Languages. DFKI Research Report RR-90-04. DFKI, Saarbr\"ucken, 1990. Revised version of paper that was published at ECAI-90.
• F. Baader and U. Sattler. An Overview of Tableau Algorithms for Description Logics. Studia Logica, 69:5-40, 2001.
• I. Horrocks, U. Sattler, and S. Tobies. Practical Reasoning for Very Expressive Description Logics. Logic Journal of the IGPL, 8(3):239-264, May 2000.
• Bernhard Nebel and Gert Smolka. Attributive description formalisms \ldots and the rest of the world. In Otthein Herzog and Claus-Rainer Rollinger, editors, Text Understanding in LILOG, pages 439--452. Springer-Verlag, Berlin, Heidelberg, New York, 1991.
• Francesco M. Donini, Maurizio Lenzerini, Daniele Nardi, and Werner Nutt. Tractable concept languages. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, pages 458--465, Sydney, Australia, August 1991. Morgan Kaufmann.
• Klaus Schild. A correspondence theory for terminological logics: Preliminary report. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, pages 466--471, Sydney, Australia, August 1991. Morgan Kaufmann. Stellt den Zusammenhang zwischen terminologischen und Modallogiken her.
• I. Horrocks, U. Sattler, and S. Tobies. Reasoning with Individuals for the Description Logic SHIQ. In David MacAllester, ed., Proceedings of the 17th International Conference on Automated Deduction (CADE-17), Germany, 2000. Springer Verlag.