Seminar Dynamics of Knowledge and Belief SS 2014

Monday, Jan 6, 2014

In this seminar we will study several modeling and reasoning techniques for knowledge and belief in dynamic systems. Knowledge is an important aspect of intelligent programs: while most of today’s systems assume a closed world, i.e., everything they don’t know to be true is assumed to be false, an intelligent system needs to consider possible that there are truths not known to the system. In a dynamic environment, i.e., an environment where one or multiple agents (inter)act, the system will usually have to acquire new knowledge through sensing. Potentially it may even revise its beliefs when it realizes some beliefs were wrong. In this seminar we will study various aspects of action, knowledge, and belief.

We plan to implement a peer review process for this seminar. That is, every student will read some other students’ term paper and provide feedback in form of a written review. This shall not only deepen your understanding of the other topics, but it also introduces you to the academic review process.


Students of Bachelor and Master programs can participate in this seminar. For Master Informatik students, the seminar belongs to the fields Theoretische Informatik and Daten- und Informationsmanagement. For Master Software Systems Engineering (SSE) students, it belongs to the fields Theoretical Foundations of SSE and Data and Information Management.

Places are allocated centrally from 14.01.2014 until 26.01.2014. Please clearly indicate why you want to join this particular seminar and your prior knowledge of the subject within the above mentioned registration process. We won’t be able to consider your application otherwise. The number of available slots is limited.


A thorough knowledge of logic and knowledge representation is absolutely essential. Relevant courses include the Mathematical Logic course from the Mathematical Foundations of Computer Science group and our lectures on Knowledge Representation.


This is the preliminary list of topics and selected related papers.

  • Knowledge and Action:
    • Knowledge, Action, and the Frame Problem by Scherl and Levesque PDF
    • A simple and tractable extension of Situation Calculus to Epistemic Logic by Demolombe and Parra PDF
    • Knowledge Equivalence in Combined Action Theories by Petrick and Levesque PDF
    • On Knowledge-Based Programming with Sensing in the Situation Calculus by Reiter PDF
  • Progression:
    • Forget It! by Lin and Reiter PDF
    • How to Progress a Database (and Why) I. Logical Foundations by Lin and Reiter PDF
    • First-Order Strong Progression for Local-Effect Basic Action Theories by Vassos, Lakemeyer and Levesque PDF
    • On the Progression of Situation Calculus Basic Action Theories: Resolving a 10-year-old Conjecture by Vassos and Levesque PDF
  • Classic Belief Revision:
    • On the Logic of Theory Change: Partial Meet Contraction and Revision Functions PDF
    • On the Logic of iterated Belief Revision PDF
    • Propositional knowledge base revision and minimal change PDF
    • Two Modellings for Theory Change PDF
  • Belief Revision under Action:
    • Knowledge, Action, and the Frame Problem by Scherl and Levesque PDF
    • Iterated belief change in the situation calculus by Shapiro, Pagnucco, Lespérance and Levesque PDF
    • Belief revision in the Situation Calculus without plausibility levels by Demolombe and Parra PDF
  • Proper Knowledge Bases:
    • A Completeness Result for Reasoning with Incomplete First-Order Knowledge Bases by Levesque PDF
    • Evaluation-Based Reasoning with Disjunctive Information in First-Order Knowledge Bases by Lakemeyer and Levesque PDF
    • Tractable Reasoning with Incomplete Knowledge in Dynamic Systems by Liu and Levesque PDF
    • Efficient Reasoning in Multiagent Epistemic Logics by Lakemeyer and Lespérance PDF
  • Noisy Sensors:
    • Reasoning about Noisy Sensors and Effectors in the Situation Calculus by Bacchus, Halpern and Levesque PDF
    • Reasoning about Continuous Uncertainty in the Situation Calculus by Belle and Levesque PDF
  • Modal Situation Calculus:
    • A semantic characterization of a useful fragment of the situation calculus with knowledge by Lakemeyer and Levesque PDF
    • A Semantical Account of Progression in the Presence of Defaults by Lakemeyer and Levesque PDF
    • Reasoning about Imperfect Information Games in the Epistemic Situation Calculus by Belle and Lakemeyer PDF
  • Planning and sensing:
    • What is Planning in the Presence of Sensing? by Levesque PDF
    • An Incremental Interpreter for High-Level Programs with Sensing by De Giacomo and Levesque PDF
  • Limited Belief:
    • A Logic of Limited Belief for Reasoning with Disjunctive Information PDF
    • Tractable First-Order Golog with Disjunctive Knowledge Base PDF
    • Decidable Reasoning in a Logic of Limited Belief with Introspection and Unknown Individuals PDF
    • Decidable Reasoning in a Fragment of the Epistemic Situation Calculus
  • Continual Planning:
    • Continual Planning and Acting in dynamic Multiagent Environments PDF
    • A Switching Planner for Combined Task and Observation Planning PDF
    • Continual Planning for Cross-Modal Situated Clarification in Human-Robot Interaction PDF
  • Conformant Planning:
    • Expressive Planning and Explicit Knowledge PDF
    • Conformant Graphplan PDF
    • A Logic Programming Approach to Knowledge-State Planning, II: The DLV^K System PDF
    • Planning with Incomplete Information as Heuristic Search in Belief Space PDF

Additional information

Introductory Meeting

  • The date and time for the introductory meeting will be announced here. Participation is compulsory.

Seminar Procedure

  • Besides writing your own term paper, you are asked to review other students’ term papers. We will use a conference management system (e.g., EasyChair) for this procedure. It will involve strict deadlines. Meeting these deadlines is mandatory. At the end of the seminar each student needs to give a talk on his topic in front of the other students and members of our group. Attendance of these talks and participation in the discussions is mandatory.

Seminar Date

  • The seminar will be held as a block seminar on two or three days, likely during the semester break.


General Info

Library Tour

  • The Computer Science Library offers guided tours on how to find literature in the library and how to prepare a seminar. Interested students should enlist for a tour in the preliminary discussion.