%A J. F. RULIFSON
%A J. A. DERKSEN
%A R. J. WALDINGER
%T QA4: A PROCEDURAL CALCULUS FOR INTUITIVE REASONING
%R Technical Note 73
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1972
%X This report presents a language, called QA4, designed
to facilitate the construction of problem-solving systems used for
robot planning, theorem proving, and automatic program synthesis and
verification. QA4 integrates an omega-order logic language with
canonical composition, associative retrieval, and pattern matching of
expressions; process-structure programming; goal-directed searching;
and demons. Thus it provides many useful programming aids. More
importantly, however, it provides a semantic framework for common
sense reasoning about these problem domains. The interpreter for the
language is extraordinary general, and is therefore an adaptable tool
for developing the specialized techniques of intuitive, symbolic
reasoning used by the intelligence system.
 Chapter One is an informal introduction to the unusual
programming concepts available in the QA4 language. Chapter Two is a
primer for the language. It informally presents the language through
the use of examples. Most of the unusual or complicated features of
the language are not discussed. The chapter concludes with a
presentation of a small robot planning system that uses only the
language features presented in the chapter. Chapter Three presents a
series of examples chosen to illustrate solutions to automatic
programming problems. The QA4 programs used in Chapter Three rely on
language features not presented in the primer. They are, however,
explained as they occur. These programs illustrate most of the
programming concepts just discussed. Chapter Four is a complete
reference guide to the language. It provides the semantics of all the
features of the language together with many implementation notes and
design rationale. Chapter Five discusses extensions to the language
that will probably be done during the next year.

%A R. J. WALDINGER
%A K. N. LEVITT
%T REASONING ABOUT PROGRAMS
%R Technical Note 86
%I SRI International
%C Menlo Park, California
%D OCTOBER 1973
%X This paper describes a theorem prover that embodies
knowledge about programming constructs, such as numbers, arrays,
lists, and expressions. The program can reason about these concepts
and is used as part of a program verification system that uses the
Floyd-Naur explication of program semantics. It is implemented in the
QA4 language; the QA4 system allows many pieces of strategic
knowledge, each expressed as a small program, to be coordinated so
that a program stands forward when it is relevant to the problem at
hand. The language allows clear, concise representation of this sort
of knowledge. The QA4 system also has special facilities for dealing
with commutative functions, ordering relations, and equivalence
relations; these features are heavily used in this deductive system.
The program interrogates the user and asks his advice in the course of
a proof. Verifications have been found for Hoare's FIND program a
real-number division algorithm, and some sort programs, as well as for
many simpler algorithms. Additional theorems have been proved about a
pattern matcher and a version of Robinson's unification algorithm.
The appendix contains a complete, annotated listing of the deductive
system and annotated traces of several of the deductions performed by
the system.

%A ZOHAR MANNA
%A Richard J. WALDINGER
%T KNOWLEDGE AND REASONING IN PROGRAM SYNTHESIS
%R Technical Note 98
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1974
%X Program synthesis is the construction of a computer
program from given specifications. An automatic program synthesis
system must combine reasoning and programming ability with a good deal
of knowledge about the subject matter of the program. This ability
and knowledge must be manifested both procedurally (by programs) and
structurally (by choice of representation).
 We describe some of the reasoning and programming capabilities of
a projected synthesis system. Special attention is paid to the
introduction of conditional tests, loops, and instructions with wide
effects in the program being constructed. The ability to satisfy
several interacting goals simultaneously proves to be important in
many contexts. The modification of an already existing program to
solve a somewhat different problem has been found to be a powerful
approach.
 We illustrate these concepts with hand simulations of the
synthesis of a number of pattern-matching programs. Some of these
techniques have already been implemented, some are in the course of
implementation, while others seem equivalent to well-known unsolved
problems in artificial intelligence.

%A RICHARD WALDINGER
%T ACHIEVING SEVERAL GOALS SIMULTANEOUSLY
%R Technical Note 107
%I SRI International
%C Menlo Park, California
%D JULY 1975
%X In the synthesis of a plan or computer program, the
problem of achieving several goals simultaneously presents special
difficulties, since a plan to achieve one goal may interfere with
attaining the others. This paper develops the following strategy: to
achieve two goals simultaneously, develop a plan to achieve one of
them and then modify that plan to achieve the second as well. A
systematic program modification technique is presented to support this
strategy. The technique requires the introduction of a special
skeleton model to represent a changing world that can accommodate
modifications in the plan. This skeleton model also provides a novel
approach to the frame problem.
 The strategy is illustrated by its application to three examples.
Two examples involve synthesizing the following programs:
interchanging the values of two variables and sorting three variables.
The third entails formulating a tricky blocks world plan. The
strategy has been implemented in a simple QLISP program.
 It is argued that skeleton modeling is valuable as a planning
technique apart from its use in plan modification, particularly
because it facilitates the representation of influential actions
whose effects may be far reaching.
 The second part of the paper is a critical survey of contemporary
planning literature, which compares our approach with other techniques
for facing the same problems.

%A EARL D. SACERDOTI
%T A STRUCTURE FOR PLANS AND BEHAVIOR
%R Technical Note 109
%I SRI International
%C Menlo Park, California
%D AUGUST 1975
%X This report describes progress that has been made in
the ability of a computer system to understand and reason actions. A
new method for representing actions within a computer memory has been
developed, and this new representation, called the procedural net, has
been employed in developing new strategies for solving problems and
monitoring the execution of the resulting solutions.
 A set of running computer programs, called the NOAH (Nets of
Action Hierarchies) systems, embodies the representation and
strategies discussed above. Its major goal is to provide a framework
for storing expertise about the actions of a particular task domain
and to impart that expertise to a human in the cooperative achievement
of nontrivial tasks.
 A problem is presented to NOAH as a statement that is to be made
true by applying a sequence of actions in an initial state of the
world. The actions are drawn from a set of actions previously defined
to the system. NOAH first creates a one-step solution to the problem
(essentially Solve the given goal). Then it progressively expands
the level of detail of the solution, filling in ever more detailed
actions. All the individual actions, composed into plans at differing
levels of detail, are stored in a data structure called the procedural
net. The system avoids imposing unnecessary constraints on the order
of the actions, rather than as linear sequences.
 The same data structure is used to guide the human user through a
task. Since the system has planned the task at varying levels of
detail, it can issue requests for action to the user at varying levels
of detail, depending on his competence and understanding of the
higher-level actions. If more detail should be needed than was
originally planned for, or if an unexpected event causes the plan to
go awry, the system can continue to plan from any point during
execution.
The key ideas that are explored include:
- Planning at many levels of detail
- Representing a plan as a partial ordering of actions with respect to
 time.
- Execution monitoring and error recovery usig hierarchial plans.
- Using procedures that represent a task domain to generate
declartive (frame-like) structures that represent individual actions.
- Using abstract actions to model iterative operators.
 The major point of the report is that the structure of a plan of
actions is as important for problem solving and execution monitoring
as the nature of the actions themselves.

%A JANE J. ROBINSON
%T A TUNEABLE PERFORMANCE GRAMMAR
%R Technical Note 112
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1975
%X This paper describes a tuneable performance grammar
currently being developed for speech understanding. It shows how
attributes of words are defined and propagated to successively larger
phrases, how other attributes are acquired, how factors reference
them to help the parser choose among competing definitions in order to
interpret the utterance correctly, and how these factors can easily be
changed to adapt the grammar to other discourses and contexts. Factors
that might be classified as syntactic are emphasized, but the
attributes they reference need not be, and seldom are, purely
syntactic.

%A GARY G. HENDRIX
%T SEMANTIC PROCESSING FOR SPEECH UNDERSTANDING
%R Technical Note 113
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1975
%X The semantic component of the speech understanding
system being developed jointly by SRI and SDC rules out phrase
combinations that are not meaningful and produces semantic
interpretations for combination that are. The system consists of a
semantic network model and routines that interact with it. The net is
partitioned into a set of hierarchically ordered subnets, facilitating
the encoding of higher-order predicates and the maintenance of
multiple parsing hypotheses. Composition routines, combining
utterance components into phrases, consult network descriptions of
prototype situations and surface-to-deep-case maps. Outputs from
these routines are network fragments consisting of several subnets
that in aggregate capture the interrelationships between a phrase's
syntax and semantics.

%A THOMAS D. GARVEY
%T PERCEPTUAL STRATEGIES FOR PURPOSIVE VISION
%R Technical Note 117
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1976
%X This report describes a computer program that
approaches perception as a problem-solving task. The system
uses information about the appearances of objects, about their
interrelationships, and about available sensors to produce a plan for
locating specified objects in images of room scenes. The strategies
produced allow for cost-effective processing by utilizing cheap
features in the early stages, reserving more complex operations for
later in the process, when the content has been sufficiently
restricted.
 The general strategy paradigm used by the system is to acquire
image samples expected to belong to the target object; validate the
hypothesis that the acquired samples do belong to the target; and
finally to bound the image of the object by outlining it in a display
picture.
 Sensors used by the system include a vidicon with three color
filters and a master-scanned, laser-rangefinder capable of producing a
range image. In addition, the range-finder measures the
reflectivity at the laser wavelength, at each post, producing a
gray-scale image in perfect registration with the range image. The
primitive attributes of brightness, line, saturation, height, and
local surface orientation at specified range locations can be computed
from these images. These attributes represent the new data available
to the system for recognizing and identifying objects. Object
descriptions are provided initially by indicating the object to the
system, and allowing the system to measure attributes. Other data,
such as typical object relationships, are provided interactively by
the user.
 When required to locate an object, the system computes a
distinguishing features representation that will serve to separate
parts of the target from those of other objects. These distinguishing
features are combined into a strategy represented as a planning graph.
This graph contains optimal subgoals for achieving the goal of
locating the object. An execution routine selects the best subgoal,
executes it, rates its effect, and selects the next best goal,
continuing with the progress until either the object is located, or
there are no options remaining.
 This approach offers several contributions to perception
research. By capitalizing on the goal-directed aspects of the
problem, the system is able to select relevant information from a mass
of irrelevant data. The system is able to organize its processing in
such a way as to optimize the use of sensor data. By generating
strategies when needed, the program allows for the easy introduction
of new objects and new sensors. The system allows for the logical
introduction of new information deriving algorithms.

%A EARL SACERDOTI
%A RICHARD FIKES
%A RENE REBOH
%A DANIEL SAGALOWICZ
%A RICHARD WALDINGER
%A B. MICHAEL WILBER
%T QLISP: A LANGUAGE FOR THE INTERACTIVE DEVELOPMENT OF COMPLEX SYSTEMS
%R Technical Note 120
%I SRI International
%C Menlo Park, California
%D MARCH 1976
%X This paper presents a functional overview of the
features and capabilities of QLISP, one of the newest of the current
generation of very high level languages developed for use in
artificial intelligence (AI) research.
 QLISP is both a programming language and an interactive
programming environment. It embeds an extended version of QA4, an
earlier AI language, in INTERLISP, a widely available version of LISP
with a variety of sophisticated programming aids.
 The language features provided by QLISP include a variety of
useful data types, an associative data base for the storage and
retrieval of expressions, a powerful pattern matcher based on a
unification algorithm, pattern-directed function invocation, teams
of pattern involved functions, a sophisticated mechanism for breaking
a data base into contexts, generators for associative data retrieval,
and easy extensibility. System features available in QLISP include a
very smooth interaction with the underlying INTERLISP language, a
facility for aggregating multiple pattern matches, and features for
interactive control of programs.
 A number of the implemented applications of QLISP are briefly
discussed, and some directions for future development are presented.

%A HARRY G. BARROW
%A J. MARTIN TENENBAUM
%T MSYS: A SYSTEM FOR REASONING ABOUT SCENES
%R Technical Note 121
%I SRI International
%C Menlo Park, California
%D APRIL 1976
%X MSYS is a system for reasoning with uncertain
information and inexact rules of inference. Its major application, to
date, has been to the interpretation of visual features (such as
regions) in scene analysis. In this application, features are
assigned sets of possible interpretations with associated likelihoods
based on local attributes (e.g., color, size, and shape).
Interpretations are related by rules of inference that adjust the
likelihoods up or down in accordance with interpretation likelihoods
of related features. An asynchronous relaxation process repeatedly
applies the rules until a consistent set of likelihood values is
attained. At this point, several alternative interpretations still
exist for each feature. One feature is chosen and the most likely of
its alternatives is assumed. the rules are then used in this more
precise context to determine likelihoods for the interpretations of
remaining features by a further round of relaxation. The selection
and relaxation steps are repeated until all features have been
interpreted.
 Some interpretation typifies constraint optimization problems
involving the assignment of values to a set of mutually constrained
variables. For an interesting class of constraints, MSYS is
guaranteed to find the optimal solution with less branching than
conventional heuristic search methods.
 MSYS is implemented as a network of asynchronous parallel
processes. The implementation provides an effective way of using data
driven systems with distributed control for optimal stochastic search.

%A J. MARTIN TENENBAUM
%A HARRY G. BARROW
%T EXPERIMENTS IN INTERPRETATION-GUIDED SEGMENTATION
%R Technical Note 123
%I SRI International
%C Menlo Park, California
%D MARCH 1976
%X This paper presents a new approach for integrating the
segmentation and interpretation phases of scene analysis. Knowledge
from a variety of sources is used to make inferences about the
interpretations of regions, and regions are merged in accordance with
their possible interpretations.
 The deduction of region interpretations is performed using a
generalization of Waltz's filtering algorithm. Deduction proceeds by
eliminating possible region interpretations that are not consistent
with any possible interpretation of an adjacent region. Different
sources of knowledge are expressed uniformly as constraints on the
possible interpretations of regions. Multiple sources of knowledge
can thus be combined in a straightforward way such that incremental
additions of knowledge (or equivalently, human guidance) will effect
incremental improvements in performance.
 Experimental results are reported in three scene domains,
landscapes, mechanical equipment, and rooms, using, respectively, a
human collaborator, a geometric model and a set of relational
constraints as sources of knowledge. These experiments demonstrate
that segmentation is much improved when integrated computational
overhead over unguided segmentation.
 Applications of the approach in cartography, photointerpretation,
vehicle guidance, medicine, and motion picture analysis are suggested.

%A RICHARD O. DUDA, PETER E. HART,
%A NILS J. NILSSON
%T SUBJECTIVE BAYESIAN METHODS FOR RULE-BASED INFERENCE SYSTEMS
%R Technical Note 124
%I SRI International
%C Menlo Park, California
%D JANUARY 1976
%X The general problem of drawing inferences from
uncertain or incomplete evidence has invited a variety of technical
approaches, some mathematically rigorous and some largely informal and
intuitive. Most current inference systems in artificial intelligence
have emphasized intuitive methods, because the absence of adequate
statistical samples forces a reliance on the subjective judgment of
human experts. We describe in this paper a subjective Bayesian
inference method that realizes some of the advantages of both formal
and informal approaches. Of particular interest are the modifications
needed to deal with the inconsistencies usually found in collections
of subjective statements.

%A THOMAS D. GARVEY
%A J. MARTIN TENENBAUM
%T APPLICATION OF INTERACTIVE SCENE ANALYSIS TECHNIQUES TO CARTOGRAPHY
%R Technical Note 127
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1976
%X One of the most time-consuming and labor-intensive
steps in map production involves the delineation of cartographic and
cultural features such as lakes, rivers, roads, and drainages in
aerial photographs. These features are usually traced manually on a
digitizing table in painstaking detail. This paper investigates an
alternative approach, an interactive graphically designates a feature
of interest by pointing at or crudely tracing it with a display
cursor. Using this input as a guide, the system employs context-dependent,
scene-analysis techniques to extract a detailed outline of
the feature. The results are displayed so that errors can be
corrected by further interaction, for example, by tracing small
sections of the boundary in detail. This interactive approach appears
applicable to many other problem domains involving large quantities of
graphic or pictorial data, which are difficult to extract in digital
form by either strictly manual or strictly automatic means.

%A ZOHAR MANNA
%A RICHARD WALDINGER
%T IS SOMETIME SOMETIMES BETTER THAN ALWAYS?
INTERMITTENT ASSERTION IN PROVING PROGRAM CORRECTNESS
%R Technical Note 132
%I SRI International
%C Menlo Park, California
%D JUNE 1976
%X This paper explores a technique for proving the
correctness and termination of programs simultaneously. This
approach, which we call the intermittent-assertion method, involves
documenting the program with assertions that must be true at some time
when control is passing through the corresponding point, but that need
not be true every time. The method, introduced by Knuth and further
developed by Burstall, promises to provide a valuable complement to
the more conventional methods.
 We first introduce and illustrate the technique with a number of
examples. We then show that a correctness proof using the invariant
assertion method or the subgoal induction method can always be
expressed using intermittent assertions instead, but that the reverse
is not always the case. The method can also be used just to prove
termination, and any proof of termination using the conventional
well-founded sets approach can be rephrased as a proof using
intermittent assertions. Finally, we show how the method can be
applied to prove the validity of program transformations and the
correctness of continuously operating programs.

%A WILLIAM H. PAXTON
%T EXPERIMENTS IN SPEECH UNDERSTANDING SYSTEM CONTROL
%R Technical Note 134
%I SRI International
%C Menlo Park, California
%D AUGUST 1976
%X A series of experiments was performed concerning
control strategies for a speech understanding system. The main
experiment tested the effects on performance of four major choices:
focus attention by inhibition or use an unbiased best-first method,
island-drive or process left or right, use context checks in
priority setting or do not, and map words all at once or map only as
called for. Each combination of choices was tested with 60
simulated utterances of lengths varying from 0.8 to 2.3 seconds. The
results include analysis of the effects and interactions of the design
choices with respect to aspects of system performance such as overall
sentence accuracy, processing time, and storage. Other experiments
include tests of acoustic processing performance and a study of the
effects of increased vocabulary and improved acoustic accuracy.

%A RICHARD O. DUDA
%T SEMANTIC NETWORK REPRESENTATION IN RULE BASED INFERENCE
 SYSTEM
%R Technical Note 136
%I SRI International
%C Menlo Park, California
%D JANUARY 1977
%X Rule-based inference systems allow judgmental knowledge
about a specific problem domain to be represented as a collection of
discrete rules. Each rule states that if certain premises are known,
then certain conclusions can be inferred. An important design issue
concerns the representational form for the premises and conclusions of
the rules. We describe a rule-based system that uses a partitioned
semantic network representation for the premises and conclusions.
 Several advantages can be cited for the semantic network
representation. The most important of these concern the ability to
represent subset and element taxonomic information, the ability to
include the potential for smooth interface with natural language
subsystems. This representation is being used in a system currently
under development at SRI to aid a geologist in the evaluation of the
mineral potential of exploration sites. The principles behind this
system and its current implementation are described in the paper.

%A HARRY BARROW
%A THOMAS GARVEY
%A JAN KREMERS
%A J. MARTIN TENENBAUM
%A HELEN C. WOLF
%T INTERACTIVE AIDS FOR CARTOGRAPHY AND PHOTO INTERPRETATION
%R Technical Note 137
%I SRI International
%C Menlo Park, California
%D JANUARY 1977
%X This report covers the six-month period October 1975 to
April 1976. In this report, the application areas of ARPA-supported
Machine Vision work at SRI were changed to Cartography and
Photointerpretation. This change entailed general familiarization
with the new domains, exploration of their current practices and uses,
and determination of outstanding problems. In addition, some
preliminary tool-building and experimentation have been performed with
a view to determining feasibility of various AI approaches to the
identified problems. The work of this period resulted in the
production and submission to ARPA of a proposal for research into
Interactive Aids for Cartography and Photointerpretation. This report
will not reiterate in detail the content of the proposal, but will
refer the reader to it for further information.

