Reasoning with model-based belief revision semantics: Theory and implementation
Chou, Seng-cho Timothy
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/22706
Description
Title
Reasoning with model-based belief revision semantics: Theory and implementation
Author(s)
Chou, Seng-cho Timothy
Issue Date
1992
Doctoral Committee Chair(s)
Winslett, Marianne
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
Abstract
Belief revision semantics appear promising as a definition for the meaning of updates to logical knowledge bases. Numerous model-based belief revision semantics have been proposed in the literature in recent years. It is not at all clear, however, how to translate a proposed model-based semantics into a procedure suitable for implementation. As a result, it becomes hard for one to analyze and identify the practical limits of these revision semantics. In this thesis, we propose an architecture for implementing model-based theory revision semantics, discuss the major algorithms implemented in our prototype system, Immortal, analyze the complexity of the algorithms, and report some results from the implementation of the algorithms. The key feature of our algorithms, as shown in the complexity analysis, is that while belief revision is intractable in general, the expected running time of our algorithms will be polynomial for many interesting cases.
The proposals for these revision semantics to date do not fully support updates involving equality. This thesis extends model-based update semantics to support updates involving equality, by permitting changes in both universe composition and in function interpretations in the models being updated. These theoretical extensions are needed for problems in more complex domains. Adding equality into our prototype system presents some new challenges. In particular, revision problems involving equality will have much larger domains of discourse with more relationships among objects to record and remember. We discuss the necessary extensions in detail.
The contributions of this thesis can be summarized as follows: (1) reduce the theoretical revision semantics into an actual implementation based on a set of algorithms which are proven correct; (2) show that the implementation can be practically used in certain interesting problems and that the implemented heuristics actually work efficiently for certain problems; (3) extend model-based revision semantics to handle equality in terms of changes in function interpretations and universe compositions, making the semantics useful for more complex problems; and (4) equip Immortal with a generic capability for handling equality and changes in the composition of relevant terms of models, an important step towards making the implementation suitable for full-blown first order theories.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
