Outline of CS323
A listing of the topics covered by each class
Logical AI, the background to representing information in logic. An overview
of what will be covered in the course, and what homeworks, papers etc.
First order logic, model theory, proof theory. Second order logic, Henkin
models. Theorem Provers, PVS.
Enderton's "A Mathematical Introduction to Logic" provides a good introduction
to logic in general. It is a little light on higher order logic, which
we will use a lot. However, luckily there is little to know.
We shall need to use the PVS theorem prover. Using theorem provers
is an art, which takes time to learn, but which is very valuable. PVS is
actually quite easy to use, after initial teething pains.
The situation calculus and the event calculus: The two main formalisms
for reasoning about change.
McCarthy and Hayes. The limitations of the situation calculus. Reiter's
foundation axioms, categoricity. Representing actions. Kowalski's event
calculus. Linear vs branching time.
For this class the basic references are McCarthy and Hayes, Some
Philosophical Problems from the Standpoint of AI, Knowledge
In Action a draft of a book by Ray Reiter. Some
contributions to the metatheory of the situation calculus a overview
paper by Fiora Pirri and Ray Reiter, and Combining
Narratives by John McCarthy and Tom Costello. Event
Calculus Revisited by Murray Shanahan.
The frame problem: A major problem of logical AI. Its monotonic solution.
Frame axioms. The Yale Shooting Problem. Hayes's objections. Generating
successor state axioms in presence of domain constraints.
The main papers here are McCarthy and Hayes, Some
Philosophical Problems from the Standpoint of AI, Ray Reiter's A
simple solution to the frame problem (sometimes).
Leora Morgenstern has a overview paper on problems with solutions to
the frame problem, The Problem with Solutions to
the Frame Problem.
Planning and prediction in temporal formalisms.
Goal regression, implementation in theorem provers. Examples.
Axiomatization of the Blocksworld.
Theory put into PVS.
Non-monotonic reasoning: why we need it? (elaboration tolerance). Various
basic forms of circumscription, domain/predicate/formula. Handout
Definitions, model theory, soundness and "completeness". Minimal
The expressive power of circumscription. The complexity of circumscription.
Meaning of minimizing a formula. Characterization of expressive power
of different variants. NP hierarchy, and complexity.
How to reduce circumscription to first order logic. Two methods, DLS
Pointwise circumscription and Chronological minimization. Handout about action. There were also
photocopies of Vladimir's Lifschitz's Pointwise Circumscription paper,
and some pages (451-459) from Vol 4. of the Handbook of logic in artificial
intelligence. (The chapter by Shoham and Sandewall.)
Domain formula circumscription. Bossu and Seigel and the limit assumption. Handout
- Ways of making circumscription satisfiability preserving. Cofinal circumscription. Handout
Circumscription and the frame problem. Solutions by Baker, Lin and Reiter.
The projection problem: Solutions by Lin and Reiter, Giunchiglia and Costello.
Splitting theories to reduce casual reasoning to projection, Giunchiglia
Non-monotonic consequence relations
Defeasable logic and conditional logic
Default logic and the necessary modifications to make it cumulative.
Belief revision as proposed by AGM
Belief update and its relationship to theories of action.
Counterfactuals (McCarthy and Costello, Pearl, Lewis, Stalnaker, Ginsberg's
Intentional phenomena: Names of formulas and abstract syntax. The paradoxes
of syntactic modality. Perlis's and others approach to truth predicates
and these paradoxes.
Contexts, lifting axioms. Modal logic approaches to context.
Possible topics for final papers:
Representing Puzzles made from beads and string
Three dimensional puzzles
The role of Qualification Constraints
An analysis of the monotonic content of Ramification Constraints
Unifying SCAN and DLS
Sliding tile puzzles
The expressive power of default logic/pointwise circ/etc.
Relational Rippling applied to Circumscription
Simplifying Circumscription Formulas
Decidability of circumscription as applied to the frame problem
modified: Tue Mar 31 15:17:14 PST 1998