The Hearsay-H speech-understanding system (SUS) developed at Carnegie-Mellon University recognizes connected speech in a 1000-word vocabulary with correct interpretations for 90 percent of test sentences. Its basic methodology involves the application of symbolic reasoning as an aid to signal processing. A marriage of general artificial intelligence techniques with specific acoustic and linguistic knowledge was needed to accomplish satisfactory speech-This research was supported chiefly by Defense Advanced Research Projects Agency contract F44620-73- C-0074 to Carnegie-Mellon University. In addition, support for the preparation of this paper was provided by USC/ISI, Rand, and the University of Massachusetts. We gratefully acknowledge their support. Views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official opinion or policy of DARPA, the U.S. government, or any other person or agency connected with them.

This research was supported at SRI International by the Defense Advanced Research Projects Agency under contract N00039--79--C--0118 with the Naval Electronic Systems Command. The views and conclusions contained in this document are those of the author and should not be interpreted as representative of the official policies either expressed or implied of the Defense Advanced Research Projects Agency, or the U. S. Government. The author is grateful to Barbara Grosz, Gary Hendrix and Terry Winograd for comments on an earlier draft of this paper.

Assume we have the following transformation rules that define integer multiplication: 0. v 0

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

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.

Human programmers seem to know a lot about programming. This suggests a way to try to build automatic programming systems: encode this knowledge in some machine-usable form. In order to test the viability of this approach, knowledge about elementary symbolic programming has been codified into a set of about four hundred detailed rules, and a system, called PECOS, has been built for applying these rules to the task of implementing abstract algorithms. The implementation techniques covered by the rules include the representation of mappings as tables, sets of pairs, property list markings, and inverted mappings, as well as several techniques for enumerating the elements of a collection. The generality of the rules is suggested by the variety of domains in which PECOS has successfully implemented abstract algorithms, including simple symbolic programming, sorting, graph theory, and even simple number theory. In each case, PECOS's knowledge of different techniques enabled the construction of several alternative implementations. In addition, the rules can be used to explain such programming tricks as the use of property list markings to perform an intersection of two linked lists in linear time. Extrapolating from PECOS's knowledge-based approach and from three other approaches to automatic programming (deductive, transformational, high level language), the future of automatic programming seems to involve a changing role for deduction and a range of positions on the generality-power spectrum.

... we began to program a computer understanding system thatwould attempt to process input texts. An item crucial to our ability to accomplishthis task was what we called a script. A script is a frequently repeated causalchain of events that describes a standard situation. In understanding, when it ispossible to notice that one of these standard event chains has been initiated,then it is possible to understand predictively. That is, if we know we are in arestaurant then we can understand where an "order" fits with what we justheard, who might be ordering what from whom, what preconditions (menu,sitting down) might have preceded the "order", and what is likely to happennext. All this information comes from the restaurant script.Hayes, J.E., D. Michie, and L. I. Mikulich (Eds.), Machine Intelligence 9, Ellis Horwood.

I will remain Ion8 and deeply indebted to Herb Simon, H. T. Kung, AI Newell, Jay

"Computing can change our ways of thinking about many things, mathematics, biology, engineering, administrative procedures, and many more. But my main concern is that it can change our thinking about ourselves: giving us new models, metaphors, and other thinking tools to aid our efforts to fathom the mysteries of the human mind and heart. The new discipline of Artificial Intelligence is the branch of computing most directly concerned with this revolution. By giving us new, deeper, insights into some of our inner processes, it changes our thinking about ourselves. It therefore changes some of our inner processes, and so changes what we are, like all social, technological and intellectual revolutions." This book, published in 1978 by Harvester Press and Humanities Press, has been out of print for many years, and is now online, produced from a scanned in copy of the original, digitised by OCR software and made available in September 2001. Since then a number of notes and corrections have been added. Atlantic Highlands, NJ: Humanities Press.

For example, lnterlisp permits accessing the control stack at an unusually detailed level.