%A GARY G. HENDRIX
%T LIFER MANUAL: A GUIDE TO BUILDING PRACTICAL NATURAL LANGUAGE INTERFACE
%R Technical Note 138
%I SRI International
%C Menlo Park, California
%D FEBRUARY 1977
%X This document describes an application-oriented system
for creating natural language interfaces between existing computer
programs (such as data base management systems) and casual users. The
system is easy to use and flexible, offering a range of capabilities
that support both simple and complex interfaces. This range of
capabilities allows beginning interface builders to rapidly define
worktable sublets of English and gives more advanced language
definitions. The system includes an automatic mechanism for handling
certain classes of elliptical (incomplete) inputs, a spelling
corrector, a grammar editor, and a mechanism that allows even novices,
through the use of paraphrase, to extend the language recognized by
the system. Experience with the system has shown that for many
applications, very practicable interfaces may be created in a few
days.

%A GARY G. HENDRIX
%T HUMAN ENGINEERING FOR APPLIED NATURAL LANGUAGE PROCESSING
%R Technical Note 139
%I SRI International
%C Menlo Park, California
%D MARCH 1977
%X Human engineering features for enhancing the usability
of practical natural language systems are described. Such features
include spelling correction, processing of incomplete (elliptical)
inputs, interrogation of the underlying language definition through
English queries, and an ability for casual users to extend the
language accepted by the system through the use of synonyms and
paraphrases. All of the features described are incorporated in LIFER,
an applications-oriented system for creating natural language
interfaces between computer programs and casual users. LIFER's
methods for realizing the more complex human engineering features are
presented.

%A EARL D. SACERDOTI
%T LANGUAGE ACCESS TO DISTRIBUTED DATA WITH ERROR RECOVERY
%R Technical Note 140
%I SRI International
%C Menlo Park, California
%D APRIL 1977
%X This paper discusses an effort in the application of
artificial intelligence to the access of data from a large,
distributed data base over a computer network. A running system is
described that provides access to multiple instances of a data base
management system over the ARPANET in real time. The system accepts a
rather wide range of appropriate queries to the data base management
system to answer the question, determines on which machine to carry
out the queries, establishes links to those machines over the ARPANET,
monitors the prosecution of the queries and recovers from certain
errors in execution, and prepares a relevant answer to the original
question. In addition to the functional components that make up the
demonstration system, equivalent functional components with higher
levels of sophistication are discussed and proposed.

%A WILLIAM H. PAXTON
%T A FRAMEWORK FOR SPEECH UNDERSTANDING
%R Technical Note 142
%I SRI International
%C Menlo Park, California
%D JUNE 1977
%X This paper reports the author's results in designing,
implementing, and testing a framework for a speech-understanding
system. The work was done as part of a multi-disciplinary effort
based on state-of-the-art advances in computational linguistics,
artificial intelligence, systems programming, and speech science. The
overall project goal was to develop one or more computer systems that
would recognize continuous speech uttered in the context or some
 well-specifiedtask by making extensive use of grammatical, semantic, and
