E1AR0002@SMUVM1.BITNET (11/16/86)
TECHNICAL NOTE: 337\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: POSSBLE-WORLD SEMANTICS FOR AUTOEPISTEMIC LOGIC\\
AUTHOR: ROBERT C. MOORE\\
DATE: AUGUST 1984\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 338\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: PARALLEL GUESSING: A STRATEGY FOR HIGH-SPEED COMPUTATION\\
AUTHOR: MARTIN A. FISCHLER and OSCAR FIRSCHEIN\\
DATE: SEPTEMBER 19, 1984\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 339\hfill PRICE: \$15.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= A SIMPLE AND EFFICIENT IMPLEMENTATION OF HIGHER-ORDER\\
\> FUNCTIONS IN LISP\\
AUTHORS: MICHAEL P. GEORGEFF and STEPHEN F. BODNAR\\
DATE: DECEMBER 1984\\[-0.15in]
\end{tabbing}
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 340\hfill PRICE: \$15.00\\[0.01in]
\noindent TITLE: AUTOMATED DEDUCTION BY THEORY RESOLUTION\\
AUTHOR: MARK E. STICKEL\\
DATE: OCTOBER 1984\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 342\hfill PRICE: \$20.00\\[0.01in]
\noindent TITLE: DESCRIPTION OF SRI'S BASELINE STEREO SYSTEM\\
AUTHOR: MARSHA JO HANNAH\\
DATE: OCTOBER 1984\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 343\hfill PRICE: \$15.00\\[0.01in]
\noindent TITLE: TEAM USER'S GUIDE \\
AUTHOR: LORNA SHINKLE \\
DATE: OCTOBER 1984\\[0.01in]
ABSTRACT: TEAM (\underline{T}ransportable \underline{E}nglish Data
\underline{A}ccess \underline{M}edium) 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 344\hfill PRICE: \$10.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= THE REPRESENTATION OF ADVERBS, ADJECTIVES AND EVENTS IN\\
\> LOGICAL FORM \\
AUTHOR: WILLIAM CROFT \\
DATE: DECEMBER 1984\\[-0.15in]
\end{tabbing}
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 345\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: ON THE MATHEMATICAL PROPERTIES OF LINGUISTIC THEORIES\\
AUTHOR: C. RAYMOND PERRAULT\\
DATE: NOVEMBER 1984\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 346\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: RECOVERING FROM EXECUTION ERRORS IN SIPE\\
AUTHOR: DAVID E. WILKINS\\
DATE: JANUARY 1985\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 347\hfill PRICE: \$10.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= TRIANGLE TABLES: A PROPOSAL FOR A ROBOT PROGRAMMING \\
\> LANGUAGE\\
AUTHOR: NILS J. NILSSON\\
DATE: FEBRUARY 1985\\[-0.15in]
\end{tabbing}
ABSTRACT: Structures called \underline{triangle} \underline{tables} were used
in connection
with the SRI robot \underline{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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 348\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: A COGNITIVIST REPLY TO BEHAVIORISM\\
AUTHOR: ROBERT C. MOORE\\
DATE: MARCH 1985\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 350\hfill PRICE: \$15.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= SYNCHRONIZATION OF MULTIAGENT PLANS USING A\\
\> TEMPORAL LOGIC THEOREM PROVER\\
AUTHOR: CHRISTOPHER STUART\\
DATE: DECEMBER 1985\\[-0.15in]
\end{tabbing}
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 351\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: THE ORIGIN OF THE BINARY-SEARCH PARADIGM\\
AUTHOR: RICHARD WALDINGER and ZOHAR MANNA\\
DATE: APRIL 1985\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 353\hfill PRICE: \$10.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= CONFIGURATIONAL VARIATION IN ENGLISH: A STUDY\\
\> OF EXTRAPOSITION AND RELATED MATTERS\\
AUTHOR: SUSAN U. STUCKY\\
DATE: MARCH 1985
\end{tabbing}
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 354\hfill PRICE: \$10.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= CRITERIA FOR DESIGNING COMPUTER FACILITIES FOR\\
\> LINGUISTIC ANALYSIS\\
AUTHOR: STUART SHIEBER\\
DATE: APRIL 1985\\[-0.15in]
\end{tabbing}
ABSTRACT: In the natural-language-processing research community, the
usefulness of computer tools for testing linquistic 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
-------