Cambridge, Mass.: MIT Press. See also: An Overview of a Theory of Syntactic Recognition for Natural Language. MIT AIM-531. 1979 (http://dspace.mit.edu/handle/1721.1/6316).

This is a short preview of the document. Your library or institution may give you access to the complete full text for this document in ProQuest.

To choose their actions, reasoning programs must be able to make assumptions and subsequently revise their beliefs when discoveries contradict these assumptions. The Truth Maintenance System (TMS) is a problem solver subsystem for performing these functions by recording and maintaining the reasons for program beliefs. Such recorded reasons are useful in constructing explanations of program actions and in guiding the course of action of a problem solver. This paper describes (1) the representations and structure of the TMS, (2) the mechanisms used to revise the current set of beliefs, (3) how dependency-directed backtracking changes the current set of assumptions, (4) techniques for summarizing explanations of beliefs, (5) how to organize problem solvers into "dialectically arguing" modules, (6) how to revise models of the belief systems of others, and (7) methods for embedding control structures in patterns of assumptions. We stress the need of problem solvers to choose between alternative systems of beliefs, and outline a mechanism by which a problem solver can employ rules guiding choices of what to believe, what to want, and what to do.Artificial Intelligence 12(3):231-272

In J. E. Hayes, D. Michie, and L. I. Mikulich (Eds.), Machine Intelligence 9. Chichester, England: Ellis Horwood Ltd., 149-195

A programming language needs simple and well defined semantics. The two favoured theoretical bases for languages have been lambda calculus as advocated by Landin and others, and predicate calculus as advocated by Kowalski (see Landin (1966) and Kowalski (1973)). In this paper I adopt an approach based on predicate calculus, but in a manner that differs from the existing PROLOG language (Warren 1975 and Battani & Meloni 1973) in that I adopt a "forward inference" approach -- inferring conclusions from premises, rather than the "backward inference" approach of PROLOG, which starts with a desired conclusion and tries to find ways of inferring it. This difference is reflected in the internal structure of the associated implementations, that of PROLOG being a "backtrack search" kind of implementation, while the most obvious implementation of the system proposed here involves a kind of mass operation on tables of data, reminiscent of APL (Iverson 1962) but in fact identical in many respects with the work of Codd (Codd 1970) on relational data bases. Indeed, from one perspective this paper can be seen as an extension of Codd's work into the realm of general purpose computing. As in the case of PROLOG it is necessary for the user of the relational programming system to make statements which are not associated with the logical structure of the problem, but reflect the need to control the computation. In PROLOG these are effected by the use of extra-logical control primitives, but in our system control is exercised by the introduction of predicates for that purpose, which have exactly the same semantics as the predicates relevant to the logical structure of the problem.

Minsky introduced the terminology of'frames' to unify and denote a loose collection of related ideas on knowledge representation: a collection which, since the publication of his paper (Minsky, 1975) has become even looser. It is not at all clear now what frames are, or were ever intended to be. I will assume, below, that frames were put forward as a (set of ideas for the design of a) formal language for expressing knowledge, to be considered as an alternative to, for example, semantic networks or predicate calculus. At least one group have explicitly designed such a language, KRL (Bobrow/ Winograd, 1977a, 19776), based on the frames idea. But it is important to distinguish this from two other possible interpretations of what Minsky was urging, which one might call the metaphysical and the heuristic (following the terminology of (Mc Carthy/Hayes, 1968)). The "metaphysical" interpretation is, that to use frames is to make a certain kind of assumption about what entities shall be assumed to exist in the world being described.

Our purpose in studying natural language understanding in conjunction with problem solving is to bring together the constraints of what formal representation can actually be obtained with the question of what knowledge is required in order to solve a wide range of problems in a semantically rich domain. We believe that these issues cannot sensibly be tackled in isolation. In practical terms we have had the benefits of an increased awareness of common problems in both areas and a realisation that some of our techniques are applicable to both the control of inference and the control of parsing. Early work on solving mathematical problems stated in natural language was done by Bobrow (STUDENT - (i]) and Chamiak (CARPS - [5]). However the rudimentary parsing and simple semantic structures used by Bobrow and Charniak are inadequate for any but the easiest problems. Our intention has been to build on B/RG Chris This work was supported by SRC grant number 94493 and an SRC research studentship for Mellish.

We discuss the problem of incorporating into a heuristic theorem prover a decision procedure for a fragment of the logic. An obvious goal when incorporating such a procedure is to reduce the search space explored by the heuristic component of the system, as would be achieved by eliminating from the system's data base some explicitly stated axioms. For example, if a decision procedure for linear inequalities is added, one would hope to eliminate the explicit consideration of the transitivity axioms. However, the decision procedure must then be used in all the ways the eliminated axioms might have been. The difficulty of achieving this degree of integration is more dependent upon the complexity of the heuristic component than upon that of the decision procedure. The view of the decision procedure as a black box is frequently destroyed by the need pass large amounts of search strategic information back and forth between the two components.

Summary of Ph.D. dissertation, Computer Science Dept., Stanford University (1979)."TEIRESIAS is a program designed to provide assistance on the task of building knowledge-based systems. It facilitates the interactive transfer of knowledge from a human expert to the system, in a high level dialog conducted in a restricted subset of natural language. This paper explores an example of TEIRESIAS in operation and demonstrates how it guides the acquisition of new inference rules. The concept of meta-level knowledge is described and illustrations given of its utility in knowledge acquisition and its contribution to the more general issues of creating an intelligent program."Also in:Readings in Artificial Intelligence, ed. Webber, Bonnie Lynn and Nils J. Nilsson, Palo Alto, CA: Tioga Publishing Co., 1981.Orig. in IJCAI-77, vol.1, pp. 321 ff. Preprint in Stanford HPP Report #HPP-77-9.See also: Artificial Intelligence, 12[#2]:409-427. Readings in Artificial Intelligence, ed. Webber, Bonnie Lynn and Nils J. Nilsson, Palo Alto, CA: Tioga Publishing Co., 1981

Distributed systems are multiprocessor information processing systems which do not rely on the central shared memory for communication. The importance of distributed systems has been growing with the advent of "computer networks" of a wide spectrum: networks of geographically distributed computers at one end, and tightly coupled systems built with a large number of inexpensive physical processors at the other end. Both kinds of distributed system are made available by the rapid progress in the technology of large-scale integrated circuits. Yet little has been done in the research on semantics and programming methodologies for distributed information processing systems. Our main research goal is to understand and describe the behaviour of such distributed systems in seeking the maximum benefit of employing multiprocessor computation schemata. The contribution of such research to Artificial Intelligence is manifold. We advocate an approach to modelling intelligence in terms of cooperation and communication among knowledge-based problem-solving experts.