and contextual constraints. We call a system emphasizing such
linguistic constraints a `speech-understanding system' to distinguish
it from speech-recognition systems which rely on acoustic information
alone.
 Two major aspects of a framework for speech understanding are
integration of the process of forming a unified system out of the
collection of components--and control--the dynamic direction of the
overall activity of the system during the processing of an input
utterance. Our method of system integration gives a central role to
the input-language definition, which is based on augmented phrase-
structure rules. A rule consists of a phrase-structure declaration
which specifies the possible for computing 'attributes'and `factors.'
Attribute statements determine the properties of particular phrases
constructed by the rule; factor statements make acceptability
judgments on phrases. Together these statements contain specifications for
 most of the potential interactions among system components.
 Our approach to system control centers on a system `Executive'
applying the rules of the language definition organizing hypotheses
and results, and assigning priorities. Phrases with their attributes
and factors are the basic entities manipulated by the Executive, which
takes on the role of a parser in carrying out its integration and
control functions. The Executive controls the overall activity of the
system by setting priorities on the basis of acoustics and linguistic
acceptability judgments. These data are combined to form scores and
ratings. A phrase score reflects a quality judgment independent of
the phrase's context and gives useful local information concerning the
sentential context. To get early and efficient access to the
contextual information, we have developed a technique for calculating
phrase ratings by a heuristic search of possible interpretations that
would use the phrase. One of our experiments shows that this
context-checking method results in significant improvements in system
performance.

%A DANIEL SAGALOWICZ
%T IDA
%R Technical Note 145
%I SRI International
%C Menlo Park, California
%D JUNE 1977
%X IDA was developed at SRI to allow a casual user to
retrieve information from a data base, knowing the fields present in
the data base, but not the structure of the data base itself. IDA is
part of a system that allows the user to express queries in a
restricted subset of English, about a data base of fourteen files
stored on CCA's Datacomputer. IDA's input is a very simple, formal
query language which is essentially a list of restrictions on fields
and queries about fields, with no mention of the structure of the data
base. It produces a series of DBMS queries, which are transmitted
over the ARPA network. The results of these queries are combined by
IDA to provide the answer to the user's query. In this paper, we will
define the input language, and give examples of IDA's behavior. We
will also present our representation of the structural schema," which
is the information needed by IDA to know how the data base is actually
organized. We will give an idea of some of the heuristics which are
used to produce a program in the language of the DBMS. Finally, we
will discuss the limitations of this approach, as well as future
research areas.

%A BARBARA J. GROSZ
%T THE REPRESENTATION AND USE OF FOCUS IN DIALOGUE
%R Technical Note 151
%I SRI International
%C Menlo Park, California
%D JULY 1977
%X This report develops a representation of focus of
attention that circumscribes discourse contexts within a general
representation of knowledge. Focus of attention is essential to any
comprehension process because what and how a person understands is
strongly influenced by where his attention is directed at a given
moment. To formalize the notion of focus, the need for and the use of
focus mechanisms are considered from the standpoint of building a
computer system that can participate in a natural language dialogue
with a user. Two ranges of focus, global and immediate, are
investigated, and representations for incorporating them in a computer
system as developed.
 The global focus in which an utterance is interpreted is
determined by the total discourse and situational setting of the
utterance. It influences what is talked about, how different concepts
are introduced, and how concepts are referenced. To encode global
focus computationally, a representation is developed that highlights
those items that are relevant at a given place in a dialogue. The
underlying knowledge representation is segmented into subunits, called
focus spaces, that contain those items that are in the focus of
attention of a dialogue participant during a particular part of the
dialogue.
 Mechanisms are required for updating the focus representation,
because, as a dialogue progresses, the objects and actions that are
relevant to the conversation, and therefore in the participants' focus
of attention, change. Procedures are described for deciding when and
how to shift focus in task-oriented dialogues, i.e., in dialogues in
which the participants are cooperating in a shared task. These
procedures are guided by a representation of the task being performed.
 The ability to represent focus of attention in a language understanding
system results in a new approach to an important problem in
discourse comprehension--the identification of the referents of
definite noun phrases. Procedures for identifying referents are
developed that take discourse structure into account and use the
distinction between highlighted items and those that are not
highlighted to constrain the search for the referent of a definite
noun phrase.
 Interpretation of an utterance also depends on the immediate
focus established by the linguistic form of the preceding utterance.
The interpretation of elliptical sentence fragments illustrates the
effect of immediate focus. Procedures that interpret elliptical
sentence fragments are developed. The use of a representation that
superimposes syntactic information about an utterance on the
interpretation of the underlying meaning of that utterance to minimize
the processing required to expand a fragment into a complete sentence.

%A GARY G. HENDRIX
%A EARL D. SACERDOTI
%A DANIEL SAGALOWICZ
%A JONATHAN SLOCUM
%T DEVELOPING A NATURAL LANGUAGE INTERFACE TO COMPLEX DATA
%R Technical Note 152
%I SRI International
%C Menlo Park, California
%D AUGUST 1977
%X This paper describes aspects of an intelligence
interface that provides natural language access to a large body of
data distributed over a computer network. The overall system
architecture is presented, showing how a user is buffered from the
actual data base management systems (DBMSs) by three layers of
insulating components. These layers operate in series to convert
natural language queries into calls to DBMSs at remote sites.
Attention is then focused on the first of the insulating components,
the natural language system. A pragmatic approach to language access
that has proved useful for building interfaces to data bases is
described and illustrated by examples. Special language features that
increase system usability, such as spelling correction, processing of
incomplete inputs, and run-time system personalization, are also
discussed.

%A RICHARD WALDINGER
%A ZOHAR MANNA
%T THE LOGIC OF COMPUTER PROGRAMMING
%R Technical Note 154
%I SRI International
%C Menlo Park, California
%D AUGUST 1977
%X Techniques derived from mathematical logic promise to
provide an alternative to the conventional methodology for
constructing, debugging, and optimizing computer programs. Ultimately, these
techniques are intended to lead to the automation of many of the
facets of the programming process.
 This paper provides a unified tutorial exposition of the logical
techniques, illustrating each with examples. The strengths and
limitations of each technique as a practical programming aid are
assessed and attempts to implement these methods in experimental
systems are discussed.

%A PETER E. HART
%A RICHARD O. DUDA
%T PROSPECTOR--A COMPUTER BASED CONSULTATION SYSTEM FOR MINERAL EXPLORATION
%R Technical Note 155
%I SRI International
%C Menlo Park, California
%D OCTOBER 1977
%X This paper reviews the principles and status of
Prospector, a computer-based consultation program for mineral
exploration. The mechanisms for representing ore deposit models by
networks of inference rules are described, and the overall approach is
compared to alternative decision making methodologies.

%A RICHARD WALDINGER
%A ZOHAR MANNA
%T SYNTHESIS: DREAMS == PROGRAMS
%R Technical Note 156
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1977
%X Deductive techniques are presented for deriving
programs systematically from given specifications. The specifications
express the purpose of the desired program without giving any hint of
the algorithm to be employed. The basic approach is to transform the
specifications repeatedly according to certain rules, until a
satisfactory program is produced. These techniques have been
incorporated in a running program-synthesis system, called DEDALUS.
 Many of the transformation rules represent knowledge about the
program's subject domain (e.g., numbers, lists, sets); some represent
the meaning of the constructs of the specification language and the
target programming language; and a few rules represent basic
programming principles. Two of these principles, the conditional-formation
rule and the recursion-formation rule, account for the
introduction of conditional expressions and of recursive calls into
the synthesized program. The termination of the programs is ensured
as new recursive calls are formed.
 Two extensions of the recursion-formation rule are discussed; a
procedure-formation rule, which admits the introduction of auxiliary
subroutines in the course of the synthesis process, and a
generalization rule, which causes the specifications to be altered to
represent a more general problem that is nevertheless easier to solve. Special
techniques are introduced for the formation of programs with side
effects.
 The techniques of this paper are illustrated with a sequence of
examples of increasing complexity; programs are constructed for list
processing, numerical calculation, and array computation.
 The methods of program synthesis can be applied to various
aspects of programming methodology--program transformation, data
abstraction, program modification, and structured programming.
 The DEDALUS system accepts specifications expressed in a
high-level language, including set notation, logical quantification,
and a rich vocabulary drawn from a variety of subject domains. The
system attempts to transform the specifications into a recursive,
LISP-like target program. Over one hundred rules have been
implemented, each expressed as a small program in a QLISP language.

%A HARRY G. BARROW
%A J. MARTIN TENENBAUM
%T RECOVERING INTRINSIC SCENE CHARACTERISTICS FROM IMAGES
%R Technical Note 157
%I SRI International
%C Menlo Park, California
%D APRIL 1978
%X We suggest that an appropriate role of early visual
processing is to describe a scene in terms of intrinsic (vertical)
characteristics--such as range, orientation, reflectance, and incident
illumination--of the surface element visible at each point in the
image. Support for this idea comes from three sources: the obvious
utility of intrinsic characteristics for higher-level scene analysis;
the apparent ability of humans to determine these characteristics,
regardless of viewing conditions or familiarity with the scene; and a
theoretical argument that such a description is obtainable, by a
noncognitive and nonpurposive process, at least, for simple scene
domains. The central problem in recovering intrinsic value encodes
all the characteristics of the corresponding scene point. Recovery
depends on exploiting constraints, derived from assumptions about the
nature of the scene and the physics of the imaging process.

%A LYNN H. QUAM
%T ROAD TRACKING AND ANOMALY DETECTION IN AERIAL IMAGERY
%R Technical Note 158
%I SRI International
%C Menlo Park, California
%D MARCH 1979
%X This report describes a new procedure for tracking road
segments and finding potential vehicles in imagery of approximately 1
to 3 feet per pixel ground resolution. This work is part of a larger
effort by SRI International to construct an image understanding system
for monitoring roads in aerial imagery.

%A EARL D. SACERDOTI
%A DANIEL SAGALOWICZ
%T A LADDER USER'S GUIDE (REVISED)
%R Technical Note 163R
%I SRI International
%C Menlo Park, California
%D MARCH 1980
%X LADDER (Language Access to Distributed Data with Error
Recovery) is a computer system designed to provide answers to
questions posed at the terminal in a subset of natural language
regarding a distributed data base of naval command and control
information. The system accepts a fairly wide range of
naturalf-language questions about the data. For each question LADDER
plans a sequence of appropriate queries to the data base management
system, determines on which machine the queries are to be processed,
establishes links to those machines over the Arpanet, monitors the
processing of the queries and recovers from certain errors in
execution, and prepares a relevant answer to the original question.
The user's guide is intended for the person who knows how to log in to
the host operating system, as well as how to enter and edit a line of
text. It does not explain how LADDER works, but rather how to use it
on a demonstration basis.

%A GARY G. HENDRIX
%T ENCODING KNOWLEDGE IN PARTITIONED NETWORKS
%R Technical Note 164
%I SRI International
%C Menlo Park, California
%D JUNE 1978
%X This paper discusses network notations for encoding a
number of different kinds of knowledge, including taxonomic
information; general statements involving quantification; information
about processes and procedures; the delineation of local contexts,
beliefs, and wishes; and the relationships between syntactic units and
their interpretations.
 Many of the encodings appeal to the concept of network
partitioning, in which a large net is partitioned into subnets and
higher-order relationships among the subnets are defined.
 Procedural mechanisms for constructing and using the various
network formalisms are discussed as equal partners with the
declarative structures.

%A ANN E. ROBINSON
%T INVESTIGATING THE PROCESS OF NATURAL LANGUAGE COMMUNICATION
%R Technical Note 165
%I SRI International
%C Menlo Park, California
%D JUNE 1978
%X This paper provides an overview of an ongoing research
program on natural language communications, indicating its status as
of June 1978, and its short term goals. This research seeks to
identify and computationally formalize the knowledge and processes
needed for participation in natural language dialogs about ongoing
tasks. The paper describes (1) the knowledge embodied in an existing
system that interprets utterances in such dialogs, (2) the formalisms
developed for encoding this knowledge, and (3) the framework in which
the knowledge is combined and coordinated during the interpretation
process. The paper also indicates anticipated extensions that will
lead to refinements of interpretations. These extensions include the
concept of modality, the use of the focus and goals of the dialog in
the identification of the referents of pronouns, and the use of
knowledge about the goals of the other dialog participants in the
interpretation of utterances.

%A JERRY R. HOBBS
%T COHERENCE AND COREFERENCE
%R Technical Note 168
%I SRI International
%C Menlo Park, California
%D AUGUST 1978
%X Coherence in conversations and in texts can be
partially characterized by a set of coherence relations, motivated
ultimately by the speaker's or writer's need to be understood. In
this paper, formal definitions are given for several coherence
relations, based on the operations of an inference system; that is,
the relations between successive portions of a discourse are
characterized in terms of the inferences that can be drawn from each.
In analyzing a discourse, it is frequently the case that we would
recognize it as coherent, in that it would satisfy the formal
definition of some coherence relation, if only we could assume certain
noun phrases to be coreferential. In such cases, we will simply
assume the identity of the entities referred to, in what might be
called a petty conversational implicature," thereby solving the
coherence and coreference problems simultaneously. Three examples of
different kinds of reference problems are presented. In each, it is
shown how the coherence of the discourse are solved, almost as a
by-product, by means of these petty conversational implicatures.

%A JERRY R. HOBBS
%A JANE J. ROBINSON
%T WHY ASK?
%R Technical Note 169
%I SRI International
%C Menlo Park, California
%D OCTOBER 1978
%X In this paper, we address the problem, What makes an
answer appropriate?" We do so by investigating indirect answers to
questions in task-oriented dialogues. Three cases are distinguished:
(1) The response, though indirect, answers the question asked; (2) the
response denies a presupposition of the question; and (3) the response
answers to higher goals the questioner was trying to achieve.
Detailed analysis shows the need for knowledge about the task, the
role of the participants, and communication goals, in the construction
of appropriate answers. We conclude with a preliminary formulation of
the appropriateness of an answer in terms of the goals of the
questioner and the knowledge of the respondent.

%A ROBERT C. MOORE
%T HANDLING COMPLEX QUERIES IN A DISTRIBUTED DATA BASE
%R Technical Note 170
%I SRI International
%C Menlo Park, California
%D OCTOBER 1979
%X As part of the continuing development of the LADDER
system, we have substantially expanded the capabilities of the
data base access component that serves as the interface between the
natural- language front end of LADDER and the data base management
systems on which the data is actually stored. SODA, the new data base
access component, goes beyond its predecessor IDA, in that it
accepts a wider range of queries and accesses multiple DBMSs. This
paper is concerned with the first of these areas, and discusses how
the expressive power of the query language was increased, how these
changes affected query processing in a distributed data base, as well
as what are some limitations of and planned extensions to the current
system.

%A MARTIN N. EPSTEIN
%A DONALD E. WALKER
%T NATURAL LANGUAGE ACCESS TO A MELANOMA DATA BASE
%R Technical Note 171
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1978
%X This paper describes ongoing research towards
developing a system that will allow physicians personal access to
patient medical data through natural language queries to support both
patient management and clinical research. A prototype system has
been implemented for a small data base on malignant melanoma. The
physician can input queries in English that retrieve specified data
for particular patients or for groups of patients satisfying certain
characteristics, that perform simple calculations, that allow browsing
through the data base, and that assist in identifying relations among
attributes. The system supports dialogue interactions; that is, the
user can follow a line of inquiry to test a particular hypothesis by
entering a sequence of queries that depend on each other. Classes of
questions that can be processed are described and examples using the
system are given.

%A J. MARTIN TENENBAUN, MARTIN A. FISCHLER,
%A HELEN C. WOLF
%T A SCENE-ANALYSIS APPROACH TO REMOTE SENSING
%R Technical Note 173
%I SRI International
%C Menlo Park, California
%D OCTOBER 1978
%X A scene-analysis approach to interpretation of remotely
sensed imagery is described, with emphasis on applications involving
continuous monitoring of predetermined ground sites. A key concept is
the use of knowledge contained in various kinds of maps to guide the
extraction of relevant information from the image.
 Geometric correspondence between a sensed image and a symbolic
map is established in an initial stage of processing by adjusting
parameters of a sensor model so that image features predicted from the
optimally match corresponding features extracted from the sensed
image. Information in the map is then used to constrain where to look
in an image, what to look for, and how to interpret what is seen. For
simple monitoring tasks involving multispectral classification, these
constraints can significantly reduce computation, simplify
interpretation, and improve the utility of the resulting information.
Moreover, previously intractable tasks requiring spatial and textural
analysis may become straightforward in the context established by the
map knowledge. Three such tasks are demonstrated: monitoring the
volume of water in a reservoir, monitoring the number of boxcars in a
railyard, and monitoring the number of ships in a harbor.
 The conceptual approach of map-guided image analysis is described
in sufficient generality to suggest numerous other applications.
Details of the map-image correspondence procedure and a general
technique for locating boundaries to subpixel accuracy using map
knowledge are described in appendices.

%A J. MARTIN TENENBAUM, HARRY G. BARROW,
%A ROBERT C. BOLLES
%T PROSPECTS FOR INDUSTRIAL VISION
%R Technical Note 175
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1978
%X Most current industrial vision systems are designed to
recognize known objects seen from standard view points in high
contrast scenes. Their performance and reliability are marginal; many
tasks including such as bin picking, recognition of parts on overhead
conveyors, and implicit inspection of surface flaws are beyond current
competence.
 Recent image understanding research suggests that the limitations
of current industrial vision systems stem from inadequate
representations for describing scenes; physical attributes
(reflectance, texture, etc.) and three-dimensional pictorial features
and object models. This paper builds a case for needed additional
levels of representation and outlines the design of a general-purpose
computer-vision system capable of high performance in a wide variety
of industrial vision tasks.
 This paper was originally presented at the General Motors
Symposium on Computer Vision and Sensor-Based Robots," September
1978, the proceedings of which will be published by Plenum Press in
1979.

%A JERRY R. HOBBS
%T WHY IS DISCOURSE COHERENT?
%R Technical Note 176
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1978
%X When people produce a discourse, what needs are they
responding to when they make it coherent, and what form does this
coherence take? In this paper, it is argued that coherence can be
characterized in terms of a set of coherence relations" between
segments of a discourse. It is shown, from an abstract description of
the discourse situation, that these relations correspond to the kinds
of communicative work that needs to get done in discourse. In
particular, four requirements for successful communication are
isolated: the message itself must be conveyed; the message must be
related to the goals of the discourse; what is new and unpredictable
in the message must be related to what the listener's inference
processes toward the full intended meaning of the message.
Corresponding to each requirement is a class of coherence relations
that help the speaker satisfy the requirements. The coherence
relations in each class are discussed and defined formally. Finally,
a fragment of a conversation is analyzed in detail to illustrate the
problems that face a speaker in trying to satisfy these requirements,
and to demonstrate the role the coherence relations play in the
solution.

%A ZOHAR MANNA
%A RICHARD WALDINGER
%T A DEDUCTIVE APPROACH TO PROGRAM SYNTHESIS
%R Technical Note 177
%I SRI International
%C Menlo Park, California
%D DECEMBER 1978
%X Program synthesis is the systematic derivation of a
program from a given specification. A deductive approach to program
synthesis is presented for the construction of recursive programs.
This approach regards program synthesis as a theorem-proving task and
relies on a theorem-proving method that combines the features of
transformation rules, unification, and mathematical induction within a
single framework.

%A GERALD J. AGIN
%T HIERARCHICAL REPRESENTATION OF THREE-DIMENSIONAL OBJECTS USING VERBAL MODELS
%R Technical Note 182
%I SRI International
%C Menlo Park, California
%D MARCH 1979
%X We present a formalism for the computer representation
of three-dimensional shapes, that has as its goal to facilitate
man-machine communication using verbal, graphic, and visual means.
With this method, pieces may be assembled hierarchically using any of
several ways of specifying attachment. The primitives of the
representation are generalized cylinders, and the creating of
assemblies may make use of the axes inherent in the primitives.
Generic models may be described that may leave some parameters or
dimensions unspecified, so that when a specific instance of the model
is described, those parameters may either be explicitly specified or
take on default values. The axes of local coordinate frames may be
given symbolic names. A set of computer programs translate
descriptions of objects into polyhedral models and line drawings.

%A BARBARA J. GROSZ
%T FOCUSING AND DESCRIPTION IN NATURAL LANGUAGE DIALOGUES
%R Technical Note 185
%I SRI International
%C Menlo Park, California
%D APRIL 1979
%X When two people talk, they focus their attention on
only a small portion of what each of them knows or believes. Both
what is said and how it is interpreted depend on a shared
understanding of this narrowing of attention to a small highlighted
portion of what is known.
 Focusing is an active process. As a dialogue progresses, the
participants continually shift their focus and thus form an evolving
context against which utterances are produced and understood. A
speaker provides a hearer with clues of what to look at and how to
look at it--what to focus on, how to focus on it, and how wide or
narrow the focusing should be. As a result, one of the effects of
understanding an utterance is that the listener becomes focused on
certain entities (both objects and relationships) from a particular
perspective.
 Focusing clues may be linguistic or they may come from knowledge
about the relationships between entities in the domain. Linguistic
clues may be either explicit, deriving directly from certain words, or
implicit, deriving from sentential structure and from rhetorical
relationships between sentences.
 This paper examines the relationships between focusing and
definite descriptions in dialogue and its implications for natural
language processing systems. It describes focusing mechanisms based
on domain structure clues which have been included in a computer
system and, from this perspective, indicates future research problems
entailed in modeling the focusing process more generally.

%A ROBERT C. MOORE
%A GARY G. HENDRIX
%T COMPUTATIONAL MODELS OF BELIEFS AND THE SEMANTICS OF BELIEF-SENTENCES
%R Technical Note 187
%I SRI International
%C Menlo Park, California
%D JUNE 1979
%X This paper considers a number of problems in the
semantics of belief sentences from the perspective of computational
models of the psychology of belief. We present a semantic
interpretation for belief sentences and show how this interpretation
overcomes some of the difficulties of alternative approaches,
especially those based on possible-world semantics. Finally, we argue
that these difficulties arise from a mistaken attempt to identify the
truth conditions of a sentence with what a competent speaker knows
about the meaning of the sentence.

%A BARBARA J. GROSZ
%T UTTERANCE AND OBJECTIVE: ISSUES IN NATURAL LANGUAGE COMMUNICATION
%R Technical Note 188
%I SRI International
%C Menlo Park, California
%D JUNE 1979
%X Communication in natural language requires a combination of
language-specific and general common-sense reasoning capabilities, the
ability to represent and reason about the beliefs, goals, and plans of
multiple agents, and the recognition that utterances are multifaceted.
This paper evaluates the capabilities of natural language processing
systems against these requirements and identifies crucial areas for
future research in language processing, common-sense reasoning, and
their coordination.

%A ROBERT C. MOORE
%T REASONING ABOUT KNOWLEDGE AND ACTION
%R Technical Note 191
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1979
%X This thesis deals with the problem of
making a computer reason about the interactions between knowledge and
action. In particular, we want to be able to reason about what
knowledge a person must have in order to perform an action, and what
knowledge a person may gain by performing an action. The first
problem we face in achieving this goal is that the basic facts about
knowledge which we need to use are most naturally expressed as a modal
logic. There are, however, no known techniques for efficiently doing
automatic deduction directly in modal logics. We solve this problem
by taking the possible-world semantics for a modal logic of knowledge
and axiomatizing it directly in first-order logic. This means that we
reason not about what facts someone knows, but rather what possible
worlds are compatible with what identifying possible worlds with the
situations before and after an action is performed. We use these
notions to express what knowledge a person must have in order to
perform a given action and what knowledge a person acquires by
carrying out a given action. Finally, we consider some
domain-specific control heuristics that are useful for doing
deductions in this formalism, and we present several examples of
deductions produced by applying these heuristics.

%A MARTIN A. FISCHLER
%A PHYLLIS BARRETT
%T AN ICONIC TRANSFORM FOR SKETCH COMPLETION AND SHAPE ABSTRACTION
%R Technical Note 195
%I SRI International
%C Menlo Park, California
%D OCTOBER 1979
%X This paper shows how a simple label propagation technique, in
 conjunction
with some novel ideas about how labels can be applied to an image to
express semantic knowledge, lead to the simplification of a number of
diverse and difficult image analysis tasks (e.g., sketch completion
and shape abstraction). A single algorithm technique, based on
skeleton and distance transform concepts, is applied to appropriately
labeled images to obtain the desired results. A key point is that the
initial semantic labeling is not required at every location in the
image, but only at those few critical locations where significant
changes or discontinuities occur.

%A J. MARTIN TENENBAUM
%A HARRY G. BARROW
%A ROBERT C. BOLLES
%A MARTIN A. FISCHLER
%A HELEN C. WOLF
%T MAP-GUIDED INTERPRETATION OF REMOTELY-SENSED IMAGERY
%R Technical Note 196
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1979
%X A map-guided approach
to interpretation of remotely sensed imagery is described, with
emphasis on applications involving continuous monitoring of
predetermined ground sites. Geometric correspondence between a sensed
image and a symbolic reference map is established in an initial stage
of processing by adjusting parameters of a sensor model so that image
features predicted from the map optimally match corresponding features
extracted from the sensed image. Information in the map is then used
to constrain where to look in an image and what to look for. With
such constraints, previously intractable remote sensing tasks can
become feasible, even easy, to automate. Four illustrative examples
are given, involving the monitoring of reservoirs, roads, railroad
yards, and harbors.

%A KURT G. KONOLIGE
%T A FRAMEWORK FOR A PORTABLE NATURAL LANGUAGE INTERFACE TO LARGE DATA BASES
%R Technical Note 197
%I SRI International
%C Menlo Park, California
%D OCTOBER 1979
%X A framework is proposed
for developing a portable natural language interface to large data
bases. A discussion of problems arising from portability leads to the
identification of a key concept of the framework: a conceptual schema
for representing a user's model of the domain as distinct from the
data base schema. The notions of conceptual completeness and
linguistic coverage are shown to be natural consequences of this
framework. An implementation of the framework, called D-LADDER, is
presented, and some preliminary performance results reported.

%A HARRY G. BARROW
%T ARTIFICIAL INTELLIGENCE: STATE OF THE ART
%R Technical Note 198
%I SRI International
%C Menlo Park, California
%D OCTOBER 1979
%X NONE

%A JANE J. ROBINSON
%T THEORETICAL FOUNDATIONS OF LINGUISTICS AND AUTOMATIC TEXT PROCESSING
%R Technical Note 199
%I SRI International
%C Menlo Park, California
%D OCTOBER 1979
%X Texts are viewed as purposeful transactions whose
interpretation requires inferences based on extra-linguistic as well
as on linguistic information. Text processors are viewed as systems
that model both a theory of text and a theory of information
processing. The interdisciplinary research required to design such
systems have a common center, conceptually, in the development of new
kinds of lexical information, since words are not only linguistics
objects, they are also psychological objects that evoke experiences
from which meanings can be inferred. Recent developments in
linguistic theory seem likely to promote more fruitful cooperation and
integration of linguistic research with research on test processing.

%A M. A. FISCHLER, J. M. TENENBAUM,
%A H. C. WOLF
%T AERIAL IMAGERY USING A MULTISOURCE KNOWLEDGE INTEGRATION TECHNIQUE
%R Technical Note 200
%I SRI International
%C Menlo Park, California
%D OCTOBER 1979 (revised December 1979)
%X This paper describes a computer-based approach to the
problem of detecting and precisely delineating roads, and similar
line-like" structures, appearing in low-resolution aerial imagery.
The approach is based on a new paradigm for combining local
information from multiple, and possibly incommensurate, sources,
including various line and edge detection operators, map knowledge
about the likely path of roads through an image, and generic knowledge
about roads (e.g., connectivity, curvature, and width costraints).
The final interpretation of the scene is achieved by using either a
graph search or dynamic programming technique to optimize a global
figure of merit. Implementation details and experimental results are
included.

%A JERRY H. HOBBS
%A DAVID A. EVANS
%T CONVERSATION AS PLANNED BEHAVIOR
%R Technical Note 203
%I SRI International
%C Menlo Park, California
%D DECEMBER 1979
%X Perhaps the most promising working hypothesis for the
study of conversation is that the participants can be viewed as using
planning mechanisms much like those developed in artificial
intelligence. In this paper, a framework for investigating
conversation, which for convenience will be called the Planning
Approach, is developed from this hypothesis. It suggests a style of
analysis to apply to conversation, analysis in terms of the
participants' goals, plans, and beliefs, and it indicates a consequent
program of research to be pursued. These are developed in detail
in Part 2.
 Parts 3 and 4 are devoted to the microanalysis of an actual
free-flowing conversation, as an illustration of the style of
analysis. In the process, order is discovered in a conversation that
on the surface seems quite incoherent. The microanalysis suggests
some ways in which the planning mechanisms common in artificial
intelligence will have to be extended to deal with conversation, and
these are discussed in Part 5. In Part 6, certain methdological
difficulties are examined. Part 7 addresses the problem that arises
in this approach of what constitutes successful communication.

%A JERRY R. HOBBS
%T METAPHOR, METAPHOR SCHEMATA, AND SELECTIVE INFERENCING
%R Technical Note 204
%I SRI International
%C Menlo Park, California
%D DECEMBER 1979
%X The importance of spatial and other metaphors is
demonstrated. An approach to handling metaphor in a computational
framework is described, based on the idea of selective inferencing.
Three examples of metaphors are examined in detail in this light--a
simple metaphor, a spatial metaphor schema, and a novel metaphor.
Finally, there is a discussion, from this perspective, of the
analogical processes that underlie metaphor in this approach and what
the approach says about several classical questions about metaphor.

%A JANE J. ROBINSON
%T DIAGRAM: A GRAMMAR FOR DIALOGUES
%R Technical Note 205
%I SRI International
%C Menlo Park, California
%D FEBRUARY 1980
%X This paper presents an explanatory overview of a large
and complex grammar, DIAGRAM, that is used in a computer system for
interpreting English dialogue. DIAGRAM analyzes all of the basic
kinds of phrases and sentences and many quite complex ones as well.
It is not tied to a particular domain of application, and it can be
extended to analyze additional constructions, using the formalism in
which it is currently written. For every expression it analyzes,
DIAGRAM provides an annotated description of the structural relations
holding among its constituents. The annotations provide important
information for other parts of the system that interpret the
expression in the context of a dialogue.
 DIAGRAM is an augmented phrase structure grammar. Its rule
procedures allow phrases to inherit attributes from their constituents
and to acquire attributes from the larger phrases in which they
themselves are constituents. Consequently, when these attributes are
used to set context-sensitive constraints on the acceptance of an
analysis, the contextual constraints can be imposed by conditions on
dominance as well as conditions on constituency. Rule procedures can
also assign scores to an analysis, rating some applications of a rule
as probable or as unlikely. Less likely analyses can be ignored by
the procedures that interpret the utterance.
 In assigning categories and writing the rule statements and
procedures for DIAGRAM, decisions were guided by consideration of the
functions that phrases serve in communication as well as by
considerations of efficiency in relating syntactic analyses to
propositional content. The major decisions are explained and
illustrated with examples of the rules and the analyses they provide.
Some contrasts with transformational grammars are pointed out and
problems that motivate a plan to use redundancy rules in the future
are discussed. (Redundancy rules are meta-rules that derive new
constituent-structure rules from a set of base rules, thereby
achieving generality of syntactic statement without having to perform
transformations on syntactic analyses.) Other extensions of both
grammar and formalism are projected in the concluding section.
Appendices provide details and samples of the lexicon, the rule
statements, and the procedures, as well as analyses for several
sentences that differ in type and structure.

%A ANN E. ROBINSON
%T THE INTERPRETATION OF VERB PHRASES IN DIALOGS
%R Technical Note 206
%I SRI International
%C Menlo Park, California
%D JANUARY 1980
%X This paper discusses two problems central to the
interpretation of utterances: determining the relationship between
actions described in an utterance and events in the world, and
inferring the state of the world'' from utterances. Knowledge of the
language, knowledge about the general subject being discussed, and
knowledge about the current situation are all necessary for this. The
problem of determining an action referred toby a verb phrase is
analogous to the problem of determining the object referred to by a
noun phrase.
 This paper presents an approach to the problems of verb phrases
resolution in which knowledge about language, the problem domain, and
the dialog itself is combined to interpret such references. Presented
and discussed are the kinds of knowledge necessary for interpreting
references to actions, as well as algorithms for using that knowledge
in interpreting dialog utterances about ongoing tasks and for drawing
inferences about the task situation that are based on a given
interpretation.

%A ANN E. ROBINSON
%A DOUGLAS E. APPELT
%A BARBARA J. GROSZ
%A GARY G. HENDRIX
%A JANE J. ROBINSON
%T INTERPRETING NATURAL-LANGUAGE UTTERANCES IN DIALOGS ABOUT TASKS
%R Technical Note 210
%I SRI International
%C Menlo Park, California
%D MARCH 1980
%X This paper describes the results of a three-year
research effort investigating the knowledge and processes needed for
participation in natural-language dialogs about ongoing
mechanical-assembly tasks. Major concerns were the ability to
interpret and respond to utterances within the dynamic environment
effected by progress in the task, as well as by the concommitant
shifting dialog context.
 The research strategy followed was to determine the kinds of
knowledge needed, to define formalisms for encoding them and
procedures for reasoning with them, to implement those formalisms and
procedures in a computer system called TDUS, and then to test them by
exercising the system.
 Principal accomplishments include: development of a framework for
encoding knowledge about linguistic processes; encoding of a grammar
for recognizing many of the syntactic structures of English;
development of the concept of focusing,'' which clarifies a major role
of context; development of a formalism for representing knowledge
about processes, and procedures for reasoning about them; development
of an overall framework for describing how different types of
knowledge interact in the communication process; development of a
computer system that not only demonstrates the feasibility of the
various formalisms and procedures, but also provides a research tool
for testing new hypotheses about the communication process.
CONTENT INDICATORS: 3.60, 3.69, 3.42
KEY WORDS: Natural-language understanding, Task-oriented dialogs

%A MARTIN A. FISCHLER
%A ROBERT C. BOLLES
%T RANDOM SAMPLE CONSENSUS: A PARADIGM FOR MODEL FITTING
WITH APPLICATIONS TO IMAGE ANALYSIS AND AUTOMATED CARTOGRAPHY
%R Technical Note 213
%I SRI International
%C Menlo Park, California
%D MARCH 1980
%X In this paper we introduce a new paradigm, Random
Sample Consensus (RANSAC), for fitting a model to experimental data.
RANSAC is capable of interpreting/smoothing data containing a
significant percentage of gross errors, and thus is ideally suited for
applications in automated image analysis where interpretation is based
on the data provided by error-prone feature detectors. A major
portion of this paper describes the application of RANSAC to the
Location Determination Problem (LDP): given an image depicting a set
of landmarks with known locations, determine that point in space from
which the image was obtained. In response to a RANSAC requirement, we
derive new results on the minimum number of landmarks needed to obtain
a solution, and present algorithms for computing these
minimum-landmark solutions in closed form. These results provide the
basis for an automatic system that can solve the LDP under difficult
viewing and analysis conditions. Implementation details and
computational examples are also presented.

%A LYNN H. QUAM
%T A STORAGE REPRESENTATION FOR EFFICIENT ACCESS TO
LARGE MULTIDIMENSIONAL ARRAYS
%R Technical Note 220
%I SRI International
%C Menlo Park, California
%D APRIL 1980
%X This paper addresses problems associated with accessing
elements of large multidimensional arrays when the order of access is
either unpredictable or is orthogonal to the conventional order of
array storage. Large arrays are defined as arrays that are larger
than the physical memory immediately available to store them. Such
arrays must be accessed either by the virtual memory system of the
computer and operating system, or by direct input and output of blocks
of the array to a file system. In either case, the direct result of
an inappropriate order of reference to the elements of the array is
the very time-consuming movement of data between levels in the memory
hierarchy, often costing factors of three orders of magnitude in
algorithm performance.
 The access to elements of large arrays is decomposed into three
steps: transforming the subscript values of an n-dimensional array
into the element number in a one-dimensional virtual array, mapping
the virtual array position to physical memory position, and accessing
the array element in physical memory. The virtual-to-physical mapping
step is unnecessary on computer systems with sufficiently large
virtual address spaces. This paper is primarily concerned with the
first step.
 A subscript transformation is proposed that solves many of the
order-of-access problems associated with conventional array storage.
This transformation is based on an additive decomposition of the
calculation of element number in the array into the sum of a set of
integer functions applied to the set of subscripts as follows:
element-number(i,j,...) = fi(i) + fj(j) + ...
 Choices for the transformation functions that minimize access
time to the array elements depend on the characteristics of the
computer system's memory hierarchy and the order of accesses to the
array elements. It is conjectured that given appropriate models for
system and algorithm access characteristics, a pragmatically optimum
choice can be made for the subscript transformation functions. In
general these models must be stochastic, but in certain cases
deterministic models are possible.
 Using tables to evaluate the functions fi and fj makes
implementation very efficient with conventional computers. When the
array accesses are made in an order inappropriate to conventional
array storage order, this scheme requires far less time than for
conventional array-accessing schemes; otherwise, accessing times are
comparable.
 The semantics of a set of procedures for array access, array
creation, and the association of arrays with file names is defined.
For computer systems with insufficient virtual memory, such as the
PDP-10, a software virtual-to-physical mapping scheme is given in
Appendix C. Implementations are also given in the appendix for the
VAX and PDP-10 series computers to access pixels of large images
stored as two-dimensional arrays of n bits per element.

%A JAY M. TENENBAUM, MARTIN A. FISCHLER,
%A HARRY G. BARROW
%T SCENE MODELING: A STRUCTURAL BASIS FOR IMAGE DESCRIPTION
%R Technical Note 221
%I SRI International
%C Menlo Park, California
%D JULY 1980
%X Conventional statistical approaches to image modeling are
fundamentally limited because they take no account of the underlying
physical structure of the scene nor of the image formation process.
The image features being modeled are frequently artifacts of viewpoint
and illumination that have no intrinsic significance for higher-level
interpretation. In this paper a structural approach to modeling is
argued for that explicitly relates image appearance to the scene
characteristics from which it arose. After establishing the necessity
for structural modeling in image analysis, a specific representation
for scene structure is proposed and then a possible computational
paradigm for recovering this description from an image is described.

%A HARRY G. BARROW,
%A J. MARTIN TENENBAUM
%T RECONSTRUCTING SMOOTH SURFACES FROM PARTIAL, NOISY INFORMATION
%R Technical Note 222
%I SRI International
%C Menlo Park, California
%D JULY 1980
%X Interpolating smooth surfaces from boundary conditions
is a ubiquitous problem in early visual processing. We describe a
solution for an important special case: the interpolation of surfaces
that are locally spherical or cylindrical from initial orientation
values and constraints on orientation. The approach exploits an
observation that components of the unit normal vary linearly on
surfaces of uniform curvature, which permits implementation using
local parallel processes. Experiments on spherical and cylindrical
test cases have produced essentially exact reconstructions, even when
boundary values were extremely sparse or only partially constrained.
Results on other test cases seem in reasonable agreement with human
perception.

%A DANIEL SAGALOWICZ
%T A D-LADDER USER'S GUIDE
%R Technical Note 224
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1980
%X D-LADDER (DIAMOND-based Language Access to Distributed
Data with Error Recovery) is a computer system designed to provide
answers to questions posed at the terminal in a subset of natural
language regarding a distributed data base of naval command and
control information. The system accepts natural-language questions
about the data. For each question D-LADDER plans a sequence of
appropriate queries to the data base management system, determines on
which machines the queries are to be processed, establishes links to
those machines over the ARPANET, monitors the processing of the
queries and answer to the original question.
 This user's guide is intended for the person who knows how to log
in to the host operating system, as well as how to enter and edit a
line of text. It does not explain how D-LADDER works, but rather how
to use it on a demonstration basis.

%A MICHAEL AGAR
%A JERRY R. HOBBS
%T INTERPRETING DISCOURSE: COHERENCE AND THE ANALYSIS OF ETHNOGRAPHIC INTERVIEWS
%R Technical Note 225
%I SRI International
%C Menlo Park, California
%D AUGUST 1980
%X The data we analyze is from a series of life history
interviews with a career heroin addict in New York, collected by Agar
(1981). We analyze this data in terms of a combination of two AI
approaches to discourse. The first is work on the inferencing that
must take place in people's comprehension and production of natural
language discourse. The second approach to discourse applies work on
planning to the planning of individual speech acts and to the plans
speakers develop for effecting their goals in larger stretches of
conversation.
 In this paper we first outline how we apply these approaches to
the ethnographic data. We discuss three kinds of coherence in terms
of which we analyze a text, and then describe our method more
generally. We next give an example of the method of microanalysis on
a short fragment of an interview, and then show how the beliefs, goals
and concerns that the microanalysis has revealed are tied in with the
rest of the corpus. Finally, we discuss the significance of this work
for ethnography.

%A ZOHAR MANNA
%A RICHARD WALDINGER
%T PROBLEMATIC FEATURES OF PROGRAMMING LANGUAGES:
SITUATIONAL-CALCULUS APPROACH
(PART I: ASSIGNMENT STATEMENTS)
%R Technical Note 226
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1980
%X Certain features of programming languages, such as data
structure operations and procedure call mechanisms, have been found to
resist formalization by classical techniques. An alternate approach
is presented, based on a situational calculus,'' which makes explicit
reference to the states of a computation. For each state, a
distinction is drawn between an expression, its value, and the
location of the value.
 Within this conceptual framework, the features of a programming
language can be described axiomatically. Programs in the language can
then be synthesized, executed, verified, or transformed by performing
deductions in this axiomatic system. Properties of entire classes of
programs, and of programming languages, can also be expressed and
proved in this way. The approach is amenable to machine
implementation.
 In a situational-calculus formalism it is possible to model
precisely many problematic'' features of programming languages,
including operations on such data structures as arrays, pointers,
lists, and records, and such procedure call mechanisms as
call-by-reference, call-by-value, and call-by-name. No particular
obstacle is presented by aliasing between variables, by declarations,
or by recursive procedures.
 The paper is divided into three parts, focusing respectively on
the assignment statement, on data structure operations, and on
procedure call mechanisms. In this first part, we introduce the
conceptual framework to be applied throughout and present the
axiomatic definition of the assignment statement. If suitable
restrictions on the programming language are imposed, the well-known
Hoare assignment axiom can then be proved as a theorem. However, our
definition can also describe the assignment statement of unrestricted
programming languages, for which the Hoare axiom does not hold.

%A NORMAN HAAS
%A GARY G. HENDRIX
%T AN APPROACH TO ACQUIRING AND APPLYING KNOWLEDGE
%R Technical Note 227
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1980
%X The problem addressed in this paper is how to enable a
computer system to acquire facts about new domains from tutors who are
experts in their respective fields, but who have little or no training
in computer science. The information to be acquired is that needed to
support question-answering activities. The basic acquisition approach
is learning by being told.'' We have been especially interested in
exploring the notion of simultaneously learning not only new concepts,
but also the linguistic constructions used to express those concepts.
As a research vehicle we have developed a system that is preprogrammed
with deductive algorithms and a fixed set of syntactic/semantic rules
covering a small subset of English. It has been endowed with
sufficient seen concepts and seed vocabulary to support effective
tutorial interaction. Furthermore, the system is capable of learning
new concepts and vocabulary, and can apply its acquired knowledge in a
range of problem-solving situations.

%A GARY G. HENDRIX
%A WILLIAM H. LEWIS
%T TRANSPORTABLE NATURAL-LANGUAGE INTERFACES TO DATABASES
%R Technical Note 228
%I SRI International
%C Menlo Park, California
%D APRIL 1981
%X Several computer systems have now been constructed that
allow users to access databases by posing questions in natural
languages, such as English. When used in the restricted domains for
which they have been especially designed, these systems have achieved
reasonably high levels of performance. However, these systems require
the encoding of knowledge about the domain of application in complex
data structures that typically can be created for a new database only
with considerable effort on the part of a computer professional who
has had special training in computational linguistics and the use of
databases.
 This paper describes initial work on a methodology for creating
natural-language processing capabilities for new databases without the
need for intervention by specially trained experts. The approach is
to acquire logical schemata and lexical information through simple
interactive dialogues with someone who is familiar with the form and
content of the database, but unfamiliar with the technology of
natural-language interfaces. A prototype system using this
methodology is described and an example transcript is presented.

%A NILS J. NILSSON
%T THE INTERPLAY BETWEEN EXPERIMENTAL AND THEORETICAL METHODS
IN ARTIFICIAL INTELLIGENCE
%R Technical Note 229
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1980
%X This note alleges that there is a dichotomy between
theoretical and experimental work in Artificial Intelligence (AI).
The reasons for this dichotomy are discussed, and AI is compared with
other, more mature disciplines in which there is closer cooperation
between experimental and theoretical branches. Some recommendations
are given for achieving this needed cooperation.

%A GARY G. HENDRIX
%T KLAUS: A SYSTEM FOR MANAGING INFORMATION AND COMPUTATIONAL RESOURCES
%R Technical Note 230
%I SRI International
%C Menlo Park, California
%D OCTOBER 1980
%X This report presents a broad-brush description of the
basic goals and philosophy of a research program at SRI International
(SRI) aimed at developing the technology needed to support systems
that can be tutored in English about new subject areas, and that can
therefore aid the initial or subsequent user in filing and retrieving
information, and in conveniently applying to the new subject area
other computer software, such as data-base management systems (DBMS),
planners, schedulers, report generators, simulators and the like.
These systems, which we call Knowledge Learning and Using Systems
(KLAUS), are intended to act as brokers between the user's needs, as
expressed in the user's terms, and the resources available in a rich
computational environment.

%A KURT KONOLIGE
%T A FIRST-ORDER FORMALIZATION OF KNOWLEDGE AND ACTION FOR A
MULTIAGENT PLANNING SYSTEM
%R Technical Note 232
%I SRI International
%C Menlo Park, California
%D DECEMBER 1980
%X We are interested in constructing a computer agent
whose behavior will be intelligent enough to perform cooperative tasks
involving other agents like itself. The construction of such agents
has been a major goal of artificial intelligence research. One of the
key tasks such an agent must perform is to form plans to carry out its
intentions in a complex world in which other planning agents also
exist. To construct such agents, it will be necessary to address a
number of issues that concern the interaction of knowledge, actions,
and planning. Briefly stated, an agent at planning time must take
into account what his future states of knowledge will be if he is to
form plans that he can execute; and if he must incorporate the plans
of other agents into his own, then he must also be able to reason
about the knowledge and plans of other agents in an appropriate way.
These ideas have been explored by several researchers, especially
McCarthy and Hayes [McCarthy and Hayes, 1969] and Moore [Moore 1980].
 Despite the importance of this problem, there has not been a
great deal of work in the area of formalizing a solution. Formalisms
for both action and knowledge separately have been examined in some
depth, but there have been few attempts at a synthesis. The exception
to this is Moore's thesis on reasoning about knowledge and action
[Moore 1980], for which a planner has been recently proposed [Appelt
1980]. Moore shows how a formalism based on possible-world semantics
can be used to reason about the interaction of knowledge and action.
In this paper we develop an alternative formalism for reasoning about
knowledge, belief, and action; we show how this formalism can be used
to deal with several well-known problems, and then describe how it
could be used by a plan constructing systems.

%A MARTIN A. FISCHLER
%T COMPUTATIONAL STRUCTURES FOR MACHINE PERCEPTION
%R Technical Note 233
%I SRI International
%C Menlo Park, California
%D JANUARY 1981
%X This note discusses the adequacy of current computer
architectures to serve as a base for building machine vision systems.
Arguments are presented to show that perceptual problems cannot be
completely formalized and dealt with in a closed abstract system. The
conclusion is that the digital computer, organized as a
general-purpose symbol processor, cannot serve as an adequate
instrument for achieving a human-like visual capability.

%A GARY G. HENDRIX
%A EARL D. SACERDOTI
%T NATURAL-LANGUAGE PROCESSING (PART ONE: THE FIELD IN PERSPECTIVE)
%R Technical Note 237
%I SRI International
%C Menlo Park, California
%D JULY 1981
%X This article deals with the problems of enabling
computers to communicate with humans in natural languages, such as
English and French, as distinguished from formal languages, such as
BASIC and PASCAL. Major issues in natural-language processing are
discussed by examining several experimental computer systems developed
over the last decade. The intent of the authors is to demonstrate
that natural-language processing techniques are useful now, to reveal
the richness of the computations performed by human natural-language
communicators, and to explain why the fluent use of natural language
by machines remains an elusive aspiration.

%A ROBERT C. MOORE
%T AUTOMATIC DEDUCTION FOR COMMONSENSE REASONING: AN OVERVIEW
%R Technical Note 239
%I SRI International
%C Menlo Park, California
%D APRIL 1981
%X How to enable computers to draw conclusions
automatically from bodies of facts has long been recognized as a
central problem in artificial-intelligence (AI) research. Any attempt
to address this problem requires choosing an application (or type of
application), a representation for bodies of facts, and methods for
deriving conclusions. This article provides an overview of the issues
involved in drawing conclusions by means of deductive inference from
bodies of commonsense knowledge represented by logical formulas. We
first briefly review the history of this enterprise: its origins, its
fall into disfavor, and its recent revival. We show why applications
involving certain types of incomplete information resist solution by
other techniques, and how supplying domain-specific control
information seems to offer a solution to the difficulties that
previously led to disillusionment with automatic deduction. Finally,
we discuss the relationship of automatic deduction to the new field of
logic programming,'' and we survey some of the issues that arise in
extending automatic-deduction techniques to nonstandard logics.

%A DONALD E. WALKER
%A JERRY R. HOBBS
%T NATURAL LANGUAGE ACCESS TO MEDICAL TEXT
%R Technical Note 240
%I SRI International
%C Menlo Park, California
%D MARCH 1981
%X This paper describes research on the development of a
methodology for representing the information in texts and of
procedures for relating the linguistic structure of a request to the
corresponding representations. The work is being done in the context
of a prototype system that will allow physicians and other health
professionals to access information in a computerized textbook of
hepatitis through natural language dialogues. The interpretation of
natural language queries is derived from DIAMOND/DIAGRAM, a
linguistically motivated, domain-independent natural language
interface developed at SRI. A text access component is being
developed that uses representations of the propositional content of
text passages and of the hierarchical structure of the text as a whole
to retrieve relevant information.

%A ROBERT C. MOORE
%T PROBLEMS IN LOGICAL FORM
%R Technical Note 241
%I SRI International
%C Menlo Park, California
%D APRIL 1981
%X Most current theories of natural-language processing
propose that the assimilation of an utterance involves producing an
expression or structure that in some sense represents the literal
meaning of the utterance. It is often maintained that understanding
what an utterance literally means consists in being able to recover
such a representation. In philosophy and linguistics this sort of
representation is usually said to display
the ``logical form'' of an utterance.
 This paper surveys some of the key problems that arise in
defining a system of representation for the logical forms of English
sentences and suggests possible approaches to their solution. We
first look at some general issues relating to the notion of logical
form, explaining why it makes sense to define such a notion only for
sentences in context, not in isolation, and we discuss the
relationship between research on logical form and work on knowledge
representation in artificial intelligence. The rest of the paper is
devoted to examining specific problems in logical form. These include
the following: quantifiers; events, actions and processes; time and
space; collective entities and substances; propositional attitudes and
modalities; questions and imperatives.

%A RENE REBOH
%T KNOWLEDGE-ENGINEERING TECHNIQUES AND TOOLS
%R Technical Note 243
%I SRI International
%C Menlo Park, California
%D May 1981
%X Techniques and tools to assist in several phases of the
knowledge-engineering process for developing an expert system are
explored.
 A sophisticated domain-independent network editor is described
that uses knowledge about the representational and computational
formalisms of the host consultation system to watch over the
knowledge-engineering process and to give the knowledge engineer a
convenient environment for developing, debugging, and maintaining the
knowledge base.
 We also illustrate how partial matching techniques can assist in
maintaining the consistency of the knowledge base (in form and
content) as it grows, and can support a variety of features that will
enhance the interaction between the system and the user and make a
knowledge-based consultation system behave more intelligently.
 Although these techniques and features are illustrated in terms
of the Prospector environment, it will be clear to the reader how
these techniques can be applied in other environments.

%A GRAHAME B. SMITH
%T DETECTION OF RIVERS IN LOW-RESOLUTION AERIAL IMAGERY
%R Technical Note 244
%I SRI International
%C Menlo Park, California
%D JUNE 1981
%X This paper describes an operator for detecting rivers
in low-resolution aerial imagery. The operator provides results that
would allow graph-traversing routines to delineate these structures.
The approach is to look for the typical river profile involving not
only the water component of the river, but its surrounding vegetation
as well.

%A ANN ROBINSON
%A DAVID WILKINS
%T AN INTERACTIVE PLANNING SYSTEM
%R Technical Note 245
%I SRI International
%C Menlo Park, California
%D JUNE 1981
%X A principal goal of our planning and plan execution
research is to develop a computer system that interacts with a person
planning some activity. The system, designed to be independent of the
problem area in which the planning takes place, will allow the person
to (1) represent the problem area and the actions that may be
performed in it; (2) explore alternative plans for performing the
activity; (3) monitor the execution of a plan so produced; and (4)
modify the plan as needed during its execution. The system currently
being tested allows a person to produce a plan inter- actively,
suggesting alternative actions, showing the effects of actions on the
situation, checking for problems in the plan, and (occasionally)
suggesting corrections for such problems. The plan is represented as
a hierarchy of actions linked together in a network, generally called
a procedural network.''
 Current areas of investigation include the following: (1)
development of representations for encoding information about a given
problem area, stressing the representation of actions that may be
performed in it; (2) development of computational methods for
identifying difficulties in a plan, such as the overallocation of a
resource or the possible effect of one action on the successful
performance of subsequent actions; (3) development of strategies for
deciding which actions and action sequences should be included in a
plan; (4) development of effective communication with the user,
including determining which and how much information should be
communicated, and how best to present it.

%A ZOHAR MANNA
%A RICHARD WALDINGER
%T DEDUCTIVE SYNTHESIS OF THE UNIFICATION ALGORITHM
%R Technical Note 246
%I SRI International
%C Menlo Park, California
%D JULY 1981
%X The deductive approach is a formal program construction
method in which the derivation of a program from a given specification
is regarded as a theorem-proving task. To construct a program whose
output satisfies the conditions of the specification, we prove a
theorem stating the existence of such an output. The proof is
restricted to be sufficiently constructive so that a program computing
the desired output can be extracted directly from the proof. The
program we obtain is applicative and may consist of several mutually
recursive procedures. The proof constitutes a demonstration of the
correctness of this program.
 To exhibit the full power of the deductive approach, we apply it
to a nontrivial example--the synthesis of a unification algorithm.
Unification is the process of finding a common instance of two
expressions. Algorithms to perform unification have been central to
many theorem-proving systems and to some programming-language
processors.
 The task of deriving a unification algorithm automatically is
beyond the power of existing program synthesis systems. In this paper
we use the deductive approach to derive an algorithm from a simple,
high-level specification of the unification task. We will identify
some of the capabilities required of a theorem-proving system to
perform this derivation automatically.

%A NILS J. NILSSON
%T ARTIFICIAL INTELLIGENCE: ENGINEERING, SCIENCE OR SLOGAN?
%R Technical Note 248
%I SRI International
%C Menlo Park, California
%D JULY 1981
%X This paper presents the view that artificial
intelligence (AI) is primarily concerned with propositional languages
for representing knowledge and with techniques for manipulating these
representations. In this respect, AI is analogous to applied
mathematics; its representations and techniques can be applied in a
variety of other subject areas. Typically, AI research is (or should
be) more concerned with the general form and properties of
representational languages and methods than it is with the content
being described by these languages. Notable exceptions involve
commonsense'' knowledge about the everyday world (no other specialty
claims this subject area as its own), and world (no knowledge about
the properties and uses of knowledge itself). In these areas AI is
concerned with content as well as form. We also observe that the
technology that seems to underlie peripheral sensory and motor
activities (analogous to low-level animal or human vision and muscle
control) seems to be quite different from the technology that seems to
underlie cognitive reasoning and problem solving. Some definitions of
AI would include peripheral as well as cognitive processes; here we
argue against including the peripheral processes.

%A ROBERT C. MOORE
%T PRACTICAL NATURAL LANGUAGE PROCESSING BY COMPUTER
%R Technical Note 251
%I SRI International
%C Menlo Park, California
%D OCTOBER 1981
%X This paper describes the state of the art in practical
computer systems for natural-language processing. We first consider
why one would want to use natural language to communicate with
computers at all, looking at both general issues and specific
applications. Next we examine what it really means for a system to
have a natural-language capability. This is followed by a discussion
of some major limitations of current technology. The bulk of the
paper is devoted to looking in detail at a single application of
natural-language processing: database retrieval by natural-language
query. We lay out an overall system architecture, explaining what
types of processing and information are required. Then we look at two
general classes of systems, special-purpose and general-purpose,
explaining how they differ and their relative advantages and
disadvantages. Afterwards we point out some remaining problems that
will require addition basic research. Finally we conclude by
discussing when language-processing technology at various levels of
capability is likely to be commercially practical, and what is may
cost to develop and use applications of that technology.

%A NORMAN HAAS
%A GARY HENDRIX
%T MACHINE LEARNING FOR INFORMATION MANAGEMENT
%R Technical Note 252
%I SRI International
%C Menlo Park, California
%D JULY 1981
%X This paper discusses machine learning in the context of
information management. The core idea is that of a compiler system
that can hold a conversation with a user in English about his specific
domain of interest, subsequently retrieve and display information
conveyed by the user, and apply various types of external software
systems to solve user problems.
 The specific learning problems discussed is how to enable
computer systems to acquire information about domains with which they
are unfamiliar from people who are expert in those domains, but have
little or no training in computer science. The information to be
acquired is that needed to support question-answering or fact
retrieval tasks, and the type of learning to be employed is learning
by being told. Reflecting the intimate connection between language
and reasoning, this paper is largely concerned with the problems of
learning concepts and language simultaneously.

%A DONALD E. WALKER
%T COMPUTATIONAL STRATEGIES FOR ANALYZING THE ORGANIZATION AND USE OF INFORMATION
%R Technical Note 253
%I SRI International
%C Menlo Park, California
%D JULY 1981
%X This chapter describes new developments in
computer-based procedures that can improve our understanding of how
people organize and use information. Relevant recent research in
information science, computational linguistics, and artificial
intelligence is reviewed. A program of research is presented that is
producing systems that make it possible to study the organization and
use of information and, at the same time, provide more effective
support for people engaged in those activities.

%A ARMAR A. ARCHBOLD, BARBARA GROSZ,
%A DANIEL SAGALOWICZ
%T A TEAM USER'S GUIDE
%R Technical Note 254
%I SRI International
%C Menlo Park, California
%D DECEMBER 1981
%X TEAM (Transportable English Data Access Manager) is a
computer system designed to acquire information about a (local or
remote) database, and subsequently to interpret and answer questions
addressed to the database in a subset of natural language.
 The system currently includes an interactive program that
acquires information about a database from the database administrator.
The user is asked how the database is to be structured and what
language is to be used to talk about its contents. The program
augments the following components of a core natural language access
system:
 * The lexicon
 * The conceptual model of the domain (or conceptual schema)
 * The structural model of the database (or database schema).
 After these steps have been completed, the system accepts
natural-language questions about the database contents and, to the
EXTENT it is able, provides relevant responses.

%A KURT KONOLIGE
%T THE DATABASE AS MODEL: A METATHEORETIC APPROACH
%R Technical Note 255
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1981
%X This paper presents a method of formally representing
the information that is available to a user of a relational database.
The intended application area is deductive question-answering systems
that must access an existing relational database. To respond
intelligently to user inquiries, such systems must have a more
complete representation of the domain of discourse than is generally
available in the tuple sets of a relational database. Given this more
expressive representation, the problem then arises of how to reconcile
the information present in the database with the domain
representation, so that database queries can be derived to answer the
user's inquiries. Here we take the formal approach of describing a
relational database as the model of a first-order language. Another
first-order language, the metalanguage, is used both to represent the
domain of discourse, and to describe the relationship of the database
to the domain. The formal advantages of this approach are presented
and contrasted with other work in the area.

%A ARTHUR M. FARLEY
%T A PROBABILISTIC MODEL FOR UNCERTAIN PROBLEM SOLVING
%R Technical Note 256
%I SRI International
%C Menlo Park, California
%D DECEMBER 1981
%X With growing interest in the application of research to
problems that arise in real-world contexts, issues raised by
consideration of uncertain states and unreliable operators are
receiving increased attention in artificial intelligence research. In
this paper, a model is presented for dealing with such concerns. The
model is a probabilistic generalization of the familiar notion of
problem space. The specification of uncertain states and unreliable
operators is discussed. Problem-solving search methods are described.
The need for information gathering is established. Search methods are
generalized to produce tree-structured plans incorporating the use of
such operators. Several application domains for our model are
discussed.

%A BARBARA J. GROSZ
%T RESEARCH ON NATURAL-LANGUAGE PROCESSING AT SRI
%R Technical Note 257
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1981
%X Research on natural-language processing at SRI spans a
broad spectrum of activity. Two of our major current efforts are a
pair of research projects under the sponsorship of the Defense
Advanced Research Projects Agency. The TEAM project is intended to
provide natural-language access to large databases via systems that
are easily adaptable to a wide range of new application domains. The
KLAUS project is a longer-range effort to address basic research
problems in natural-language semantics, commonsense reasoning, and the
pragmatics of natural-language communication. These two projects
share a common core-language-processing system called DIALOGIC.

%A DAVID E. WILKINS
%T PARALLELISM IN PLANNING AND PROBLEM SOLVING: REASONING ABOUT RESOURCES
%R Technical Note 258
%I SRI International
%C Menlo Park, California
%D JANUARY 1982
%X The implications of allowing parallel actions in a plan
or problem solution are discussed. The planning system should take
advantage of helpful interactions between parallel branches, must
detect harmful interactions, and, if possible, remedy them. This
paper describes what is involved in this and presents some new
techniques that are implemented in an actual planning system and are
useful in seeking solutions to these problems. The most important of
these techniques, reasoning about resources, is emphasized and
explained.

%A DOUGLAS E. APPELT
%T PLANNING NATURAL-LANGUAGE UTTERANCES TO SATISFY MULTIPLE
 GOALS
%R Technical Note 259
%I SRI International
%C Menlo Park, California
%D MARCH 1982
%X This dissertation presents the results of research on a
planning formalism for a theory of natural-language generation that
will support the generation of utterances that satisfy multiple goals.
Previous research in the area of computer generation of
natural-language utterances has concentrated two aspects of language
production: (1) the process of producing surface syntactic forms from
an underlying representation, and (2) the planning of illocutionary
acts to satisfy the speaker's goals. This work concentrates on the
interaction between these two aspects of language generation and
considers the overall problem to be one of refining the specification
of an illocutionary act into a surface syntactic form, emphasizing the
problems of achieving multiple goals in a single utterance.
 Planning utterances requires an ability to reason in detail about
what the hearer knows and wants. A formalism, based on a
possible-worlds semantics of an intentional logic of knowledge and
action, was used for representing the effects of illocutionary acts
and the speaker's beliefs about the hearer's knowledge of the world.
Techniques are described that enable a planning system to use the
representation effectively.
 The language-planning theory and knowledge representation are
embodied in a computer system called KAMP (Knowledge And Modalities
Planner), which plans both physical and linguistic actions, given a
high-level description of the speaker's goals.
 The research has application to the design of gracefully
interacting computer systems, multiple-agent planning systems, and the
planning of knowledge acquisition.

%A ZOHAR MANNA
%A RICHARD WALDINGER
%T SPECIAL RELATIONS IN PROGRAM-SYNTHETIC DEDUCTION
%R Technical Note 260
%I SRI International
%C Menlo Park, California
%D MARCH 1982
%X Program synthesis is the automated deviation of a
computer program from a given
specification. In the ``deductive'' ``approach'', the
 synthesis of a program is regarded as a theorem-proving
problem; the desired program is constructed as a by-product of the
proof. This paper presents a formal deduction system for program
synthesis, with special features for handling equality, the
equivalence connective, and ordering relations.
 In proving theorems involving the equivalence connective, it is
awkward to remove all the quantifiers before attempting the proof.
The system therefore deals with ``partially'' ``skolemized''
 ``sentences'', in
which some of the quantifiers may be left in place. A rule is
provided for removing individual quantifiers when required after the
proof is under way.
 The system is also ``nonclausal''; i.e., the theorem does not need
to be put into conjunctive normal form. The equivalence, implication,
and other connectives may be left intact.

%A STEPHEN T. BARNARD
%A MARTIN A. FISCHLER
%T COMPUTATIONAL STEREO
%R Technical Note 261
%I SRI International
%C Menlo Park, California
%D MARCH 1982
%X Perception of depth is a central problem in machine
vision. Stereo is an attractive technique for depth perception
because, compared to monocular techniques, it leads to more direct,
unambiguous, and quantitative depth measurements, and unlike such
active" approaches as radar and laser ranging, it is suitable in
almost all application domains.
We broadly define computational stereo as the recovery of the
three-dimensional characteristics of a scene from multiple images
taken from different points of view. The first part of the paper
identifies and discusses each of the functional components of the
computational stereo paradigm: image acquisition, camera modeling,
feature acquisition, matching, depth determination, and interpolation.
The second part discusses the criteria that are important for
evaluating the effectiveness of various computational stereo
techniques. The third part surveys a representative sampling of
computational stereo research.

%A BARBARA J. GROSZ
%T TEAM: A TRANSPORTABLE NATURAL-LANGUAGE INTERFACE SYSTEM
%R Technical Note 263R
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1982
%X A major benefit of using natural language to access the
information in a database is that it shifts onto the system to burden
of mediating between two views of the data: the way in which the data
is stored (the database view''), and the way in which an end-user
thinks about it (the user's view''). Database information is recorded
in terms of files, records, and fields, while natural-language
expressions refer to the same information in terms of entities and
relationships in the world. A major problem in constructing a
natural-language interface is determining how to encode and use the
information needed to bridge these two views. Current
natural-language interface systems require extensive efforts by
specialists in natural-language processing to provide them with the
information they need to do the bridging. The systems are, in effect,
handtailored to provide access to particular databases.
 This paper focuses on the problem of constructing ``transportable''
natural-language interfaces, i.e., systems that can be adapted to
provide access to databases for which they were not specifically
handtailored. It describes an initial version of a transportable
system, called TEAM (for ``T''ransportable ``E''nglish
 ``A''ccess Data
``M''anager). The hypothesis underlying the research described in
 this
paper is that the information required for the adaptation can be
obtained through an interactive dialogue with database management
personnel who are not familiar with natural-language processing
techniques.

%A ROBERT C. MOORE
%T THE ROLE OF LOGIC IN KNOWLEDGE REPRESENTATION AND COMMONSENSE REASONING
%R Technical Note 264
%I SRI International
%C Menlo Park, California
%D JUNE 1982
%X This paper examines the role that formal logic ought to play
in representing and reasoning with commonsense knowledge. We take
issue with the commonly held view (as expressed by Newell [1980]) that
the use of representations based on formal logic is inappropriate in
most applications of artificial intelligence. We argue to the
contrary that there is an important set of issues, involving
incomplete knowledge of a problem situation, that so far have been
addressed only by systems based on formal logic and deductive
inference, and that, in some sense, probably can be dealt with only by
systems based on logic and deduction. We further argue that the
experiments of the late 1960s on problem-solving by theorem-proving
did not show that the use of logic and deduction in AI systems was
necessarily inefficient, but rather that what was needed was better
control of the deduction process, combined with more attention to the
computational properties of axioms.

%A DAVID H. D. WARREN
%T A VIEW OF THE FIFTH GENERATION AND ITS IMPACT
%R Technical Note 265
%I SRI International
%C Menlo Park, California
%D JULY 1982
%X In October 1981, Japan announced a national project to
develop highly innovative computer systems for the 1990s, with the
title Fifth Generation Computer Systems.'' This paper is a personal
view of that project, its significance, and reactions to it.

%A DAVID WILKINS
%T DOMAIN INDEPENDENT PLANNING: REPRESENTATION AND PLAN GENERATION
%R Technical Note 266R
%I SRI International
%C Menlo Park, California
%D May 1983
%X A domain independent planning program that supports both
automatic and interactive generation of hierarchical, partially
ordered plans is described. An improved formalism makes extensive use
of ``constraints'' and ``resources'' to represent domains and
 actions more
powerfully. The formalism also offers efficient methods for
representing properties of objects that do not change over time,
allows specification of the plan rationale (which includes scoping of
conditions and appropriately relating different levels in the
hierarchy), and provides the ability to express deductive rules for
deducing the effects of actions. The implications of allowing
parallel actions in a plan or problem solution are discussed, and new
techniques for efficiently detecting and remedying harmful parallel
interactions are presented. The most important of these techniques,
reasoning about resources, is emphasized and explained. The system
supports concurrent exploration of different branches in the search,
making best-first search easy to implement.

%A MARTIN A. FISCHLER
%A STEPHEN T. BARNARD
%A ROBERT C. BOLLES
%A MICHAEL LOWRY
%A LYNN QUAM
%A GRAHAME SMITH
%A ANDREW WITKIN
%T MODELING AND USING PHYSICAL CONSTRAINTS IN SCENE ANALYSIS
%R Technical Note 267
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1982
%X This paper describes the results obtained in a research
program ultimately concerned with deriving a physical sketch of a
scene from one or more images. Our approach involves modeling
physically meaningful information that can be used to constrain the
interpretation process, as well as modeling the actual scene content.
In particular, we address the problems of modeling the imaging process
(camera and illumination), the scene geometry (edge classification and
surface reconstruction), and elements of scene content (material
composition and skyline delineation).

%A MARK E. STICKEL
%T A NONCLAUSAL CONNECTION-GRAPH RESOLUTION THEOREM-PROVING PROGRAM
%R Technical Note 268
%I SRI International
%C Menlo Park, California
%D OCTOBER 1982
%X A new theorem-proving program, combining the use of
nonclausal resolution and connection graphs, is described. The use of
nonclausal resolution as the inference system eliminates some of the
redundancy and unreadability of clause-based systems. The use of a
connection graph restricts the search space and facilitates graph
searching for efficient deduction.

%A GERALD E. PETERSON
%A MARK E. STICKEL
%T COMPLETE SYSTEMS OF REDUCTIONS USING ASSOCIATIVE AND/OR COMMUTATIVE UNIFICATION
%R Technical Note 269
%I SRI International
%C Menlo Park, California
%D OCTOBER 1982
%X An extension to the Knuth-Bendix algorithm for finding
complete systems of reductions is described. The extension permits
the derivation of complete systems of reductions for theories which
include functions which are associative and/or commutative. A few
examples of the use of the extended Knuth-Bendix algorithm are
presented for theories of groups, rings, lattices, Boolean algebras,
and primitive recursive functions.

%A BARBARA J. GROSZ
%A NORMAN HAAS
%A GARY HENDRIX
%A JERRY HOBBS
%A PAUL MARTIN
%A ROBERT MOORE
%A JANE ROBINSON
%A STANLEY ROSENSCHEIN
%T DIALOGIC: A CORE NATURAL-LANGUAGE PROCESSING SYSTEM
%R Technical Note 270
%I SRI International
%C Menlo Park, California
%D NOVEMBER 9, 1982
%X The DIALOGIC system translates English sentences into
representations of their literal meaning in the context of an
utterance. These representations, or logical forms,'' are intended to
be a purely formal language that is as close as possible to the
structure of natural language, while providing the semantic
compositionality necessary for meaning-dependent computational
processing. The design of DIALOGIC (and of its constituent modules)
was influenced by the goal of using it as the core language-processing
component in a variety of systems, some of which are transportable to
new domains of application.

%A STEPHEN T. BARNARD
%T INTERPRETING PERSPECTIVE IMAGES
%R Technical Note 271
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1982
%X A fundamental problem in computer vision is how to determine
the 3-D spatial orientation of curves and surfaces appearing in an
image. The problem is generally under-constrained, and is complicated
by the fact that metric properties, such as orientation and length,
are not invariant under projection. Under perspective projection (the
correct model for most real images) the transform is nonlinear, and
therefore hard to invert. Two constructive methods are presented.
The first finds the orientation of parallel lines and planes by
locating vanishing points and vanishing lines. The second determines
the orientation of plans by backprojection" of two intrinsic
properties of contours: angle magnitude and curvature.

%A ALEX P. PENTLAND
%T LOCAL SHADING ANALYSIS
%R Technical Note 272
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1982
%X Local analysis of image shading, in the absence of prior
knowledge about the viewed scene, may be used to provide information
about the scene. The following has been proved.
 ``Every'' image point has the same image intensity and first and
 second
derivatives as the image of an umbilical point (a point with equal
principal curvatures) on a Lambertian surface; there is ``exactly one''
combination of surface orientation, curvature, (overhead) illumination
direction and albedo times illumination intensity that will produce a
particular set of image intensity and first and second derivatives. A
solution for the unique combination of surface orientation, etc., at
umbilical points is presented.
 This solution has been extended by using general position and regional
constraints to obtain estimates of the following:
- Surface orientation at each image point
- Whether the surface is planar, singly or doubly curved at each
 point
- The mean illuminant direction within a region
- Whether a region is convex, concave, or is a saddle surface.
 Algorithms to recover illuminant direction, identify discontinuities,
and estimate surface orientation have been evaluated on both natural
and synthesized images, and have been found to produce useful
information about the scene.

%A GRAHAME B. SMITH
%T FROM IMAGE IRRADIANCE TO SURFACE ORIENTATION
%R Technical Note 273
%I SRI International
%C Menlo Park, California
%D DECEMBER 1982
%X The image irradiance equation constrains the relationship
between surface orientation in a scene and the irradiance of its
image. This equation requires detailed knowledge of both the scene
illumination and the reflectance of the surface material. For this
equation to be used to recover surface orientation from image
irradiance, additional constraints are necessary. The constraints
usually employed require that the recovered surface be smooth. We
demonstrate that smoothness is not sufficient for this task.
A new formulation of shape from shading is presented in which surface
orientation is related to image irradiance without requiring detailed
knowledge of the scene illumination, or of the albedo of the surface
material. This formulation, which assumes isotropic scattering,
provides some interesting performance parallels to those exhibited by
the human visual system.

%A FERNANDO PEREIRA
%T LOGIC FOR NATURAL LANGUAGE ANALYSIS
%R Technical Note 275
%I SRI International
%C Menlo Park, California
%D JANUARY 1983
%X This work investigates the use of formal logic as a
practical tool for describing the syntax and semantics of a subset of
English, and building a computer program to answer data base queries
expressed in that subset.
To achieve an intimate connection between logical descriptions and
computer programs, all the descriptions given are in the definite
clause subset of the predicate calculus, which is the basis of the
programming language Prolog. The logical descriptions run directly as
efficient Prolog programs.
Three aspects of the use of logic in natural language analysis are
covered: formal representation of syntactic rules by means of a
grammar formalism based on logic, extraposition grammars; formal
semantics for the chosen English subset, appropriate for data base
queries; informal semantic and pragmatic rules to translate analyzed
sentences into their formal semantics.
On these three aspects, the work improves and extends earlier work by
Colmerauer and others, where the use of computational logic in
language analysis was first introduced.

%A MARTIN A. FISCHLER
%A HELEN C. WOLF
%T A GENERAL APPROACH TO MACHINE PERCEPTION OF LINEAR STRUCTURE IN IMAGED DATA
%R Technical Note 276
%I SRI International
%C Menlo Park, California
%D FEBRUARY 1983
%X In this paper we address a basic problem in machine
perception: the tracing of line-like'' structures appearing in an
image. It is shown that this problem can profitably be viewed as the
process of finding skeletons in a gray scale image after observing
(1) that line detection does not necessarily depend on gradient
information, but rather is approachable from the standpoint of
measuring total intensity variation, and (2) that smoothing the
original image produces an approximate distance transform. An
effective technique for extracting the delineating skeletons from an
image is presented, and examples of this approach using aerial,
industrial, and radiographic imagery are shown.

%A ANDREW J. HANSON
%T THE DARPA/DMA IMAGE UNDERSTANDING TESTBED USER'S MANUAL
%R Technical Note 277
%I SRI International
%C Menlo Park, California
%D JANUARY 1984
%X The primary purpose of the Image Understanding (IU) Testbed
is to provide a means for transferring technology from the
DARPA-sponsored IU research program to DMA and other organizations in
the defense community.
The approach taken to achieve this purpose has two components:
- The establishment of a uniform environment that will be as compatible
 as possible with the environments of research centers at universities
 participating in the IU program. Thus, organizations obtaining copies
 of the Testbed can receive a flow of new results derived from ongoing
 research.
- The acquisition, integration, testing, and evaluation of selected
 scene analysis techniques that represent mature examples of generic
 areas of research activity. These contributions from participants in
 the IU program will allow organizations with Testbed copies to
 immediately begin investigating potential applications of IU
 technology to problems in automated cartography and other areas of
 scene analysis.
The IU Testbed project was carried out under DARPA Contract
No. MDA903-79-C-0588. The views and conclusions contained in this
document are those of the author and should not be interpreted as
necessarily representing the official policies, either expressed or
implied, of the Defense Advanced Research Projects Agency or the
United States government.
This document presents a user's view of the IU Testbed and the
facilities it provides. Many talented people, both at SRI and at each
of the contributing institutions, must be acknowledged for their part
in bringing the Testbed into existence. Special recognition is due to
David Kashtan and Kenneth Laws for their essential contributions to
the environment described here.

%A PETER CHEESEMAN
%T A REPRESENTATION OF TIME FOR PLANNING
%R Technical Note 278
%I SRI International
%C Menlo Park, California
%D FEBRUARY 1983
%X A new time representation is described that allows a
continuously changing world to be represented, so that queries about
the truth of a proposition at an instant or over an interval can be
answered. The deduction mechanism used to answer the common queries
necessary in planning is the same as that employed for deducing all
other information, thereby avoiding the need for a specialized time
expert. The representation allows any time information to be
represented without forcing an over specification. The implementation
of this representation requires mechanisms to detect the effects of
world changes on previous deductions (truth maintenance).

%A ALEX P. PENTLAND
%T FRACTAL-BASED DESCRIPTION OF NATURAL SCENES
%R Technical Note 280
%I SRI International
%C Menlo Park, California
%D FEBRUARY 1984
%X This paper addresses the problems of: (1) representing
natural shapes such as mountains, trees, and clouds, and (2) computing
their description from image data. To solve these problems, we must
be able to relate natural surfaces to their images; this requires a
good model of natural surface shapes. Fractal functions are a good
choice for modeling 3-D natural surfaces because (1) many physical
processes produce a fractal surface shape, (2) fractals are widely
used as a graphics tool for generating natural-looking shapes, and (3)
a survey of natural imagery has shown that the 3-D fractal surface
model, transformed by the image formation process, furnishes an
accurate description of both textured and shaded image regions.
The 3-D fractal model provides a characterization of 3-D surfaces and
their images for which the appropriateness of the model is verifiable.
Furthermore, this characterization is stable over transformations of
scale and linear transforms of intensity.
The 3-D fractal model has been successfully applied to the problems of
(1) texture segmentation and classification, (2) estimation of 3-D
shape information, and (3) distinguishing between perceptually
smooth and perceptually textured surfaces in the scene.

%A STUART M. SHIEBER
%T SENTENCE DISAMBIGUATION BY A SHIFT-REDUCE PARSING TECHNIQUE
%R Technical Note 281
%I SRI International
%C Menlo Park, California
%D MARCH 1983
%X Native speakers of English show definite and consistent
preferences for certain readings of syntactically ambiguous sentences.
A user of a natural-language-processing system would naturally expect
it to reflect the same preferences. Thus, such systems must model in
some way the ``linguistic performance'' as well as the
 ``linguistic
competence'' of the native speaker. We have developed a parsing
algorithm--a variant of the LALR(1) shift-reduce algorithm--that
models the preference behavior of native speakers for a range of
syntactic preference phenomena reported in the psycholinguistic
literature, including the recent data on lexical preferences. The
algorithm yields the preferred parse deterministically, without
building multiple parse trees and choosing among them. As a side
effect, it displays appropriate behavior in processing the much
discussed garden-path sentences. The parsing algorithm has been
implemented and has confirmed the feasibility of our approach to the
modeling of these phenomena.

%A FERNANDO C.N. PEREIRA
%T CAN DRAWING BE LIBERATED FROM THE VON NEUMANN STYLE?
%R Technical Note 282
%I SRI International
%C Menlo Park, California
%D JUNE 1983
%X Current graphics database tools give the user a view of
drawing that is too constrained by the low-level machine operations
used to implement the tools. A new approach to graphics databases is
proposed, based on the description of objects and their relationships
in the restricted form of logic embodied in the programming language
Prolog.

%A STUART M. SHIEBER
%A SUSAN U. STUCKY
%A HANS USZKOREIT
%A JANE J. ROBINSON
%T FORMAL CONSTRAINTS ON METARULES
%R Technical Note 283
%I SRI International
%C Menlo Park, California
%D APRIL 1983
%X Metagrammatical formalisms that combine context-free phrase
structure rules and metarules (MPS grammars) allow concise statement
of generalizations about the syntax of natural languages.
Unconstrained MPS grammars, unfortunately, are not computationally
safe. We evaluate several proposals for constraining them, basing
our assessment on computational tractability and explanatory adequacy.
We show that none of them satisfies both criteria, and suggest new
directions for research on alternative metagrammatical formalisms.

%A ROBERT C. MOORE
%T SEMANTICAL CONSIDERATIONS ON NONMONOTONIC LOGIC
%R Technical Note 284
%I SRI International
%C Menlo Park, California
%D JUNE 1983
%X Commonsense reasoning is nonmonotonic in the sense that
we often draw, on the basis of partial information, conclusions that
we later retract when we are given more complete information. Some of
the most interesting products of recent attempts to formalize
nonmonotonic reasoning are the nonmonotonic logics of McDermott and
Doyle [McDermott and Doyle, 1980; McDermott, 1982]. These logics,
however, all have peculiarities that suggest they do not quite succeed
in capturing the intuitions that prompted their development. In this
paper we reconstruct nonmonotonic logic as a model of an ideally
rational agent's reasoning about his own beliefs. For the resulting
system, called ``autoepistemic logic'', we define an intuitively based
semantics for which we can show autoepistemic logic to be both sound
and complete. We then compare autoepistemic logic with the approach
of McDermott and Doyle, showing how it avoids the peculiarities of
their nonmonotonic logic.

%A HANS USZKOREIT
%T A FRAMEWORK FOR PROCESSING PARTIALLY FREE WORD ORDER
%R Technical Note 285
%I SRI International
%C Menlo Park, California
%D May 1983
%X The partially free word order in
German belongs to the class of phenomena in
natural language that require a close
interaction between syntax and pragmatics. Several competing principles,
 which
are based on syntactic and on discourse information, determine the
linear order of noun phrases. A solution to problems of this sort is
a prerequisite for high-quality language generation. The linguistic
framework of Generalized Phrase Structure Grammar offers tools for
dealing with word order variation. Some slight modifications to the
framework allow for an analysis of the German data that incorporates
just the right degree of interaction between syntactic and pragmatic
components and that can account for conflicting ordering statements.

%A MARK E. STICKEL
%T THEORY RESOLUTION: BUILDING IN NONEQUATIONAL THEORIES
%R Technical Note 286
%I SRI International
%C Menlo Park, California
%D May 1983
%X Theory resolution constitutes a set of complete procedures
for building nonequational theories into a resolution theorem-proving
program so that axioms of the theory need never be resolved upon.
Total theory resolution uses a decision procedure that is capable of
determining inconsistency of any set of clauses using predicates in
the theory. Partial theory resolution employs a weaker decision
procedure that can determine potential inconsistency of a pair of
literals. Applications include the building in of both mathematical
and special decision procedures, such as for the taxonomic information
furnished by a knowledge representation system.

%A GRAHAME B. SMITH
%T SHAPE FROM SHADING: AN ASSESSMENT
%R Technical Note 287
%I SRI International
%C Menlo Park, California
%D May 1983
%X We review previous efforts to recover surface shape from
image irradiance in order to assess what can and cannot be
accomplished. We consider the informational requirements and
restrictions of these approaches. In dealing with the question of
what surface parameters can be recovered locally from image shading,
we show that, at most, shading determines relative surface curvature,
i.e., the ratio of surface curvature measured in orthogonal image
directions. The relationship between relative surface curvature and
the second derivatives of image irradiance is independent of other
scene parameters, but insufficient to determine surface shape. This
result places in perspective the difficulty encountered in previous
attempts to recover surface orientation from image shading.

%A KENNETH I. LAWS
%T THE GHOUGH GENERALIZED HOUGH TRANSFORM PACKAGE: DESCRIPTION AND EVALUATION
%R Technical Note 288
%I SRI International
%C Menlo Park, California
%D DECEMBER 1982
%X GHOUGH is a computer program for detecting instances of a
given shape within an image. It may be used for cueing, counting, or
mensuration. GHOUGH can find instances that are displaced, rescaled,
rotated, or incomplete relative to the shape template. They are
detected by computing a generalized Hough transform of the image
edge elements. Each edge element votes for all those instances of the
shape that could contain it; the votes are tallied and the best
supported instances are reported as likely matches.
GHOUGH was contributed to the DARPA Image Understanding Testbed at SRI
by the University of Rochester. This report summarizes applications
for which GHOUGH is suited, the history and nature of the algorithm,
details of the Testbed implementation, the manner in which GHOUGH is
invoked and controlled, the types of results that can be expected, and
suggestions for further development. The scientific contributions of
this technical note are the analysis of GHOUGH's parameter settings
and performance characteristics.

%A KENNETH I. LAWS
%T THE PHOENIX IMAGE SEGMENTATION SYSTEM: DESCRIPTION AND EVALUATION
%R Technical Note 289
%I SRI International
%C Menlo Park, California
%D DECEMBER 1982
%X PHOENIX is a computer program for segmenting images into
homogeneous closed regions. It uses histogram analysis, thresholding,
and connected-components analysis to produce a partial segmentation,
then resegments each region until various stopping criteria are
satisfied. Its major contributions over other recursive segmenters
are a sophisticated control interface, optional use of more than one
histogram-dependent intensity threshold during tentative segmentation
of each region, and spatial analysis of resulting subregions as a form
of look-ahead for choosing between promising spectral features at
each step.
PHOENIX was contributed to the DARPA Image Understanding Testbed at
SRI by Carnegie-Mellon University. This report summarizes
applications for which PHOENIX is suited, the history and nature of
the algorithm, details of the Testbed implementation, the manner in
which PHOENIX is invoked and controlled, the type of results that can
be expected, and suggestions for further development. Baseline
parameter sets are given for producing reasonable segmentations of
typical imagery.

%A DAVID H.D. WARREN
%T APPLIED LOGIC--ITS USE AND IMPLEMENTATION AS A PROGRAMMING TOOL
%R Technical Note 290
%I SRI International
%C Menlo Park, California
%D JUNE 1983
%X The first part of the thesis explains from first principles
the concept of logic programming and its practical application in
the programming language Prolog. Prolog is a simple but powerful
language which encourages rapid, error-free programming and clear,
readable, concise programs. The basic computational mechanism is a
pattern matching process (unification) operating on general record
structures (terms of logic).
The ideas are illustrated by describing in detail one sizable Prolog
program which implements a simple compiler. The advantages and
practicability of using Prolog for real compiler implementation are
discussed.
The second part of the thesis describes techniques for implementing
Prolog efficiently. In particular, it is shown how to compile the
patterns involved in the matching process into instructions of a
low-level language. This ideas has actually been implemented in a
compiler (written in Prolog) from Prolog to DECsystem-10 assembly
language. However, the principles involved are explained more
abstractly in terms of a Prolog Machine. The code generated is
comparable in speed with that produced by existing DEC10 Lisp
compilers. Comparison is possible since pure Lisp can be viewed as a
(rather restricted) subset of Prolog.
It is argued that structured data objects, such as lists and trees,
can be manipulated by pattern matching using a structure sharing
representation as efficiently as by conventional selector and
constructor functions operating on linked records in heap storage.
Moreover, the pattern matching formulation actually helps the
implementor to produce a better implementation.

%A STUART M. SHIEBER
%T DIRECT PARSING OF ID/LP GRAMMARS
%R Technical Note 291
%I SRI International
%C Menlo Park, California
%D AUGUST 1983
%X The Immediate Dominance/Linear Precedence (ID/LP) formalism
is a recent extension of Generalized Phrase Structure Grammar (GPSG)
designed to perform some of the tasks previously assigned to
metarules--for example, modeling the word-order characteristics of
so-called free-word-order languages. It allows a simple specification
of classes of rules that differ only in constituent order. ID/LP
grammars (as well as metarule grammars) have been proposed for use in
parsing by expanding them into an equivalent context-free grammar. We
develop a parsing algorithm, based on the algorithm of Earley, for
parsing ID/LP grammars directly, circumventing the initial expansion
phase. A proof of correctness of the algorithm is supplied. We also
discuss some aspects of the time complexity of the algorithm and some
formal properties associated with ID/LP grammars and their
relationship to context-free grammars.

%A BARBARA J. GROSZ
%A et\ al.
%T PROVIDING A UNIFIED ACCOUNT OF DEFINITE NOUN PHRASES IN DISCOURSE
%R Technical Note 292
%I SRI International
%C Menlo Park, California
%D JUNE 1983
%X Linguistic theories typically assign various linguistic
phenomena to one of the categories, ``syntactic'', ``semantic'', or
``pragmatic'', as if the phenomena in each category were relatively
independent of those in the others. However, various phenomena in
discourse do not seem to yield comfortably to any account that is
strictly a syntactic or semantic or pragmatic one. This paper focuses
on particular phenomena of this sort--the use of various referring
expressions such as definite noun phrases and pronouns--and examines
their interaction with mechanisms used to maintain discourse
coherence.
Even a casual survey of the literature on definite descriptions and
referring expressions reveals not only defects in the individual
accounts provided by theorists (from several different disciplines),
but also deep confusions about the roles that syntactic, semantic, and
pragmatic factors play in accounting for these phenomena. The
research we have undertaken is an attempt to sort out some of these
confusions and to create the basis for a theoretical framework that
can account for a variety of discourse phenomena in which all three
factors of language use interact. The major premise on which our
research depends is that the concepts necessary for an adequate
understanding of the phenomena in question are not exclusively either
syntactic or semantic or pragmatic.
The next section of this paper defines two levels of discourse
coherence and describes their roles in accounting for the use of
singular definite noun phrases. To illustrate the integration of
factors in explaining the uses of referring expressions, their use on
one of these levels, i.e., the local one, is discussed in Sections 3
and 4. This account requires introducing the notion of the centers of
a sentence in a discourse, a notion that cannot be defined in terms of
factors that are exclusively syntactic or semantic or pragmatic. In
Section 5, the interactions of the two levels with these factors and
their effects on the uses of referring expressions in discourse are

%A PAUL MARTIN, DOUGLAS APPELT,
%A FERNANDO PEREIRA
%T TRANSPORTABILITY AND GENERALITY IN A NATURAL-LANGUAGE INTERFACE SYSTEM
%R Technical Note 293
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1983
%X This paper describes the design of a transportable natural
language (NL) interface to databases and the constraints that
transportability places on each components of such a system. By a
``transportable'' NL system, we mean an NL processing system that is
constructed so that a domain expert (rather than an AI or linguistics
expert) can move the system to a new application domain. After
discussing the general problems presented by transportability, this
paper describes ``TEAM'' (an acronym for ``T''ransportable
 ``E''nglish database
``A''ccess ``M''edium), a demonstratable prototype of such a
 system. The
discussion of TEAM shows how domain-independent and domain-dependent
information can be separated in the different components of an NL
interface system, and presents one method of obtaining domain-specific
information from a domain expert.

%A KURT KONOLIGE
%T A DEDUCTIVE MODEL OF BELIEF
%R Technical Note 294
%I SRI International
%C Menlo Park, California
%D JUNE 1983
%X Representing and reasoning about the knowledge an agent
(human or computer) must have to accomplish some task is becoming an
increasingly important issue in artificial intelligence (AI) research.
To reason about an agent's beliefs, an AI system must assume some
formal model of those beliefs. An attractive candidate is the
``Deductive'' ``Belief'' ``model'': an agent's beliefs
 are described as a set of
sentences in some formal language (the ``base''
 ``sentences''), together
with a deductive process for deriving consequences of those beliefs.
In particular, a Deductive Belief model can account for the effect of
resource limitations on deriving consequences of the base set: an
agent need not believe all the logical consequences of his beliefs.
In this paper we develop a belief model based on the notion of
deduction, and contrast it with current AI formalisms for belief
derived from Hintikka/Kripke possible-worlds semantics for knowledge.

%A FERNANDO C.N. PEREIRA
%A DAVID H.D. WARREN
%T PARSING AS DEDUCTION
%R Technical Note 295
%I SRI International
%C Menlo Park, California
%D JUNE 1983
%X By exploring the relationship between parsing and deduction,
a new and more general view of chart parsing is obtained, which
encompasses parsing for grammar formalisms based on unification, and
is the basis of the Earley Deduction proof procedure for definite
clauses. The efficiency of this approach for an interesting class of
grammars is discussed.

%A FERNANDO C.N. PEREIRA
%T A NEW CHARACTERIZATION OF ATTACHMENT PREFERENCES
%R Technical Note 296
%I SRI International
%C Menlo Park, California
%D MARCH 1983
%X Several authors have tried to model attachment preferences
for structurally ambiguous sentences, which cannot be disambiguated
from semantic information. These models lack rigor and have been
widely criticized. By starting from a precise choice of parsing
model, it is possible to give a simple and rigorous description of
Minimal Attachment and Right Association that avoids some of the
problems of other models.

%A DOUGLAS E. APPELT
%T TELEGRAM: A GRAMMAR FORMALISM FOR LANGUAGE PLANNING
%R Technical Note 297
%I SRI International
%C Menlo Park, California
%D JUNE 1983
%X Planning provides the basis for a theory of language
generation that considers the communicative goals of the speaker when
producing utterances. One central problem in designing a system based
on such a theory is specifying the requisite linguistic knowledge in a
form that interfaces well with a planning system and allows for the
encoding of discourse information. The TELEGRAM (TELEological
GRAMmar) system described in this paper solves this problem by
annotating a unification grammar with assertions about how grammatical
choices are used to achieve various goals, and by enabling the planner
to augment the functional description of an utterance as it is being
unified. The control structures of the planner and the grammar
unifier are then merged in a manner that makes it possible for general
planning to be guided by unification of a particular functional
description.

%A KENNETH I. LAWS
%T THE DARPA/DMA IMAGE UNDERSTANDING TESTBED PROGRAMMER'S MANUAL
%R Technical Note 298
%I SRI International
%C Menlo Park, California
%D JANUARY 1984
%X The primary purpose of the Image Understanding (IU) Testbed
is to provide a means for transferring technology from the
DARPA-sponsored IU research program to DMA and other organizations in
the defense community.
The approach taken to achieve this purpose has two components:
- The establishment of a uniform environment that will be as compatible
 as possible with the environments of research centers at universities
 participating in the IU program. Thus, organizations obtaining copies
 of the Testbed can receive a flow of new results derived from ongoing
 research.
- The acquisition, integration, testing, and evaluation of selected
 scene analysis techniques that represent mature examples of generic
 areas of research activity. These contributions from participants in
 the IU program will allow organizations with Testbed copies to
 immediately begin investigating potential applications of IU
 technology to problems in automated cartography and other areas of
 scene analysis.
 The IU Testbed project was carried out under DARPA Contract No.
MDA903-79-C-0588. The views and conclusions contained in this
document are those of the author and should not be interpreted as
necessarily representing the official policies, either expressed or
implied, of the Defense Advanced Research Projects Agency or the
United States government.
This report provides UNIX-style programmer's reference documentation
for IU Testbed software modules that are based on the UNIX system
environment.

%A ANDREW J. HANSON
%T THE DARPA/DMA IMAGE UNDERSTANDING TESTBED SYSTEM MANAGER'S MANUAL
%R Technical Note 299
%I SRI International
%C Menlo Park, California
%D JANUARY 1984
%X The primary purpose of the Image Understanding (IU) Testbed
is to provide a means for transferring technology from the
DARPA-sponsored IU research program to DMA and other organizations in
the defense community.
The approach taken to achieve this purpose has two components:
- The establishment of a uniform environment that will be as compatible
 as possible with the environments of research centers at universities
 participating in the IU program. Thus, organizations obtaining copies
 of the Testbed can receive a flow of new results derived from ongoing
 research.
- The acquisition, integration, testing, and evaluation of selected
 scene analysis techniques that represent mature examples of generic
 areas of research activity. These contributions from participants in
 the IU program will allow organizations with Testbed copies to
 immediately begin investigating potential applications of IU
 technology to problems in automated cartography and other areas of
 scene analysis.
 The IU Testbed project was carried out under DARPA Contract
No. MDA903-79-C-0588. The views and conclusions contained in this
document are those of the author and should not be interpreted as
necessarily representing the official policies, either expressed or
implied, of the Defense Advanced Research Projects Agency or the
United States government.
This manual contains a selection of information and procedures needed
by system managers responsible for the maintenance of the IU Testbed
software system.

%A DAVID H.D. WARREN
%T AN ABSTRACT PROLOG INSTRUCTION SET
%R Technical Note 309
%I SRI International
%C Menlo Park, California
%D OCTOBER 1983
%X This report describes an abstract Prolog instruction set
suitable for software, firmware, or hardware implementation. The
instruction set is abstract in that certain details of its encoding
and implementation are left open, so that it may be realized in a
number of different forms. The forms that are contemplated are:
- Translation into a compact bytecode, with emulators written in
 C (for maximum portability), Progol (a macrolanguage generating
 machine code, for efficient software implementations as an
 alternative to direct compilation on machines such as the
 VAX), and VAX-730 microcode.
- Compilation into the standard instructions of machines such as
 the VAX or DECsystem-10/20.
- Hardware (or firmware) emulation of the instruction set on a
 specially designed Prolog processor.
The abstract machine described herein (new Prolog Engine) is a major
revision of the old Prolog Engine described in a previous document.
The new model overcomes certain difficulties in the old model, which
are discussed in a later section. The new model can be considered to
be a modification of the old model, where the stack contains compiler-
defined goals called environments instead of user-defined goals. The
environments correspond to some number of goals forming the tail of a
clause. The old model was developed having primarily in mind a
VAX-730 microcode implementation. The new model has, in addition,
been influenced by hardware implementation considerations, but should
remain equally amenable to software or firmware implementation on
machines such as the VAX.

%A ANDREW J. HANSON
%T OVERVIEW OF THE IMAGE UNDERSTANDING TESTBED
%R Technical Note 310
%I SRI International
%C Menlo Park, California
%D OCTOBER 1983
%X The Image Understanding Testbed is a system of hardware and
software that is designed to facilitate the integration, testing, and
evaluation of implemented research concepts in machine vision. The
system was developed by the Artificial Intelligence Center of SRI
International under the joint sponsorship of the Defense Advanced
Research Projects Agency (DARPA) and the Defense Mapping Agency (DMA).
The primary purpose of the Image Understanding (IU) Testbed is to
provide a means for transferring technology from the DARPA-sponsored
IU research program to DMA and other organizations in the defense
community.
The approach taken to achieve this purpose has two components:
- The establishment of a uniform environment that will be as
 compatible as possible with the environments of research centers at
 universities participating in the IU program. Thus, organizations
 obtaining copies of the testbed can receive new results of ongoing
 research as they become available.
- The acquisition, integration, testing, and evaluation of
 selected scene analysis techniques that represent mature examples of
 generic areas of research activity. These contributions from IU
 program participants will allow organizations with testbed copies to
 immediately begin investigating potential applications of IU
 technology to problems in automated cartography and other areas of
 scene analysis.
An important component of the DARPA IU research program is the
development of image-understanding techniques that could be applied to
automated cartography and military image interpretation tasks; this
work forms the principal focus of the testbed project. A number of
computer modules developed by participants in the IU program have been
transported to the uniform testbed environment as a first step in the
technology transfer process. These include systems written in UNIX C,
MAINSAIL, and FRANZ LISP. Capabilities of the computer programs
include segmentation, linear feature delineation, shape detection,
stereo reconstruction, and rule-based recognition of classes of
three-dimensional objects.

%A DOUGLAS APPELT
%T PLANNING ENGLISH REFERRING EXPRESSIONS
%R Technical Note 312
%I SRI International
%C Menlo Park, California
%D OCTOBER 1983
%X This paper describes a theory of language generation based
on planning. To illustrate the theory, the problem of planning
referring expressions is examined in detail. A theory based on
planning makes it possible for one to account for noun phrases that
refer, that inform the hearer of additional information, and that are
coordinated with the speaker's physical actions to clarify his
communicative intent. The theory is embodied in a computer system
called KAMP, which plans both physical and linguistic actions, given
a high-level description of the speaker's goals.

%A MICHAEL GEORGEFF
%T COMMUNICATION AND INTERACTION IN MULTI-AGENT PLANNING
%R Technical Note 313
%I SRI International
%C Menlo Park, California
%D DECEMBER 9, 1983
%X A method for synthesizing multi-agent plans from simpler
single-agent plans is described. The idea is to insert communication
acts into the single-agent plans so that agents can synchronize
activities and avoid harmful interactions. Unlike most previous
planning systems, actions are represented by ``sequences'' of states,
rather than as simple state change operators. This allows the
expression of more complex kinds of interaction than would otherwise
be possible. An efficient method of interaction and safety analysis
is then developed and used to identify critical regions in the plans.
An essential feature of the method is that the analysis is performed
without generating all possible interleavings of the plans, thus
avoiding a combinatorial explosion. Finally, communication primitives
are inserted into the plans and a supervisor process created to handle
synchronization.

%A MICHAEL GEORGEFF
%A UMBERTO BONOLLO (MONASH U., AUSTRALIA)
%T PROCEDURAL EXPERT SYSTEMS
%R Technical Note 314
%I SRI International
%C Menlo Park, California
%D DECEMBER 9, 1983
%X A scheme for explicitly representing and using expert
knowledge of a procedural kind is described. The scheme allows the
``explicit'' representation of both declarative and procedural knowledge
within a unified framework, yet retains all the desirable properties
of expert systems such as modularity, explanatory capability, and
extendability. It thus bridges the gap between the procedural and
declarative languages, and allows formal algorithmic knowledge to be
uniformly integrated with heuristic declarative knowledge. A version
of the scheme has been fully implemented and applied to the domain of
automobile engine fault diagnosis.

%A STEPHEN T. BARNARD
%T CHOOSING A BASIS FOR PERCEPTUAL SPACE
%R Technical Note 315
%I SRI International
%C Menlo Park, California
%D JANUARY 3, 1984
%X If it is possible to interpret an image as a projection of
rectangular forms, there is a strong tendency for people to do so. In
effect, a mathematical basis for a vector space appropriate to the
world, rather than to the image, is selected. A computational
solution to this problem is presented. It works by backprojecting
image features into three-dimensional space, thereby generating
(potentially) all possible interpretations, and by selecting those
which are maximally orthogonal. In general, two solutions that
correspond to perceptual reversals are found. The problem of choosing
one of these is related to the knowledge of verticality. A measure of
consistency of image features with a hypothetical solution is defined.
In conclusion, the model supports an information-theoretic
interpretation of the Gestalt view of perception.

%A MARTHA E. POLLACK
%T GENERATING EXPERT ANSWERS THROUGH GOAL INFERENCE
%R Technical Note 316
%I SRI International
%C Menlo Park, California
%D OCTOBER 1983
%X Automated expert systems have adopted a restricted view in
which the advice-seeker is assumed always to know what advice he
needs, and always to express in his query an accurate, literal request
for that advice. In fact, people often need to consult with an expert
precisely because they don't know what it is they need to know. It is
a significant feature of human expertise to be able to deduce, from an
incomplete or inappropriate query, what advice is actually needed.
This paper develops a framework for enabling automated experts to
perform similar deductions, and thereby generate appropriate answers
to queries made to them.

%A NILS J. NILSSON
%T THE SRI ARTIFICIAL INTELLIGENCE CENTER--A BRIEF HISTORY
%R Technical Note 317
%I SRI International
%C Menlo Park, California
%D JANUARY 24, 1984
%X Charles A. Rosen came to SRI in 1957. I arrived in 1961.
Between these dates, Charlie organized an Applied Physics Laboratory
and became interested in learning machines and self-organizing
systems. That interest launched a group that ultimately grew into a
major world center of artificial intelligence research--a center that
has endured twenty-five years of boom and bust in fashion, has
graduated over a hundred AI research professionals, and has
generated ideas and programs resulting in new products and companies
as well as scientific articles, books, and this particular collection
itself.
The SRI Artificial Intelligence Center has always been an extremely
cohesive group, even though it is associated with many contrasting
themes. Perhaps these very contrasts are responsible for its
vitality. It is a group of professional researchers, but visiting
Ph.D. candidates (mainly from Stanford University) have figured
prominently in its intellectual achievements. It is not part of a
university, yet its approach to AI has often been more academic and
basic than those used in some of the prominent university
laboratories. For many years a vocal group among its professionals
has strongly emphasized the role of logic and the centrality of
reasoning and declarative representation in AI, but it is also home to
many researchers who pursue other aspects of the discipline. Far more
people have left it (to pursue careers in industry) than are now part
of it, yet it is still about as large as it has ever been and retains
a more or less consistent character. It is an American research
group, supported largely by the Defense Department, but, from the
beginning, it has been a melting pot of nationalities.

%A THOMAS D. GARVEY
%A JOHN D. LOWRANCE
%T AN AI APPROACH TO INFORMATION FUSION
%R Technical Note 318
%I SRI International
%C Menlo Park, California
%D DECEMBER 1983
%X This paper discusses the use of selected artificial
intelligence (AI) techniques for integrating multisource information
in order to develop an understanding of an ongoing situation. The
approach takes an active, top-down view of the task, projecting a
situation description forward in time, determining gaps in the current
model, and tasking sensors to acquire data to fill the gaps.
Information derived from tasked sensors and other sources is combined
using new, non-Bayesian inference techniques.
This active approach seems critical to solve the problems posed by the
low emission signatures anticipated for near-future threats. Simula-
tion experiments lead to the conclusion that the utility of ESM system
operation in future conflicts will depend on how effectively onboard
sensing resources are managed by the system.
The view of AI that will underly the discussion is that of a tech
nology attempting to extend automation capabilities from the current
replace the human's hands approach to that of replacing or
augmenting the human's cognitive and perceptual capabilities.
Technology transfer issues discussed in the presentation are the
primary motivation for highlighting this view. The paper will
conclude with a discussion of unresolved problems associated with the
introduction of AI technology into real world military systems.

%A KURT KONOLIGE
%T BELIEF AND INCOMPLETENESS
%R Technical Note 319
%I SRI International
%C Menlo Park, California
%D JANUARY 11, 1984
%X Two artificially intelligent (AI) computer agents begin to
play a game of chess, and the following conversation ensues:
- S1: Do you know the rules of chess?
- S2: Yes.
- S1: Then you know whether White has a forced initial win
 or not.
- S2: Upon reflection, I realize that I must.
- S1: Then there is no reason to play.
- S2: No.
Both agents are state-of-the-art constructions, incorporating the
latest AI research in chess playing, natural-language understanding,
planning, etc. But because of the overwhelming combinatorics of
chess, neither they nor the fastest foreseeable computers would be
able to search the entire game tree to find out whether White has a
forced win. Why then do they come to such an odd conclusion about
their own knowledge of the game?
The chess scenario is an anecdotal example of the way inaccurate
cognitive models can lead to behavior that is less than intelligent in
artificial agents. In this case, the agents' model of belief is not
correct. They make the assumption that an agent actually knows all
the consequences of his beliefs. S1 knows that chess is a finite
game, and thus reasons that, in principle, knowing the rules of chess
is all that is required to figure out whether White has a forced
initial win. After learning that S2 does indeed know the rules of
chess, he comes to the erroneous conclusion that S2 also knows this
particular consequence of the rules. And S2 himself, reflecting on
his own knowledge in the same manner, arrives at the same conclusion,
even though in actual fact he could never carry out the computations
necessary to demonstrate it.

%A ROBERT C. MOORE
%T A FORMAL THEORY OF KNOWLEDGE AND ACTION
%R Technical Note 320
%I SRI International
%C Menlo Park, California
%D FEBRUARY 1984
%X Most work on planning and problem solving within the field
of artificial intelligence assumes that the agent has complete
knowledge of all relevant aspects of the problem domain and problem
situation. In the real world, however, planning and acting must
frequently be performed without complete knowledge. This imposes two
additional burdens on an intelligent agent trying to act effectively.
First, when the agent entertains a plan for achieving some goal, he
must consider not only whether the physical prerequisites of the plan
have been satisfied, but also whether he has all the information
necessary to carry out the plan. Second, he must be able to reason
about what he can do to obtain necessary information that he lacks.
In this paper, we present a theory of action in which these problems
are taken into account, showing how to formalize both the knowledge
prerequisites of action and the effects of action on knowledge.

%A NILS J. NILSSON
%T PROBABILISTIC LOGIC
%R Technical Note 321
%I SRI International
%C Menlo Park, California
%D FEBRUARY 6, 1984
%X Because many artificial intelligence applications require
the ability to deal with uncertain knowledge, it is important to seek
appropriate generalizations of logic for that case. We present here a
semantical generalization of logic in which the truth-values of
sentences are probability values (between 0 and 1). Our generaliza-
tion applies to any logical system for which the consistency of a
finite set of sentences can be established. (Although we cannot
always establish the consistency of a finite set of sentences of
first-order logic, our method is usable in those cases in which we
can.) The method described in the present paper combines logic with
probability theory in such a way that probabilistic logical entailment
reduces to ordinary logical entailment when the probabilities of all
sentences are either 0 or 1.

%A ROBERT C. MOORE
%T POSSBLE-WORLD SEMANTICS FOR AUTOEPISTEMIC LOGIC
%R Technical Note 337
%I SRI International
%C Menlo Park, California
%D AUGUST 1984
%X In a previous paper [Moore, 1983a, 1983b], we presented a
nonmonotonic logic for modeling the beliefs of ideally rational agents
who reflect on their own beliefs, which we call autoepistemic
logic.
We define a simple and intuitive sematics for autoepistemic logic and
proved the logic sound and complete with respect to that semantics.
However, the nonconstructive character of both the logic and its
semantics made it difficult to prove the existence of sets of beliefs
satisfying all the constraints of autoepistemic logic. This note
presents an alternative, possible-world semantics for autoepistemic
logic that enables us to construct finite models for autoepistemic
theories, as well as to demonstrate the existence of sound and
complete autoepistemic theories based on given sets of premises.

%A MARTIN A. FISCHLER
%A OSCAR FIRSCHEIN
%T PARALLEL GUESSING: A STRATEGY FOR HIGH-SPEED COMPUTATION
%R Technical Note 338
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 19, 1984
%X Attempts have been made to speed up image-understanding
computation involving conventional serial algorithms by decomposing
these algorithms into portions that can be computed in parallel.
Because many classes of algorithms do not readily decompose, one seeks
some other basis for parallelism (i.e, for using additional hardware
to obtain higher processing speed). In this paper we argue that
parallel guessing for image analysis is a useful approach, and that
several recent IU algorithms are based on this concept. Problems
suitable for this approach have the characteristic that either
distance from a true solution, or the correctness of a guess, can be
readily checked. We review image-analysis algorithms having a
parallel guessing or randomness flavor.
We envision a parallel set of computers, each of which carries out a
computation on a data set using some random or guessing process, and
communicate the goodness of its results to its co-workers through a
blackboard mechanisms.

%A MICHAEL P. GEORGEFF
%A STEPHEN F. BODNAR
%T A SIMPLE AND EFFICIENT IMPLEMENTATION OF HIGHER-ORDER FUNCTIONS IN LISP
%R Technical Note 339
%I SRI International
%C Menlo Park, California
%D DECEMBER 1984
%X A relatively simple method for handling higher-order
functions (funargs) in LISP is described. It is also shown how this
scheme allows extension of the LISP language to include partial
application of functions.
The basis of the approach is to defer evaluation of function-valued
expressions until sufficient arguments have been accumulated to reduce
the expression to a nonfunctional value. This results in stacklike
environment structures rather than the treelike structures produced by
standard evaluation schemes. Consequently, the evaluator can be
implemented on a standard runtime stack without requiring the complex
storage management schemes usually employed for handling higher-order
functions.
A full version of LISP has been implemented by modifying the FRANZ
LISP interpreter to incorporate the new scheme. These modificaions
prove to be both simple and efficient.

%A MARK E. STICKEL
%T AUTOMATED DEDUCTION BY THEORY RESOLUTION
%R Technical Note 340
%I SRI International
%C Menlo Park, California
%D OCTOBER 1984
%X Theory resolution constitutes a set of complete procedures
for incorporating theories into a resolution theorem-proving program,
thereby making it unnecessary to resolve directly upon axioms of the
theory. This can grealy reduce the length of proofs and the size o
the search space. Theory resolution effects a beneficial division of
labor, improving the performance of the theorem prover and increasing
the applicability of the specialized reasoning procedures. Total
theory resolution utilizes a decision procedure that is capable of
determining unsatisfiability of any set of clauses using predicates in
the theory. Partial theory resolution employes a weaker decision
procedure that can determine potential unsatisfiability of sets of
literals. Applications include the building in of both mathematical
and special decision procedures, e.g., for the taxonomic information
furnished by a knowledge representation system. Theory resolution is
a generalization of numerous previously known resolution refinements.
Its power is demonstrated by comparing solutions of Schubert's
Steamroller challenge problem with or without building in axioms
through theory resolution.

%A MARSHA JO HANNAH
%T DESCRIPTION OF SRI'S BASELINE STEREO SYSTEM
%R Technical Note 342
%I SRI International
%C Menlo Park, California
%D OCTOBER 1984
%X We are implementing a baseline system for automated area-
based stereo compilation. This system, STSYS, operates in several
passes over the data, during which it iteratively builds, checks, and
refines its model of the 3-dimensional world, as represented by a pair
of images. In this papers, we describe the components of STSYS and
give examples of the results it produces. We find that these results
agree reasonably well with those produced on the interactive DIMP
system at ETL, the best available benchmark.

%A LORNA SHINKLE
%T TEAM USER'S GUIDE
%R Technical Note 343
%I SRI International
%C Menlo Park, California
%D OCTOBER 1984
%X TEAM (Transportable English data Access Medium) is a
transportable natural-language (NL) interface to a database. It is a
tool of considerable power that enables the user to retrieve data and
elicit answers to queries by asking questions and giving commands in
English instead of a formal query language. Moreover, TEAM is not
limited to any particular database, but can be adapted to demonstrate
natural-language retrieval in a broad variety of application domains.
The prototype TEAM software described herein was developed by the
Artificial Intelligence Center of SRI International to demonstrate the
system's capabilities and adaptive potential.
This user's guide is designed to assist new TEAM users to learn about
the concepts and tasks involved in retrieving data and in preparing a
demonstration for a new application area. An effort has been made to
illustrate some of the problems TEAM must solve in translating an
English question into a database query. However, the necessarily
limited scope of this guide cannot include a discussion of all the
natural-language-processing issues addressed by the system; our
emphasis is on a practical, rather than theoretical, understanding of
the concepts. Similarly, while this guide cannot cover every detail
of creating a new demonstration for TEAM, it does provide a thorough
introduction to the procedure to be followed and explains how to use
the on-line help provided by the system.
This introductory manual is designed to be read in conjunction with
actual use of the system. While a casual perusal of this document may
acquaint the reader with some of TEAM's features, using the examples
and suggestions as a practical guide to actually experimenting with
the system will prove a much more effective method of learning how to
use TEAM and becoming familiar with both its capabilities and its
limitations. Much of this guide consists of comments, descriptions,
and other background information, but the user is frequently
instructed to perform some action as a learning experience. In the
examples shown in the text, the portions printed in boldface are typed
as selected by the user; these portions may or may not appear in
boldface on the screen when TEAM is used. In the examples illustrated
by figures, however, the type faces do correspond exactly to the
screen display.

%A WILLIAM CROFT
%T THE REPRESENTATION OF ADVERBS, ADJECTIVES AND EVENTS IN LOGICAL FORM
%R Technical Note 344
%I SRI International
%C Menlo Park, California
%D DECEMBER 1984
%X The representation of adjectives and their adverbial
counterparts in logical form rises a number of issues in the relation
of (morpho)syntax to semantics, as well as more specific problems of
lexical and grammatical analysis. This paper addresses those issues
which have bearing on the relation of properties to events. It is
argued that attributes and context play only an indirect role in the
relation between properties and events. The body of the paper
addresses the criteria for relating surface forms to logical form
representations, and offers a unified analysis of adjectives and their
adverbial conterparts in logical form while maintaining a clear
distinction between operators and predicates; this requires the
postulation of a factive sentential operator and the relaxation of the
one-to-one syntax-semantics corespondence hypothesis. Criteria for
determining the number of arguments for a predicate are established
and are used for the analyses of phenomena such as passive-
sensitivity, lexical derivational patterns, and gradability.

%A C. RAYMOND PERRAULT
%T ON THE MATHEMATICAL PROPERTIES OF LINGUISTIC THEORIES
%R Technical Note 345
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1984
%X Metatheoretical findings regarding the decidability,
generative capacity, and recognition complexity of several syntatic
theories are surveyed. These include context-free, transformational,
lexical-functional, generalized phrase structure, tree adjunct, and
stratificational grammars. The paper concludes with a discussion of
the implications of these results with respect to linguistic theory.

%A DAVID E. WILKINS
%T RECOVERING FROM EXECUTION ERRORS IN SIPE
%R Technical Note 346
%I SRI International
%C Menlo Park, California
%D JANUARY 1985
%X In real-world domains (e.g., a mobile robot environment),
things do not always proceed as planned, so it is important to develop
better execution-monitoring techniques and replanning capabilities.
This paper describes these capabilities in the SIPE planning system.
The motivation behind SIPE is to place enough limitations on the
representation so that planning can be done efficiently, while retain-
ing sufficient power to still be useful. This work assumes that new
information given to the execution monitor is in the form of
predicates, thus avoiding the difficult problem of how to generate
these predicates from information provided by sensors.
The replanning module presented here takes advantage of the rich
structure of SIPE plans and is intimately connected with the planner,
which can be called as a subroutine. This allows the use of SIPE's
capabilities to determine efficiently how unexpected events affect the
plan being executed and, in many cases, to retain most of the original
plan by making changes in it to avoid problems caused by these
unexpected events. SIPE is also capable of shortening the original
plan when serendipitous events occur. A general set of replanning
actions is presented along with a general replanning capability that
has been implemented by using these actions.

%A NILS J. NILSSON
%T TRIANGLE TABLES: A PROPOSAL FOR A ROBOT PROGRAMMING LANGUAGE
%R Technical Note 347
%I SRI International
%C Menlo Park, California
%D FEBRUARY 1985
%X Structures called ``triangle tables'' were used in connection
with the SRI robot ``Shakey'' for storing sequences of robot actions.
Because the rationale for triangle tables still seems relevant, I have
recently elaborated the original concept and have begun to consider
how the expanded formalism could be used as a general robot-
programming language. The present article describes this new view of
triangle tables and how they might be used in a language that supports
asynchronous ad concurrent action computations.

%A ROBERT C. MOORE
%T A COGNITIVIST REPLY TO BEHAVIORISM
%R Technical Note 348
%I SRI International
%C Menlo Park, California
%D MARCH 1985
%X The objections to mentalistic psychology raised by Skinner
in Behaviorism at Fifty [Skinner, 1984] are reviewed, and it is
argued that a cognitivist perspective offers a way of constructing
mentalistic theories tha overcome these objections.

%A CHRISTOPHER STUART
%T SYNCHRONIZATION OF MULTIAGENT PLANS USING A TEMPORAL LOGIC THEOREM PROVER
%R Technical Note 350
%I SRI International
%C Menlo Park, California
%D DECEMBER 1985

%A RICHARD WALDINGER
%A ZOHAR MANNA
%T THE ORIGIN OF THE BINARY-SEARCH PARADIGM
%R Technical Note 351
%I SRI International
%C Menlo Park, California
%D APRIL 1985
%X In a binary-search algorithm for the computation of a
numerical function, the interval in which the desired output is
sought is divided in half at each iteration. The paper considers how
such algorithms might be derived from their specifications by an
automatic program-synthesis system. The derivation of the
binary-search concept has been found to be surprisingly
straightforward. The programs obtained, though reasonably simple and
efficient, are quite different from those that would have been
costructed by informal means.

%A SUSAN U. STUCKY
%T CONFIGURATIONAL VARIATION IN ENGLISH: A STUDY OF EXTRAPOSITION AND RELATED MATTERS
%R Technical Note 353
%I SRI International
%C Menlo Park, California
%D MARCH 1985
%X Natural languages typically permit more than one order of
words or phrases, though they differ with respect to both the amount
of order variation allowed and the kind of information carried by
these differences in order. In some languages, linear order conveys
information about the argument relations. In others, this role is
perfomed by morphology alone. Linear order may otherwise bear
information about the status of the content of an utterance in the
discourse--whether it is new or expected, for instance. Even within a
particular language, different orders may carry fundamentally
disparate kinds of information.

%A STUART SHIEBER
%T CRITERIA FOR DESIGNING COMPUTER FACILITIES FOR LINGUISTIC ANALYSIS
%R Technical Note 354
%I SRI International
%C Menlo Park, California
%D APRIL 1985
%X In the natural-language-processing research community, the
usefulness of computer tools for testing linguistic analyses is often
taken for granted. Linguists, on the other hand, have generally been
unaware of or ambivalent about such devices. We discuss several
aspects of computer use that are preeminent in establishing the
utility for linguistic research of computer tools and describe several
factors that must be considered in designing such computer tools to
aid in testing linguistic analyses of grammatical phenomena. A series
of design alternatives, some theoretically and some practically
motivated, is then based on the resultant criteria. We present one
way of pinning down these choices which culminates in a description of
a particular grammar formalism for use in computer linguistic tools.
The PATR-II formalism thus serves to exemplify our general perspective.

%A ZOHAR MANNA
%A RICHARD WALDINGER
%T SPECIAL RELATIONS IN AUTOMATED DEDUCTION
%R Technical Note 355
%I SRI International
%C Menlo Park, California
%D JUNE 1985
%X Two deduction rules are introduced to give streamlined
treatment to relations of special importance in an automated
theorem-proving system. These rules, the ``relation
replacement'' and ``relation matching'' rules, generalize to an
arbitrary binary relation the paramodulation and E-resolution rules,
respectively, for equality, and may operate within a noclausal or
clausal system. The new rules depend on an extension of the notion of
``polarity'' to apply to subterms as well as to subsentences,
with respect to a given binary relation. The rules allow us to
eliminate troublesome axioms, such as transitivity and monotonicity,
from the system; proofs are shorter and more comprehensible, and the
search space is correspondingly deflated.

%A BARBARA GROSZ
%A DOUGLAS E. APPELT
%A PAUL MARTIN
%A FERNANDO PEREIRA
%T TEAM: AN EXPERIMENT IN THE DESIGN OF TRANSPORTABLE NATURAL-LANGUAGE INTERFACES
%R Technical Note 356
%I SRI International
%C Menlo Park, California
%D AUGUST 1985
%X This paper describes TEAM, a transportable natural-language
interface system. TEAM was constructed to test the feasibility of
building a natural-language system that could be adapted to interface
with new databases by users who were not experts in natural-language
processing. The paper presents an overview of the system design,
emphasizing those choices that were imposed by the demands of
transportability. It discusses several general problems of
natural-language processing that were faced in constructing the
system, including quantifier scoping, various pragmatic issues, and
verb acquisition. The paper also provides a comparison of TEAM with
several other transportable systems; the comparison includes
discussion of the range of natural language handled by each as well as
a description of the approach taken to transportability in each.

%A ALEX P. PENTLAND
%T PERCEPTUAL ORGANIZATION AND THE REPRESENTATION OF NATURAL FORM
%R Technical Note 357 (Revised)
%I SRI International
%C Menlo Park, California
%D JULY 1986
%X To support our reasoning abilities perception must recover
environment regularities--e.g., rigidity, objectness,'' axes of
symmetry--for later use of cognition. To create a theory of how our
perceptual apparatus can produce meaningful cognitive primitives from
an array of image intensities we require a representation whose
elements may be lawfully related to impotant physical regularities,
and that correctly describes the perceptual organization people impose
on the stimulus. Unfortunately, the representations that are
currently available were originally developed for other purposes (e.g.,
physics, engineering) and have so far proven unsuitable for the
problems of perception or commo-sense reasoning. In answer to this
problem we present a representation that has proven competent to
accurately describe an extensive variety of natrual forms (e.g.,
people, mountains, clouds, trees), as well as man-made forms, in a
succinct and natural manner. The approach taken in this
representational system is to describe scene structure at a scale that
is similar to our naive perceptual notion of a part,'' by use of
descriptions that reflect a possible formative history of the object,
e.g., how the object might have been constructed from lumps of clay.
For this representation to be useful it must be possible to recover
such descriptions from image data; we show that the primitive elements
of such descriptions may be recovered in an overconstrained and
therefore reliable manner. We believe that this descriptive system
makes an important contribution towards solving current problems in
perceiving and reasoning about natural forms by allowing us to
construct accurate descriptions that are extremely compact and that
capture people's intuitive notions about the part structure of
three-dimensional forms.

%A EDWIN P.D. PEDNAULT
%T PRELIMINARY REPORT ON A THEORY OF PLAN SYNTHESIS
%R Technical Note 358
%I SRI International
%C Menlo Park, California
%D AUGUST1985

%A DAVID ISRAEL
%T A WEAK LOGIC OF KNOWLEDGE AND BELIEF: EPISTEMIC
AND DOXASTIC LOGIC FOR THE YUPPIE GENERATION
%R Technical Note 359
%I SRI International
%C Menlo Park, California
%D 1985

%A AMY L. LANSKY
%T BEHAVIORAL SPECIFICATION AND PLANNING FOR MULTIAGENT DOMAINS
%R Technical Note 360
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1985
%X This report discusses a new approach to the specification of
properties of multiagent enviroments and the generation of plans for
such domains. The ideas presented elaborate previous work on a
formal, behavioral model of concurrent action, called GEM (the Group
Element Model). By combining the GEM specification formalism with
artificial intelligence techniques for planning, we have devised a
framework that seems promising in several respects. First, instead of
ad hoc planning techniques, we are utilizing a formal concurrency
model as a basis for planning. Secondly, the model encourages the
description of domain properties in terms of behavioral constraints,
rather than using more traditional state predicate approaches.
Behavioral descriptions, which emphasize the causal, temporal, and
simultaneity relationships among actions, are particularly suited to
describing the complex properties of multiagent domains. Finally, we
present an initial proposal for a planner based on behavioral forms of
representation. Given a set of constraints describing a problem
domain, the proposed planner generates plans through a process of
incremental constraint satisfaction.

%A STUART M. SHIEBER
%A LAURI KARTTUNEN
%A FERNANDO PEREIRA
%A MARTIN KAY
%T MORE NOTES FROM THE UNIFICATION UNDERGROUND: A SECOND
COMPILATION OF PAPERS ON UNIFICATION-BASED GRAMMAR
FORMALISMS
%R Technical Note 361
%I SRI International
%C Menlo Park, California
%D AUGUST 1985

%A STANLEY J. ROSENSCHEIN
%T FORMAL THEORIES OF KNOWLEDGE IN AI AND ROBOTICS
%R Technical Note 362
%I SRI International
%C Menlo Park, California
%D SEPTEMBER 1985
%X Although the concept of knowledge plays a central role in
artificial intelligence, the theoretical foundations of knowledge
representation currently rest on a very limited conception of what it
means for a machine to know a proposition. In the current view, the
machine is regarded as knowing a fact if its state either explicitly
encodes the fact as a sentence of an interpreted formal language or if
such a sentence can be derived from other encoded sentences according
to the rules of an appropriate logical system. We contract this
conception, the interpreted-symbolic-structure approach, with another,
the situated-automata approach, whih seeks to analyze knowledge in
terms of relations between the state of a machine and the state of its
environment over time using logic as a metalanguage in which the
analysis is carried out.

%A KURT G. KONOLIGE
%T EXPERIMENTAL ROBOT PSYCHOLOGY
%R Technical Note 363
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1985
%X In this paper I argue that an intentional methodology is
appropriate in the design of robot agents in cooperative planning
domains--at least in those domains that are sufficiently open-ended to
require extensive reasoning about the environment (including other
agents). That is, we should take seriously the notion that an agent's
cognitive state expresses beliefs about the world, desires or goals to
change the world, and intentions or plans that are likely to achieve
these goals. In cooperative situations, reasoning about these cognitive
structures is important for communication and problem-solving.
How can we construct such models of agent cognition? Here I propose
an approach that I call it experimental robot psychology because it
involves formalizing and reasoning about the design of existing robot
agents. It shows promise of yielding an efficient and general means
of reasoning about cognitive states.

%A HANS USZKOREIT
%T CONSTRAINTS ON ORDER
%R Technical Note 364
%I SRI International
%C Menlo Park, California
%D OCTOBER 1985
%X Partially free word order as it occurs in German and
probably to some extent in all natural languages arises through the
interaction of potentially conflicting ordering principles. A
modified linear precedence (LP) component of Generalized Phrase
Structure Grammar (GPSG) is proposed that accommodates partially free
word order. In the revised framework, LP rules are sets of LP
clauses. In a case in which these clauses make conflicting ordering
predictions, more than one order is grammatical. LP clauses may refer
to different types of categorial information such as category
features, morphological case, thematic roles, discourse roles, and
phonological information. The modified framework is applied to
examples from German. It is demonstrated how the new LP component
constrains the linear ordering of major nominal categories.

%A MARSHA JO HANNAH
%T EVALUATION OF STEREOSYS VS. OTHER STEREO SYSTEMS
%R Technical Note 365
%I SRI International
%C Menlo Park, California
%D OCTOBER 1985

%A MARSHA JO HANNAH
%T THE STEREO CHALLENGE DATA BASE
%R Technical Note 366
%I SRI International
%C Menlo Park, California
%D OCTOBER 1985

%A THOMAS M. STRAT
%T ONE-EYED STEREO: A UNIFIED STRATEGY TO RECOVER SHAPE
FROM A SINGLE IMAGE
%R Technical Note 367
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1985
%X A single two-dimensional image is an ambiguous
representation of the three-dimensional world--many different scenes
could have poduced the same image--yet the human visual system is
extremely successful at recovering a qualitatively correct dept model
from this type of representation. Workers in the field of
computational vision have devised a number of distinct schemes that
attempt to emulate this human capability; these schemes are
collectively known as shape from....'' methods (e.g., shape from
shading, shape from texture, or shape from contour). In this paper we
contend that the distinct assumptions made in each of these schemes
must be tantamount to providing a second (virtual) image of the
original scene, and that any one of these approaches can be translated
into a conventional stereo formalism. In paticular, we show that it
is frequently possible to structure the problem as one of recovering
depth from a stereo pair consisting of the supplied perspective image
(the original image) and an hypothesized orthograhic image (the
virtual image). We present a new algorithm of the form required to
accomplish this type of stereo reconstruction task.

%A AMICHAI KRONFELD
%T REFERENCE AND DENOTATION: THE DESCRIPTIVE MODEL
%R Technical Note 368
%I SRI International
%C Menlo Park, California
%D OCTOBER 1985

%A BARBARA J. GROSZ
%T THE STRUCTURES OF DISCOURSE STRUCTURE
%R Technical Note 369
%I SRI International
%C Menlo Park, California
%D NOVEMBER 1985

%A HANS USZKOREIT
DATE : OCTOBER 1985
%T LINEAR PRECEDENCE IN DISCONTINUOUS CONSTITUENTS: COMPLEX FRONTING IN GERMAN
%R Technical Note 371
%I SRI International
%C Menlo Park, California
%X Syntactic processes that have been identified as sources of
discontinuous constituents exhibit radically different properties.
They seem to fall into several classes: leftward extraction,''
right-ward movements,'' scrambling'' phenomena, and parenthetical
insertions. Current linguistic theories differ as to the formal tools
they employ both for describing the paticipaing syntactic phenomena
and for encoding the resulting representations.
In this paper, the general problem of determining the linear order in
the discontinuous parts of a constituent is discussed. The focus lies
on frameworks that use their feature mechanisms for connecting the
noncontiguous elements. It is then shown that the current framework
of Generalized Phrase Structure Grammar (GPSG) is not suited for
describing the interaction of leftward extractions, scrambling, and
constraints on linear order. The relevant data come from German
fronting. Previous analyses (Johnson 1983; Nerbonne 1984; Uszkoreit
1982; 1984) have neglected certain types of fronting or failed to
integrate their account of fronting properly with an analysis of
linear precedence.

%A MICHAEL P. GEORGEFF
%A CHRISTOPHER S. WALLACE
%T A GENERAL SELECTION CRITERION FOR INDUCTIVE INFERENCE
%R Technical Note 372
%I SRI International
%C Menlo Park, California
%D DECEMBER 1985
%X This paper presents a general criterion for measuring the
degree to which any given theory can be considered a good explanation
of a particular body of data. A formal definition of what constitutes
an acceptable explanation of a body of data is given, and the length
of explanation used as a measure for selecting the best of a set of
competing theories. Unlike most previous approaches to inductive
inference, the length of explanation includes a measure of the com-
plexity or likelihood of a theory as well as a measure of the degree
of fit between theory and data. In this way, prior expectations about
the environment can be represented, thus providing a hypothesis space
in which search for good or optimal theories is made more tractable.
Furthermore, it is shown how theories can be represented as structures
tha reflect the conceptual entities used to describe and reason about
the given problem domain.

%A STEPHEN T. BARNARD
%T A STOCHASTIC APPROACH TO STEREO VISION
%R Technical Note 373
%I SRI International
%C Menlo Park, California
%D APRIL 1986
%X A stochastic optimization approach to stereo matching is
presented. Unlike conventional correlation matching and feature
matching, the approach provides a dense array of disparities,
eliminating the need for interpolation. First, the stereo matching
problem is defined in terms of finding a disparity map that satisfies
two competing constraints: (1) matched points should have similar
image intensity, and (2) the disparity map should be smooth. These
constraints are expressed in an energy'' function that can be
evaluated locally. A simulated annealing algorithm is used to find a
disparity map that has very low energy (i.e., in which both con-
straints have simultaneously been approximately satisfied). Annealing
allows the large-scale structure of the disparity map to emerge at
higher temperaures, and avoids the problem of converging too quickly
on a local minimum. Results are shown for a spase random-dot
stereogram, a vertical aerial stereogram (shown in comparison to
ground truth), and an oblique ground-level scene with occlusion
boundaries.

%A MICHAEL P. GEORGEFF
%T MANY AGENTS ARE BETTER THAN ONE
%R Technical Note 417
%I SRI International
%C Menlo Park, California
%D MARCH 1987
%P 16
%X This paper aims to show how much of the frame problem can be
alleviated by using domain models that allow for the simultaneous
occurrence of actions and events. First, a generalize situation
calculus is constructed for describing and reasoning about events
in multiagent settings. Notions of independence and causality are then
introduced and it is shown how they can be used to determine the
persistence of facts over time. Finally, its is shown how these
notions, together with traditional predicate circumscription,
make it possible to retain a simple model of actionm while avoiding
most of the difficulties associated with the frame problem.