E1AR0002@SMUVM1.BITNET (11/11/86)
TECHNICAL NOTE: 246\hfill PRICE: \$16.00\\[0.01in]
\noindent TITLE: DEDUCTIVE SYNTHESIS OF THE UNIFICATION ALGORITHM\\
AUTHORS: ZOHAR MANNA and RICHARD WALDINGER\\
DATE: JULY 1981\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 248\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: ARTIFICIAL INTELLIGENCE: ENGINEERING, SCIENCE OR SLOGAN?\\
AUTHOR: NILS J. NILSSON\\
DATE: JULY 1981\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 251\hfill PRICE: \$14.00\\[0.01in]
\noindent TITLE: PRACTICAL NATURAL LANGUAGE PROCESSING BY COMPUTER\\
AUTHOR: ROBERT C. MOORE\\
DATE: OCTOBER 1981\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 252\hfill PRICE: \$12.00\\[0.01in]
\noindent TITLE: MACHINE LEARNING FOR INFORMATION MANAGEMENT\\
AUTHORS: NORMAN HAAS and GARY HENDRIX\\
DATE: JULY 1981\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 253\hfill PRICE: \$20.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= COMPUTATIONAL STRATEGIES FOR ANALYZING THE ORGANIZATION\\
\> AND USE OF INFORMATION\\
AUTHOR: DONALD E. WALKER\\
DATE: JULY 1981\\[-0.15in]
\end{tabbing}
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 254\hfill PRICE: \$20.00\\[0.01in]
\noindent TITLE: A TEAM USER'S GUIDE\\
AUTHORS: ARMAR A. ARCHBOLD, BARBARA GROSZ, and DANIEL SAGALOWICZ\\
DATE: DECEMBER 1981\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 255\hfill PRICE: \$14.00\\[0.01in]
\noindent TITLE: THE DATABASE AS MODEL: A METATHEORETIC APPROACH\\
AUTHOR: KURT KONOLIGE\\
DATE: SEPTEMBER 1981\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 256\hfill PRICE: \$14.00\\[0.01in]
\noindent TITLE: A PROBABILISTIC MODEL FOR UNCERTAIN PROBLEM SOLVING\\
AUTHOR: ARTHUR M. FARLEY\\
DATE: DECEMBER 1981\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 257\hfill PRICE: \$20.00\\[0.01in]
\noindent TITLE: RESEARCH ON NATURAL-LANGUAGE PROCESSING AT SRI\\
AUTHOR: BARBARA J. GROSZ\\
DATE: NOVEMBER 1981\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 258\hfill PRICE: \$10.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= PARALLELISM IN PLANNING AND PROBLEM SOLVING:\\
\> REASONING ABOUT RESOURCES\\
AUTHOR: DAVID E. WILKINS\\
DATE: JANUARY 1982\\[-0.15in]
\end{tabbing}
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 259\hfill PRICE: \$20.00\\[0.01in]
\noindent TITLE: PLANNING NATURAL-LANGUAGE UTTERANCES TO SATISFY MULTIPLE
GOALS\\
AUTHOR: DOUGLAS E. APPELT\\
DATE: MARCH 1982\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 260\hfill PRICE: \$18.00\\[0.01in]
\noindent TITLE: SPECIAL RELATIONS IN PROGRAM-SYNTHETIC DEDUCTION\\
AUTHORS: ZOHAR MANNA and RICHARD WALDINGER\\
DATE: MARCH 1982\\[0.01in]
ABSTRACT: Program synthesis is the automated deviation of a
computer program from a given
specification. In the \underline{deductive} \underline{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 \underline{partially} \underline{skolemized}
\underline{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 \underline{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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 261\hfill PRICE: \$14.00\\[0.01in]
\noindent TITLE: COMPUTATIONAL STEREO\\
AUTHORS: STEPHEN T. BARNARD and MARTIN A. FISCHLER\\
DATE: MARCH 1982\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 263R\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: TEAM: A TRANSPORTABLE NATURAL-LANGUAGE INTERFACE SYSTEM\\
AUTHOR: BARBARA J. GROSZ\\
DATE: NOVEMBER 1982\\[0.01in]
ABSTRACT: 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 \underline{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 \underline{T}ransportable \underline{E}nglish
\underline{A}ccess Data
\underline{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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
-------