leff@smu.CSNET (Laurence Leff) (06/06/87)
Abstracts of papers in Computational Intelligence 3(2), May 1987 Expressiveness and tractability in knowledge representation and reasoning Hector J. Levesque and Ronald J. Brachman A fundamental computational limit on automated reasoning and its effect on knowledge representation is examined. Basically, the problem is that it can be more difficult to reason correctly with one representational language than with another and, moreover, that this difficulty increases dramatically as the expressive power of the language increases. This leads to a tradeoff between the expressiveness of a representational language and its computational tractability. Here we show that this tradeoff can be seen to underlie the differences among a number of existing representational formalisms, in addition to motivating many of the current research issues in knowledge representation. Go\*:del, Lucas, and mechanical models of the mind Robert F. Hadley In \fIMinds, Machines, and Go\*:del\fP, J.R. Lucas offers an argument, based on Go\*:del's incompleteness theorems, that the mind cannot be modelled by a machine. This argument has generated a variety of alleged refutations, some of which are incompatible with others. It is argued here that the incompatibility of these `refutations' points to a central paradox which has not yet been resolved. A solution to this paradox is presented, and a related paradox, concerning the existence of consistent models for inconsistent humans, is described and solved. An argument is presented to demonstrate that although humans commonly produce inconsistent output, they can, in an important sense, be modelled by \fIconsistent\fP formal systems, if their behavior is deterministic. It is also shown that Go\*:del's results present no obstacle to humans' proving the consistency of their own formal models. Domain circumscription: A re-evaluation David W. Etherington and Robert Mercer Some time ago, McCarthy developed the domain circumscription formalism for closed-world reasoning. Recently, attention has been directed towards other circumscriptive formalisms. The best-known of these, predicate and formula circumscription, cannot be used to produce domain-closure axioms; nor does it appear likely that the other forms can. Since these axioms are important in deductive database theory (and elsewhere), and since domain circumscription often can conjecture these axioms, there is reason to resurrect domain circumscription. .25 Davis presents an intuitively appealing semantics for domain circumscription, based on minimal models. However, under certain conditions McCarthy's syntactic realization of domain circumscription can induce inconsistencies in consistent theories with minimal models. We present a simple, easily motivated change that corrects this problem but retains the appealing semantics outlined by Davis. We also explore some of the repercussions of this semantics, including soundness and limited completeness results. Defeat among arguments: A system of defeasible inference R.P. Loui This paper presents a system of non-monotonic reasoning with defeasible rules. The advantage of such a system is that many multiple extension problems can be solved without additional explicit knowledge; ordering competing extensions can be done in a natural and defensible way, via syntactic considerations. The objectives closely resemble Poole's objectives, but the logic is different from Poole's. The most important difference is that this system allows the kind of chaining that many other non-monotonic systems allow. Also, the form in which the inference system is presented is quite unusual. It mimics an established system of inductive logic, and it treats defeat in the way of the epistemologist-philosophers. The contributions are both of content and of form: the kinds of defeat that are considered, and the way in which defeat is treated in the rules of inference. A hybrid, decidable, logic-based knowledge representation system Peter F. Patel-Schneider The major problem with using standard first-order logic as a basis for knowledge representation systems is its undecidability. A variant of first-order tautological entailment, a simple version of relevance logic, has been developed that has decidable inference and thus overcomes this problem. However, this logic is too weak for knowledge representation and must be strengthened. One way to strengthen the logic is create a hybrid logic by adding a terminological reasoner. This must be done with care to retain the decidability of the logic as well as its reasonable semantics. The result, a stronger decidable logic, is used in the design of a hybrid, decidable, logic-based knowledge representation system. Patterns of interaction in rule-based expert system programming Stan Raatz and George Drastal We study the effect of adding a rule to a rule-based heuristic classification expert system, in particular, a rule which causes an unforeseen interaction with rules already in the rule set. We show that it is possible for such an interaction to occur between \fIsets\fP of rules, even when no interaction is present between any \fIpair\fP of rules contained in these sets. A method is presented that identifies interactions between sets of rules, and an analysis is given which relates these interactions to rule-based programming practices which help to maintain the integrity of the knowledge base. We argue that the method is practical given some reasonable assumptions on the knowledge base. \fISubscription information\fP Computational Intelligence is published by the National Research Council of Canada and sponsored by CSCSI. Non-institutional members may subscribe for $Cdn16, a considerable discount on the regular price. To join CSCSI, send $Cdn25 to CSCSI c/o CIPS, 243 College Street (5th floor), Toronto, CANADA M5T 2Y1. If you wish to subscribe without joining CSCSI, write to: Distribution R-88 National Research Council of Canada, Ottawa, Ontario, CANADA K1A 0R6. Regular rates are $Cdn37 for individuals, $Cdn75 for libraries; add $10 extra for postage outside Canada. Make cheques payable to ``Receiver General of Canada, credit NRCC''.