This paper is concerned primarily with (1) the procedure by which process-oriented specifications are obtained from goal-oriented requirement specifications and (2) computer-based tools for their construction. It first determines some attributes of a suitable process-oriented specification language, then examines the reasons why specifications would still be difficult to write in such a language. The key to overcoming these difficulties seems to be the careful introduction of informality based on partial, rather than complete, descriptions and the use of a computer-based tool that uses context extensively to complete these descriptions during the process of constructing a well-formed specification. Some results obtained by a running prototype of such a computer-based tool on a few informal example specifications are presented and, finally, some of the techniques used by this phototype system are discussed.

THE REPRESENTATION AND USE OF FOCUS IN A SYSTEM FOR UNDERSTANDING DIALOGS Barbara J. Grosz Artificial Intelligence Center SRI International, Menlo Park, California 94025 ABSTRACT As a dialog progresses the objects and actions that are most relevant to the conversation, and hence in the focus of attention of the dialog participants, change. This paper describes a representation of focus for language understanding systems, emphasizing its use in understanding taskoriented dialogs. The representation highlights that part of the knowledge base relevant at a given point in a dialog. A model of the task is used both to structure the focus representation and to provide an index into potentially relevant concepts in the knowledge base The use of the focus representation to make retrieval of items from the knowledge base more efficient is described. I INTRODUCTION To understand the sentences in a discourse, a computer system, like a person, must have knowledge about the domain of the discourse. However, the knowledge required to understand even simple, reallife domains is so extensive that it will overwhelm a system that does not apply it selectively. This means that the ability to focus on the subset of knowledge relevant to a particular situation is crucial. This paper addresses the problem of focus from the perspective of building a computer system that can participate in a task-oriented dialog. A representation for focus is presented; its use is illustrated by showing how the referents of definite noun phrases are identified. A combination of contextual factors influences the interpretation of an utterance. In fact, what is usually meant by "the context of an utterance" is precisely that set of constraints which together direct attention to the concepts of interest in the discourse in which the utterance occurs. Both the preceding discourse context - - the utterances that have already occurred -- and the situational context -- the environment in which an utterance occurs -- affect the interpretation of the utterance. For a dialog, the situational context includes the physical environment, the social setting, and the relationship between the participants in the dialog. This paper shows how the task and dialog contexts combine to provide a focus on those concepts relevant to the interpretation of utterances in task-oriented dialogs.

We here discuss insights gained about the structure of evaluation functions for a large domain such as backgammon. Evaluation began as a single linear polynomial of backgammon features. Later, we introduced Mate-classes, each with its own evaluation function. This improved the play, but caused problems with odge-effects between state-classes. Our latest effort uses models of position potential to select across the set of best members of each represented state-class. "This has produced a significant jump in performance of BKG. Because of the localization of knowledge, state-classes permit relatively easy modification of knowledge used in evaluation. They also permit the building of opponent models based upon what evidence shows the opponent knows in each state-class.

Abstract: It has been claimed that production systems have several advantages over other representational schemes. These include the potential for general self-augmentation (i.e., learning of new behavior) and the ability to function in complex environments. The production system language, OPS, was implemented to test these claims. In this paper we explore some of the issues that bear on the design of production system languages and try to show the adequacy of OPS for its intended purpose. I. INTRODUCTION Much of the work that has been done with production systems during the past few years has had as its primary goal the development of systems that are expert in some particular task. The tasks so far addressed include: chemical inference [Buchanan and Lederberg, J 971], medical diagnosis [Davis, Buchanan, and Shortliffe, 1975], discovery in mathematics [Lenat, 1976], speech recognition [Erman and Lesser, 1975; McCracken, 1977], and automatic programming [Barstow, 1977]. Although many of these systems have shown impressive power in the particular task for which they were designed, there remains a question of how suitable the production system representation is for large general problem solving programs. The Instructable Production System (IPS) project at CMU [Rychener and Newell, 1977] is attempting to answer this question. It has been claimed that production systems are capable of learning in a nontrivial way. If this is true, a production system should be able to learn not only facts, but also new behaviors.

