CS222 Knowledge Representation and Reasoning
Tom Costello
Course Overview

Week 1
Wednesday 5th From Data Structures to Logic.

Readings: A Framework for Representing Knowledge http://web.media.mit.edu/~minsky/papers/Frames/frames.html Programs with Common Sense http://www-formal.stanford.edu/jmc/mcc59.html

Week 2
Monday 10th First Order Logic, Syntax, Semantics, Completeness, Undecidability. Monadic Second order Logic, completeness, decidability. Higher order logics. Incompleteness.

Readings: KR&R Chapter 2

Wednesday 12th Resolution Theorem Proving, KR&R, Snark
Readings: Snark Manual

Week 3
Monday 17th Frames
Readings: Hayes, P. J. (1980). The logic of frames. In D. Metzing, Ed., Frame Conceptions and Text Understanding. Berlin: deGruyter, pp. 46-61.
A Framework for Representing Knowledge, Minsky Bernhard Nebel; "Frame-Based Systems"; The MIT Encyclopedia of Cognitive Sciences.

Wednesday 19th KIF and standardized logics
Readings: KIF Manual http://logic.stanford.edu/kif/Hypertext/kif-manual.html http://www-ksl.stanford.edu/email-archives/interlingua.messages/530.html

SCL http://philebus.tamu.edu/cl/

Week 4
Monday 24th Modal Logics. Knowledge, Belief, Deontic Logic, All I know. Issues in first order modal logics. Predicates on sentences and Montagues Paradox

Readings: Mints, Grigori A Short Introduction to Modal Logic. Kaplan, D. and Montague, R. (1960) `A Paradox Regained', Notre Dame Journal of Formal Logic 1: 79-90

Wednesday 26th Description Logics
Readings: chapter 9 of KR&R Alexander Borgida, Ronald J. Brachman, Deborah L. McGuinness, Lori Alperin Resnick; CLASSIC: A Structural Data Model for Objects; 1989.

Week 5
Monday 31st Relational Algebra, Databases Readings.

Wednesday 2nd February n-variable fragments.
(un)Decidability and (in)completeness of description logics and relation algebra.

Week 6
Monday 7th Inference, proof checkers, automated theorem proving, PVS,
Readings: PVS Manual

Wednesday 9th Satisfiability. GSAT, Davis Putnam, Linear Logic and Cut. GSAT, WalkSAT, KR&R,

Week 7
Monday 14th Ontologies
Readings: R. Fikes; "Ontologies: What Are They, and Where's The Research?"; Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning; Cambridge, Massachusetts; November 5-8, 1996.
Tom Gruber; "What Is An Ontology?"; Knowledge Systems Laboratory, Stanford University.

Wednesday 16th DAML OIL
Readings: Dan Brickley and R.V. Guha (editors); "Resource Description Framework (RDF) Schema Specification 1.0".
Mike Dean, Dan Connolly, Frank van Harmelen, James Hendler, Ian Horrocks, Deborah L. McGuinness, Peter F. Patel-Schneider, and Lynn Andrea Stein (editors); "Web Ontology Language (OWL) Reference Version 1.0"; W3C Working Draft; 12 November 2002.

Week 8
Monday 21st Situation Calculus

Wednesday 23rd
Readings: Allen, event calculus, interval temporal logic Readings: Allen, J.F. and Ferguson, G. Actions and Events in Interval Temporal Logic, J. Logic and Computation 4, 5, 1994.
P. Hayes; "A Catalog of Temporal Theories"; Tech report UIUC-BI-AI-96-01, University of Illinois; 1995. Chapters 1-3; chapters 4,5 and appendices. Planning, STRIPS, Sitcalc,

Week 9
Monday 28th Minimal Entailment. Lewis, conditionals, Circumscription,

Wednesday 2nd KLM's preferential entailment, Shoham, Cumulative Default Logic. Closed World Assumption, Domain Closure.

Week 10
Monday 7th Belief Revision. Ramsey Test, AGM postulates, Gardenfors Triviality Result.

Wednesday 9th Intensional Logic, Montague Grammar, Morning and Evening Star, McAllester's Noun Phrases

Final: Take home exam 40%

Three homeworks: 20% each.

Homework 1: Due Monday 24th January Primarily c-programming

Homework 2: Due Monday 7th February Using Snark and automated theorem prover, and some problem questions

Homework 3: Due Monday 28th February Using PVS, a proof checker, and some problem questions.