E1AR0002@SMUVM1.BITNET (11/17/86)
TECHNICAL NOTE: 355\hfill PRICE: \$15.00\\[0.01in]
\noindent TITLE: SPECIAL RELATIONS IN AUTOMATED DEDUCTION\\
AUTHORS: ZOHAR MANNA and RICHARD WALDINGER\\
DATE: JUNE 1985\\[0.01in]
ABSTRACT: Two deduction rules are introduced to give streamlined
treatment to relations of special importance in an automated
theorem-proving system. These rules, the \underline{relation
replacement} and \underline{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
\underline{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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 356\hfill PRICE: \$20.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= TEAM: AN EXPERIMENT IN THE DESIGN OF TRANSPORTABLE\\
\> NATURAL-LANGUAGE INTERFACES\\
AUTHORS: \= BARBARA GROSZ, DOUGLAS E. APPELT, PAUL MARTIN\\
\> FERNANDO PEREIRA\\
DATE: AUGUST 1985\\[-0.15in]
\end{tabbing}
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 357 (Revised)\hfill PRICE: \$10.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= PERCEPTUAL ORGANIZATION AND THE REPRESENTATION OF\\
\> NATURAL FORM\\
AUTHOR: ALEX P. PENTLAND\\
DATE: JULY 1986\\[-0.15in]
\end{tabbing}
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 358\hfill PRICE: \$15.00\\[0.01in]
\noindent TITLE: PRELIMINARY REPORT ON A THEORY OF PLAN SYNTHESIS\\
AUTHOR: EDWIN P.D. PEDNAULT\\
DATE: AUGUST1985\\[0.01in]
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 359\hfill PRICE: \$10.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= A WEAK LOGIC OF KNOWLEDGE AND BELIEF: EPISTEMIC\\
\> AND DOXASTIC LOGIC FOR THE YUPPIE GENERATION\\
AUTHOR: DAVID ISRAEL\\
DATE: 1985\\[-0.15in]
\end{tabbing}
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 360\hfill PRICE: \$15.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= BEHAVIORAL SPECIFICATION AND PLANNING FOR\\
\> MULTIAGENT DOMAINS\\
AUTHOR: AMY L. LANSKY\\
DATE: NOVEMBER 1985\\[-0.15in]
\end{tabbing}
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 361\hfill PRICE: \$15.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= MORE NOTES FROM THE UNIFICATION UNDERGROUND: A SECOND\\
\> COMPILATION OF PAPERS ON UNIFICATION-BASED GRAMMAR\\
\> FORMALISMS\\
AUTHORS: \= STUART M. SHIEBER, LAURI KARTTUNEN, FERNANDO PEREIRA and\\
\> MARTIN KAY\\
DATE: AUGUST 1985\\[-0.15in]
\end{tabbing}
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 362\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: FORMAL THEORIES OF KNOWLEDGE IN AI AND ROBOTICS\\
AUTHOR: STANLEY J. ROSENSCHEIN\\
DATE: SEPTEMBER 1985\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 363\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: EXPERIMENTAL ROBOT PSYCHOLOGY\\
AUTHOR: KURT G. KONOLIGE\\
DATE: NOVEMBER 1985\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 364\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: CONSTRAINTS ON ORDER\\
AUTHOR: HANS USZKOREIT\\
DATE: OCTOBER 1985\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 365\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: EVALUATION OF STEREOSYS VS. OTHER STEREO SYSTEMS\\
AUTHOR: MARSHA JO HANNAH\\
DATE: OCTOBER 1985\\[0.01in]
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 366\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: THE STEREO CHALLENGE DATA BASE\\
AUTHOR: MARSHA JO HANNAH\\
DATE: OCTOBER 1985\\[0.01in]
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 367\hfill PRICE: \$10.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= ONE-EYED STEREO: A UNIFIED STRATEGY TO RECOVER SHAPE \\
\> FROM A SINGLE IMAGE\\
AUTHOR: THOMAS M. STRAT\\
DATE: NOVEMBER 1985\\[-0.15in]
\end{tabbing}
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 368\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: REFERENCE AND DENOTATION: THE DESCRIPTIVE MODEL\\
AUTHOR: AMICHAI KRONFELD\\
DATE: OCTOBER 1985\\[0.01in]
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 369\hfill PRICE: \$15.00\\[0.01in]
\noindent TITLE: THE STRUCTURES OF DISCOURSE STRUCTURE\\
AUTHOR: BARBARA J. GROSZ\\
DATE: NOVEMBER 1985\\[0.01in]
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 371\hfill PRICE: \$10.00\\[-0.15in]
\begin{tabbing}
\noindent TITLE: \= LINEAR PRECEDENCE IN DISCONTINUOUS CONSTITUENTS: COMPLEX\\
\> FRONTING IN GERMAN\\
AUTHOR: HANS USZKOREIT\\
DATE : OCTOBER 1985\\[-0.15in]
\end{tabbing}
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 372\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: A GENERAL SELECTION CRITERION FOR INDUCTIVE INFERENCE\\
AUTHORS: MICHAEL P. GEORGEFF and CHRISTOPHER S. WALLACE\\
DATE: DECEMBER 1985\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
TECHNICAL NOTE: 373\hfill PRICE: \$10.00\\[0.01in]
\noindent TITLE: A STOCHASTIC APPROACH TO STEREO VISION\\
AUTHOR: STEPHEN T. BARNARD\\
DATE: APRIL 1986\\[0.01in]
ABSTRACT: 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.\\
--------------------------------------------------------------------------------
-------------------------------------------------\\
-------