The Department of Computer Science & Engineering
CSE 663:
Fall 2006


This is a living document; the latest version will always be available on the Web at:

Last Update: 13 November 2006

Note: NEW or UPDATED material is highlighted

Index: Other Relevant Links:
  • Course Description
  • CSE 663 homepage
  • Prerequisites
  • Directory of Documents
  • Staff
  • Email Archive
  • Class Meetings
  • Texts
  • Important Dates & Tentative Schedule
  • Reading
  • Attendance, Homeworks, Projects, Exams, Listserv
  • Projects
  • How to Study
  • Grading
  • Incompletes
  • Academic Integrity
  • Classroom Disruptions


    Knowledge representation (KR), more properly called "knowledge representation and reasoning" (KRR), is the part of AI that is concerned with the techniques for representing and reasoning about the information to be used by an AI program.

    Official catalog description:
    A second graduate course in knowledge representation and reasoning covering such topics as automated theorem proving, semantic network implementation, etc., and surveying knowledge representation and reasoning topics not covered in other graduate-level courses. Topics will vary according to instructor and student interests.

    Fall 2006 description:
    This course is a sequel to
    Prof. Shapiro's CSE 563 from the Spring 2006 semester. It will be a survey of issues and techniques of representing knowledge, belief, and information in a(n artificially intelligent) computer system and of the syntax and semantics of various representational formalisms. Classic papers will be read and current research issues discussed.

    I will begin with a brief review of logic and automated theorem proving (unification and resolution) and of the SNePS knowledge-representation, reasoning, and acting system. Remaining topics will include some or all of the following, as well as others as time permits: ontologies, semantic networks, production systems, frames, description logics, inheritance networks, default reasoning, and modal and epistemic logics.




    LectureRapaport472919 MWF12:00 noon - 12:50 p.m. Bell 337



    Note 1: In addition to the schedule below, I plan to meet with each of you individually once or twice during the semester to discuss your projects with you.

    Note 2: I have adjusted some of the dates and assignments below to reflect what we actually did in class—including the week we lost when I was in the hospital—rather than on what I had planned or hoped to do:-)

    M Aug 28 1. What is KR? this syllabus;
    B&L, Ch.1
    W   30 What is KR? (concluded);
    2. Contextual Vocabulary Acquisition
    CVA website
    F Sep 1 Syntax vs. Semantics
    3. First-Order Logic (review)
    B&L, Ch.2
    M   4 Labor Day; no class  
    W   6 FOL review (cont'd.) Thomason 1998
    F   8 out of town?; no class?  
    M   11 FOL review (cont'd.)  
    W   13 SNePS Tutorial due;
    FOL review (cont'd.)
    B&L, Ch.3
    F   15 CVA word choice due;
    FOL review (concluded)
    Smith 2003
    M   18 4. Ontologies Noy & McGuinness 2001
    W   20 Ontologies (concluded)  
    F   22 5. Semantic Networks:
    Shapiro & Rapaport 1995
    M   25 no class—WJR in hospital  
    W   27 no class—WJR in hospital  
    F   29 no class—WJR in hospital  
    M Oct 2 Yom Kippur; no class  
    W   4 Semantic Networks:
    Quillian 1967
    F   6 Semantic Networks:
    Quillian (concluded);
    Conceptual Dependency
    Lytinen 1992
    M   9 Conceptual Dependency (concluded) B&L, Ch.7
    W   11 6. Production Systems Slagle 1971
    F   13 Snow Day—no class  
    M   16 Snow Day—no class  
    W   18 SNePSLOG predicates & function symbols
    for CVA project
    Lehmann et al. (2006)
    F   20 7. Frames B&L, Ch.8
    M   23 Frames (concluded) Minsky 1974
    W   25 8. Description Logics Fikes et al. 1985
    F   27 out of town; no class B&L, Ch. 9
    M   30 Description Logics (cont'd.) Woods 1975
    W Nov 1 Description Logics (concluded) Woods et al. 1992
    F   3 9. Inheritance Networks  
    M   6 Inheritance Nets (cont'd.) B&L, Ch. 10
    W   8 Inheritance Nets (cont'd.) Etherington et al. 1983
    F   10 Last day to resign with "R"
    Inheritance Nets (concluded)
    Thomason 1992
    M   13 Project Reports B&L, Ch. 11
    W   15 10. Default Reasoning Selections from Ginsberg 1987
    (book is on reserve at UGL/SEL)
    F   17 Default Reasoning (cont'd.) Selections from Ginsberg 1987
    (book is on reserve at UGL/SEL)
    M   20 Default Reasoning (cont'd.) Selections from Ginsberg 1987
    (book is on reserve at UGL/SEL)
    W   22 Thanksgiving; no class  
    F   24 Thanksgiving; no class  
    M   27 Default Reasoning (concluded) Martins & Shapiro 1988
    W   29 11. Modal & Epistemic Logics Garson (Oct. 2003)
    F Dec 1 Modal & Ep. Logics (cont'd.) Rapaport 1992
    M   4 Modal & Ep. Logics (cont'd.) Moore 1977
    W   6 Modal & Ep. Logics (concluded)  
    F   8 Last Class:
    Course summary


    "Teachers open the door, but you must enter by yourself." — Chinese Proverb

    "You can lead a horse to water, but you can't make him drink." — American Proverb

    "You can lead a horse to water, but you must convince him it is water before there is any chance he will drink." — Albert Goldfain

    "Education is not filling a bucket, but lighting a fire" — William Butler Yeats


  • For general advice on how to study for any course, see my web page, "How to Study".

  • For advice on how to read a computer science text, see "How to Read (a Computer Science Text)".


    1. You will be expected to attend all lectures, and to complete all readings and assignments on time. There may be occasional homework assignments, and there will be a required term project.

    2. Any homeworks will be announced in lecture. Therefore, be sure to get a classmate's phone number (for instance, 1 or 2 people sitting next to you in class, whoever they are!) so that you will not miss assignments in the unlikely event that you miss a class.

    3. Email list:

      You will automatically be placed on an email list (a "Listserv") for the course. If you do not normally read email at the email address that UB has as your official address, please either do so for this course, or else have your mail forwarded. I will use this list as my main means of communicating with you out of class, and you can use it to communicate with the rest of us.

      You may send questions and comments that are of general interest to the entire class using the Listserv: Just send them to:

      You can also send email just to me, at:

      In any case, be sure to fill in the subject line, beginning with "CSE 663: " so that my mailer doesn't think it's spam.

      If you send email to me that I deem to be of general interest, I will feel free to remail it anonymously to the email list along with my reply unless you explicitly tell me otherwise.

      I will archive the emails at

      For more information, read the Listserv Information webpage.

    4. Just as you cannot expect to learn how to drive a car by reading about it or by watching other people do it, the same holds true for doing computer science. Do your work on time—this is one course you simply cannot cram for at the last minute, so don't even try! I cannot stress this strongly enough. The project, especially, may be fairly time-consuming, so please consider your other commitments, and plan your time accordingly.

    5. Students should notify Prof. Rapaport within the first two weeks of class if they have a disability which would make it difficult to carry out course work as outlined (requiring note-takers, readers, extended test time).


    1. The default term project for the course is to take a paragraph of text (in most cases, to be provided by me) containing an "unknown" word, to represent that passage in SNePS, together with any background information (including "rules") that would be needed to figure out ("compute") a meaning for that word. This is part of our Contextual Vocabulary Acquisition project.

    2. Programming Languages, Lisp, and Unix:

      One prerequisite for this course is knowledge of any high-level programming language.

      But you are strongly advised to (learn and) use Lisp if you intend to do any research in AI. Moreover, there are good reasons to learn Lisp even if you want to make it in the real world of e-commerce; see:

      1. Paul Graham's Lisp Resources

      2. St. Amant, Robert, & Young, R. Michael (2001), "Common Lisp Resources on the Web" (PDF), intelligence 12(3): 21-23.

      3. ... and, especially, Graham, Paul (2001), "Beating the Averages".

      4. NEW
        You might also be interested in:
        Gabriel, Richard P. (1991), "Lisp: Good News, Bad News, How to Win Big"

      If you decide to use Lisp: The implementation of Lisp for this course is Allegro Common Lisp (acl), which runs under the Unix operating system. You will be expected to learn the idiosyncrasies of Allegro Common Lisp on your own (Shapiro's text should be of help). For more information on Lisp, see Marty Hall's "An Introduction and Tutorial for Common Lisp" website.

    3. SNePS:

      We will discuss the SNePS knowledge representation and reasoning system in class, but those of you who do not already know it should work through the SNePSUL Tutorial and/or the SNePSLOG Introduction at

      as soon as possible.

    4. You should have an account on the Grad Lab machines. If you do not have access to these machines, please let me know as soon as possible! You will be expected to learn how to use Unix, emacs, etc., on your own. CIT offers short courses on Unix, etc. To contact CIT:
      in person:216 Computing Center
      by phone:645-3542
      by fax:645-3617
      on the Web:

    5. Project Policies:


    Your final course grade will be a weighted average (probably 50-50) of:
    1. your class attendance, class participation, and homeworks, and
    2. your grade on the project.

    For further information, see my web document on "How to Grade"


    It is University policy that a grade of Incomplete is to be given only when a small amount of work or a single exam is missed due to circumstances beyond the student's control, and that student is otherwise doing passing work. I will follow this policy strictly! Thus, you should assume that I will not give incompletes :-)

    Any incompletes that I might give, in a lapse of judgment :-), will have to be made up by the end of the
    Spring 2007

    For more information on Incomplete policies, see the Graduate School web page, "Incomplete Grades".


    While it is acceptable to discuss general approaches with your fellow students, the work you turn in must be your own. It is the policy of this department that any violation of academic integrity will result in an F for the course, that all departmental financial support including teaching assistanceship, research assistanceship, or scholarships be terminated, that notification of this action be placed in the student's confidential departmental record, and that the student be permanently ineligible for future departmental financial support. If you have any problems doing the assignments, consult Prof. Rapaport. Please be sure to read the webpage, "Academic Integrity: Policies and Procedures", which spells out all the details of this, and related, policies.


    In large classes (but not such as this:-), students have been known to be disruptive, either to the instructor or to fellow students. The university's policies on this topic, both how the instructor should respond and how students should behave, may be found in the document
    "Obstruction or Disruption in the Classroom".

    Copyright © 2006 by William J. Rapaport (
    file: 663/F06/syl-20061113.html