Hierarchies are observed in the levels of description used in image understanding along a few dimensions: processing unit, detail, composition and scene/view distinction. Emphasis is placed on the importance of explicitly handling the hierarchies both in representing knowledge and in using it. A scheme of "knowledge block" representation which is structured along the processing-unit hierarchy is also presented. I. INTRODUCTION Image Understanding System(IUS) constructs a description of the scene being viewed from an array of image sensory data: intensity, color, and sometimes range data. Image understanding is best characterized by description, whereas pattern recognition by classification, and image processing by image output.

I shall refer to such restrictions as preference restrictions, because of the way the present NLUS is already able to accept natural language that violates preferences, as (1) does (see recap in next section for more detail). Such usage as (s) will be referred to as extended, or preference violating, and these will serve instead of the more literary and philosophical term "metaphorical". It is an important assumption of this paper that such usage is the norm in ordinary everyday language use, and cannot be relegated to the realm of the exceptional, or the odd, and so dealt with by considerations of "performance". On the contrary it is, I would argue, central to our language capabilities, and any theory of language must have something concrete to say about it. Even if the newspaper usages above are "extended", I would suggest that anyone who could not grasp these extension could not be said to understand English properly (given adequate knowledge from which to extend, and we shall come to that.) It will be obvious already that the commitment to a norm implies a corresponding commitment to general everyday language as a proper topic for Al.

In English, "1ikewise", "too", "similarly", etc., followed optionally by a preposition and then by a noun phrase indicate that the role filled by the new noun phrase in a previously mentioned predicate is a non-subject one.

Experimental measurements (figure 1) reveal reduction by a factor of 2.5 for the 8-queens puzzle (factor of 8.7 for 16 queens) in T, the number of pair-tests performed before finding a solution (i.e., first solution). " seconds, net speedup is by a factor of 2.0 and 6.0 for 8-and 16-queens, respectively. The speedup can be attributed to the elimination of almost all redundant tests otherwise recomputed in many parts of the search tree, as indicated in figure 2, which shows the mean number of times, D, an arbitrary pair-test is executed. If D 1 then all tests are distinct (no recomputatiOn). Note that each data point in the figures represents the mean over 30 or 70 problem instances that differ as follows: instead of instantiating queen 3, say, on square (3,1), then on (3,2),..., then (3,8), these 8 squares are ordered randomly.

U.S.A. Abstract: This paper presents a discussion of means of describing the discourse and its components which makes speech act interpretation and anaphora disambiguation possible with minimal search of the knowledge in the database. A portion of this paper will consider how a frames representation of sentences and common sense knowledge provides a mechanism for representing the postulated discourse components. Finally some discussion of the use of the discourse model and of frames in a discourse understanding program for a personal assistant will be presented. Introduction The person who communicates with a personal assistant, whether human or machine, wants to request some action of the assistant via sentences in English. Generally, a single sentence is insufficient to capture all the information that is to be given as well as an unnatural way to make a request. However, as several example dialogues below will show, the human user does not tightly relate the sentences s/he speaks about a particular subject. It is instead the job of the hearer to interpret how the incoming sentence is related to the previous discourse. Each sentence or clause of a discourse that makes some demand upon the hearer must be interpreted for the kind of demand being made. These demands are generally referred to as speech acts {1}. However, the speech acts are not just strings of individual requests. They have a connecting pattern which the hearer must extract as the discourse goes on. Thus the hearer's task is twofold: to interpret the speech act in a clause and to relate that speech act to the overall discourse. In this paper this two-pronged task will be referred to as speech act interpretation. Closely associated with speech act interpretation is the process of understanding what the various noun and pronoun phrases of the incoming sentence refer to. Speakers denote previously mentioned objects in a variety of ways with apparent ambiguity in the choice of referents.

A range of different encoding techniques have been developed, along with a number of approaches to applying knowledge. Most of the effort to date, however, has concentrated on representing and manipulating knowledge about a specific domain of application, like game-playing ([14]), natural language understanding ([15], [19]), speech understanding ([8], [11]), chemistry ([7]), etc. This paper explores a number of issues involving representation and use of what we term meta-level knowledge, or knowledge about knowledge. It begins by defining the term, then exploring a few of its varieties and considering the range of capabilities it makes possible. Four specific examples of meta-level knowledge are described, and a demonstration given of their application to a number of problems, including interactive transfer of expertise and guiding the use of knowledge. Finally, we consider the long term implications of the concept and its likely impact on the design of large programs.