Knowledge Based Systems (KBSs) constitute an important area of contemporary research in artificial intelligence. I chose this as my area of research because it involves the modeling of issues that are central in the study of cognition, a topic that has long fascinated me; because it draws heavily from the field of mathematical logic in which my training is very strong; and because it has a wide spectrum of applications in computer science, including intelligent databases, expert systems and robotics.
When initially conceived, KBSs containing only positive information were considered. No negated information can be inferred from these systems unless some strategy or rule for default negation is adopted. A rule for default negation establishes when it is sound to conclude the negation of a statement in the absence of information forcing the statement to be true. It models the way humans reason when they jump to conclusions based on incomplete information. Several default rules have been proposed. Some of them concentrate only on the epistemological soundness of the conclusions they derive while others also address the issue of computational complexity. Traditionally, each application has chosen only one of these rules and has applied it to every piece of data in the domain of the application. However, in commonsense reasoning, we can see that there are situations in which it is not possible to use a single default method to deduce negated information. If we are, for instance, reasoning about a museum, we probably would conclude that the museum does not open on Mondays from the statement ``the museum opens from Tuesday to Sunday'', but we hardly would infer that no paintings by Picasso are exhibited in the museum when the only information we have is that the museum is running a special exhibition of paintings by Matisse.
The purpose of my doctoral dissertation is to introduce and investigate formalisms that admit several forms of default negation which interact with each other and with classical (or ``explicit'') negation in the same application. Some theoretical aspects of this research include the investigation of the expressive power of the new formalisms and the characterization of their semantics. Practical issues include implementing procedures to compute in these formalisms, calculating the computational complexity of different reasoning tasks under the proposed semantics and modeling real life applications. One example is the problem of merging several knowledge bases, each of which uses a different rule for negation, and finding answers to queries in the combined knowledge base.
Certainly, such a study should open the door to a new approach to the understanding and use of negation in non-monotonic reasoning and KBSs and will have immediate applications to practical problems such as planning, deductive databases and knowledge base merging.
In accordance with the above objectives, I have made the following contributions.
This paper studies the interaction between clasical negation and an arbitrary rule of negation by default in a special class of KBSs containing indefinite information, called disjunctive logic programs. It describes model, fixpoint, and proof theoretic characterizations of the semantics of these KBSs.
This paper extends the results obtained in the above paper by describing general techniques applicable to any semantics of KBSs. It pays particular attention to the expressive power and the computational complexity of these KBSs.
The problem of whether or not one of the most important semantics for KBSs, called the partial stable model semantics, is computable, was open for several years. This paper provides a positive answer to this problem by providing a new characterization of this semantics that yields an effective procedure for its computation. This allows the semantics to be not only of theoretical importance but also of practical use in real life applications.
This paper introduces a new class of KBSs containing two forms of default negation in addition to classical negation and investigates their semantics. An effective procedure to compute the proposed semantics is given. Also, the complexities of different reasoning tasks under this semantics are discussed. Applications to knowledge representation and knowledge base merging are presented.
I am presently working on extending these results to more general classes of KBSs containing several forms of default negation; to implement a system allowing for the application of this theory to solve concrete problems in knowledge representation and commonsense reasoning; and to study the expressive power of the obtained system.