Knowledge Representation & Reasoning: 2012-2013
OverviewMSc students will be assessed by invigilated exam lasting approximately 3 hours in week 0 of TT.
Students attending this course are expected to acquire a good understanding of the logical foundations of Knowledge Representation and Reasoning as well as to become familiar with current research trends in the field. The course requires some familiarity with propositional and first order logic.
Special emphasis is placed on decidable fragments of first order logic, which are suited for Knowledge Representation. These include, for example, the logics underlying ontology-based technologies and the Semantic Web.
The course will also discuss logics that depart from first order logic, such as non-monotonic logics.
- Students satisfying the prerequisites are expected to understand the fundamental principles of logic-based Knowledge Representation;
- be able to model simple application domains in a logic-based language;
- understand the notion of a reasoning service;
- master the fundamentals of the reasoning algorithms underlying current systems;
- understand the fundamental tradeoff between representation power and computational properties of a logic-based representation language;
- be conversant with several widely used knowledge representation languages; and
- understand how the theoretical material covered in the course is currently being applied in practice.
PrerequisitesStudents taking this course should have completed the first year Logic and Proof course (or an equivalent course in a different institution). Students would benefit from taking the third year Computational Complexity course as well as the second year Databases course; however, this is not a requirement.
PART 1: KR&R WITH PROPOSITIONAL AND FIRST ORDER LOGIC
- Introduction to knowledge-based technologies and knowledge representation
- Propositional Logic as a simple knowledge representation language
- Reasoning in Propositional Logic
- Representing Knowledge in First Order Predicate Logic
- Reasoning in First Order Predicate Logic
PART 2: FRAGMENTS OF FIRST ORDER LOGIC
- Description Logics as Knowledge Representation Languages
- Reasoning in Description Logics
- Lightweight description logics.
- Horn Fragments of First Order Logic. Rule-based Knowledge Representation and Reasoning
- Ontologies and Ontology Languages.
- Other Decidable Fragments of First Order Logic for Knowledge Representation
PART 3: NON-MONOTONIC LOGICS
- Classical vs non-monotonic logic. Ways to achieve non-monotonicity.
- Stable Model Semantics
Representing knowledge using logic. Reasoning techniques in propositional and first order logic. Fundamental tradeoff between representation power and computational properties. Fragments of first order logic suited for Knowledge Representation. Ontology languages for the Semantic Web. Non-monotonic logics.
Relevant for Part 1:
- Knowledge Representation and Reasoning. Ronald Brachman and Hector Levesque. The Morgan Kaufmann Series in Artificial Intelligence, 2004.
- First Order Logic and Automated Theorem Proving. Melvin Fitting. Texts in Computer Science. 1995.
- Handbook of Knowledge Representation. Frank van Harmelen, Vladimir Lifschitz and Bruce Porter (Eds). Foundations of Artificial Intelligence, 2008.
Relevant for Part 2:
- The Description Logic Handbook: Theory, Implementation and Applications, 2nd Edition. Franz Baader, Diego Calvanese, Deborah L. MacGuinness, and Daniele Nardi. Cambridge University Press. 2007.
- Foundations of Semantic Web Technologies. Chapman & Hall/ CRC Textbooks in Computing. Pascal Hitzler, Markus Kroetsch, and Sebastian Rudolph, 2009.
Relevant for Part 3:
- Nonmonotonic Reasoning. Grigoris Antoniou. The MIT Press, 1997.
- Bridges Between Classical and Nonmonotonic Logic. David Makinson. Texts in Computing. 2005.