Subject: AIList Digest V4 #90

From: vtcs1::in% ([email-masked])
Date: Wed, 16 Apr 86 00:49:11 est

AIList Digest            Tuesday, 15 Apr 1986      Volume 4 : Issue 90

Today's Topics:
  Bibliography - Recent Articles #5

----------------------------------------------------------------------

Date: WED, 10 JAN 84 17:02:23 CDT
From: [email-masked]
Subject: Recent Articles #5

%A M. Celenk
%A S. H. Smith
%T A New Systematic Method for Color Image Analysis
%R Tech. Rep EE 8509
%D DEC 1985
%I Stevens Institute of Technology Electrical Engineering and Computer
Science Departments
%K AI06

%A S. A. Friedberg
%T Symmetry Evaluators
%R TR134 (revised)
%D JAN 1986
%I The University of Rochester Computer Science Department
%K AI06 Hough transform
%X $1.25 24 pages

%A D. H. Ballard
%A P. J. Hayes
%T Parallel Logical Inference and Energy Minimization
%R TR142
%D DEC 1985
%I The University of Rochester Computer Science Department
%K connectionist H03 AI08
%X $1.50 34 pages

%A J. A. Feldman
%T Parallelism in High Level Vision
%R TR146
%D JAN 1985
%I The University of Rochester Computer Science Department
%K H03 AI08 AI06
%X 33 pages $1.50

%A J. Tenenberg
%T Reasoning Using Exclusion: an Extension of Clausal Form
%R TR147
%D JAN 1986
%I The University of Rochester Computer Science Department
%K common sense reasoning AI10 AI11
%X 25 pages $1.25

%A D. H. Ballard
%T Form Perception as Transformation
%R TR148
%D JAN 1986
%I The University of Rochester Computer Science Department
%K AI06 AI07
%X 34 pages $1.50

%A A. Basu
%A C. M. Brown
%T Algorithms and Hardware for Efficient Image Smoothing
%R TR149
%D DEC 1984
%I The University of Rochester Computer Science Department
%K AI06 H03 median mean filters
%X 20 pages $1.00

%A B. Sarachan
%T Experiments in Rotational Egomotion Calculation
%R TR152
%D FEB 1985
%I The University of Rochester Computer Science Department
%K AI06
%X 26 pages $1.25 [Seems to be a paper for a robot to determine if it got
rotated.  LEFF]

%A G. W. Cottrell
%T A Connectionist Approach to Word Sense Disambiguation
%R TR154
%D MAY 1985 (PHD Thesis)
%I The University of Rochester Computer Science Department
%K AI02 AI08
%X 242 pages $7.25

%A J. A. Feldman
%T Energy and the Behavior of Connection Models
%R TR155
%D NOV 1985
%I The University of Rochester Computer Science Department
%K H03 AI12
%X 41 pages, $1.75

%A D. Sher
%T Template Matching on Parallel Architectures
%R TR156
%D JUL 1985
%I The University of Rochester Computer Science Department
%K H03 AI06 Fourier Transform WARP Butterfly
%X 28 pages, $1.25

%A A. Bandopadhay
%A J. Aloimonos
%T Perception of Rigid Motion from Spatio-Temporal Derivatives of Optical Flow
%R TR157
%D MAR 1985
%I The University of Rochester Computer Science Department
%K AI06
%X 18 pages $1.00 [Seems to be another paper on getting a robot to tell
whether somebody rotated it or not LEFF]

%A J. Aloimonos
%A A. Bandopadhay
%T Perception of Structures from Motion: Lower Bound Results
%R TR158
%D MAR 1985
%I The University of Rochester Computer Science Department
%K AI06
%X 16 pages $1.00

%A J. Aloimonos
%T One Eye Suffices: a Computational Model of Monocular Robot Depth Perception
%R TR160
%D DEC 1984
%I The University of Rochester Computer Science Department
%K AI06 optical flow depth perception orthographic perspective projection
%X 16 pages $1.00

%A J. Aloimonos
%A P. B. Chou
%T Detection of Surface Orientation and Motion from Texture: 1. The
Case of Planes
%R TR161
%I The University of Rochester Computer Science Department
%K AI06 Gibson
%X 21 pages $1.25

%A Henry A. Kautz
%T Toward a Theory of Plan Recognition
%R TR162
%I The University of Rochester Computer Science Department
%K AI09
%D JUL 1985
%X 15 pages $1.00

%A L. Shastri
%T Evidential Reasoning in Semantic Networks: A Formal Theory and its
Parallel Implementation
%R TR166
%I The University of Rochester Computer Science Department
%K H03 O04
%D SEP 1985
%X 256 pages $7.50

%A D. H. Ballard
%A P. Gardner
%A M. Srinivas
%T Graph Problems and Connection Architectures
%I The University of Rochester Computer Science Department
%R TR167
%K H03 AI12
%D DEC 1985
%X 24 pages $1.25

%A  A. Bandopadhay
%T Constraints on the Computation of Rigid Motion Parameters from
Retial Displacements
%I The University of Rochester Computer Science Department
%R TR168
%K AI07 AI06
%D OCT 1985
%X 77 pages, $2.75 [Seems to be another paper on getting a robot to tell
whether somebody rotated it or not LEFF]

%A A. Bandopadhay
%A J. Aloimonos
%T Perception of Structure and Motion of Rigid Objects
%D DEC 1985
%I The University of Rochester Computer Science Department
%R TR169
%K AI07 AI06
%X 55 pages $2.00 [Seems to be another paper on getting a robot to tell
whether somebody rotated it or not LEFF]

%A D. J. Litman
%T Plan Recognition and Discourse Analysis: An Integrated Approach for
Understanding Dialogues
%D  1985
%R TR170
%I The University of Rochester Computer Science Department
%K AI02 AI09
%X 197 pages $6.00

%A J. A. Feldman
%A D. H. Ballard
%A C. M. Brown
%A G. S. Drell
%T Rochester Connectionist Papers 1979-85
%D DEC 1985
%R TR172
%I The University of Rochester Computer Science Department
%K AI12 AT21
%X no charge

%A N. Murray
%A E. Rosenthal
%T On Deleting Links in Semantic Graphs
%R TR 85-4
%I State University of New York at Albany, Computer Science Department
%K predicate calculus path resolution AI11

%A S. Chaiken
%A N. Murray
%A E. Rosenthal
%T An Application of $P sub 4$ Free Free Graphs in Theorem Proving
%R TR85-8
%I State University of New York at Albany, Computer Science Department
%K AI11
%X We describe the application of graphs that have no induced $P sub 4$
(4 vertex path) subgraphs to automatic theorem proving.  The semantics of
a propositional formula are expressed in terms of the maximal cliques in
a $P sub 4$ free graph rather than by truth assignments.  Arc sets of s-t
paths in a series parallel network provide an equivalent formulation.
We provide combinatorial foundations for Murray and Rosenthal's work
on path resolution (e. g. TR84-1, TR 84-12 and TR 85-4)  For
any graph G, a c-block (resp d-block) is an induced subgraph H in G such
that for all  maximal cliques (resp maximal stable sets) C in G, C $int$
H is $PHI$ or is a maximal clique (resp. maximal stable set) in H.  A
full block is botha c-block and a d-block.  Blocks are generalizations of
substitution subgraphs which occur in Lovasz's work on perfect graphs.
Theorem:  If full block H is $P sub 4$-free then H must arise by
substitution.  Other properties in these blocks in arbitrary graphs and
in $P sub 4$-free graphs are given.  These constructs are instrumental
in the development of several closely related inference rules collectively
referred to as path resolution.  Finally we show how semantics of $P sub 4$
graphs are
generalized to blocking systems by Minty's painting lemma.  This suggests
possible generalization of path resolution to other combinatorial structures.

%A M. Balaban
%T Western Tonal Music - A New Domain for AI Research
%R TR 85-10
%I State University of New York at Albany, Computer Science Department
%K AI02 AA25

%A M. Balaban
%T Knowledge Representation and Inferencing in a Musical Database
%R TR 85-11
%I State University of New York at Albany, Computer Science Department
%K frames AA25 AA14 T02

%A M. Balaban
%T The Generalized Concept Formalism - A Frame and Logic Based
Representation Model
%R TR 85-20
%I State University of New York at Albany, Computer Science Department
%K AA25 T02

%A Mira Balaban
%T Foundations for Artificial Intelligence Research of Western Tonal Music
%R TR 85-22
%I State University of New York at Albany, Computer Science Department
%K AA25

%A M. Balaban
%T CSM: An AI Approach to the Study of Western Tonal Music
%R TR 85-24
%I State University of New York at Albany, Computer Science Department
%K AA25

%A H. B. Hunt
%A R. E. Stearns
%T Distributive Lattices and the Complexity of Logics and Probability
%R TR 85-28
%I State University of New York at Albany, Computer Science Department
%K AI11 O04
%X Relationships between number of repetitions of variables in formulas
and complexity of decision problems for the formulas.
Applications to logic and probability:
1) Any reasonable propositional calculus with a reasonable implication
operator has a coNP-hard logical Validy problem.  This is true for very
simple formulas involving or, and and a single occurrence of the implication
operator
2) The set of theorems of the propositional calculus of classical
implicative logic is coNP complete
3. Computing the probabilities of a joint event and a conditional event becomes
"hard" almost immediately when the events E1 and E2 are not statistically
independent

%A H. B. Hunt
%A R. E. Stearns
%T Monotone Boolean Formulas, Distributive Lattices, and the Complexities
of Logics, Algebraic Structures, and Computation Structures (Preliminary Report)
%R TR85-29
%I State University of New York at Albany, Computer Science Department
%K AI11 O04

%A Andrew Laine
%A Seymour V. Pollack
%T The Enhanced Wudma Image Processing
%R WUCS-85-1
%I Department of Computer Science, Washington University
%C St. Louis, Missouri
%K AI06

%A S. E. Elnahas
%A R. G. Jost
%A J. R. Cox
%A R. L. Hill
%T Transmission Progressive of Digital Diagnostic Images
%R WUCS-85-8
%I Department of Computer Science, Washington University
%C St. Louis, Missouri
%K AI06 AA01
%X Progressive transmission of digital pictures permits the receiver
to construct an approximate picture first, then gradually improve the quality
of reconstruction.

%A James R. Slagle
%A JOhn M. Long
%A Michael R. Wick
%A John P. Matts
%A Arthur  S. Leon
%T Expert Systems in Medical Studies- A New Twist
%R TR 86-3
%I University of Minessota, Department of Computer Science
%D 1986
%K AA01 AI01

%A Robert M. Herndon, Jr.
%A Valdis A. Berzins
%T An Interpretive Technique for Evaluating Functional Attribute
Grammars
%R TR 86-5
%I University of Minessota, Department of Computer Science
%R 1986

%A Robert M. Herndon, Jr.
%A Valdis A. Berzins
%T A Method for the Construction of Dynamic, Lazy Evaluators for
Functional Attribute Grammars
%R 86-6
%I University of Minessota, Department of Computer Science
%R 1986

%A J. Schwartz
%A M. Sharir
%T Efficient Motion Planning Algorithms in Environments of
Bounded Local Complexity
%R 164
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%K AI07
%D JUN 1985

%A J. Schwartz
%A M. Sharir
%T Identification of Partially Obscured Objects in Two Dimensions
by Matching of Noisy 'Characteristic Curves'
%R 165
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%D JUN 1985
%K AI06

%A G. Landau
%A U. Vishkin
%T Efficient String Matching with k Mismatches
%R 167
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%D JUN 1985
%X Give a text of length n, a pattern of length m and an integer k,
we present an algorithm for finding all occurrences of the patterns in
the text, with at most k mismatches running in O(k(mlogm + n)

%A G. Landau
%A U. Vishkin
%T An Efficient String Matching Algorithm with k Differences for
Nucleotide and Amino Acid Sequences
%R 168
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%D JUN 1985
%X Algorithm to allow for optimal alignment of one sequence, the
pattern of length m, with another longer sequence the text, of
length n.  These algorithms allow mismatches, deletions
and insertions.  If k is the maximum number of differences,
then the time is O(k sup 2 n).

%A R. Hummel
%A A. Rojer
%T Connected Component Labeling in Image Processing with
MIMD Architectures
%R 173
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%D SEP 1985
%K AI06  H03

%A S. Zucker
%A R. Hummel
%T Receptive Fields and the Representation of Visual Information
%R 176
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%D SEP 1985
%K AI06 AI08 Gaussian retina
%X Hypothesis that the receptive fields of the retina provide
a suitable method for transmitting the image over the optic nerve
which is a limited bandwidth channel.

%A M. Landy
%A R. Hummel
%T A Brief Survey of Knowledge Aggregation Methods
%R 177
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%D SEP 1985
%K AI04

%A G. Landau
%A U. Vishkin
%T Efficient String Matching with k Differences
%R 186
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%D OCT 1985
%X If the mismatches considered are a single character mismatch,
a superfluous character in the text or pattern, there exists an
algorithm that runs in time O(m+k sup 2 n ) when the
alphabet size is fixed and O(m log m + k sup 2 n) otherwise
where m is length of pattern, k is the number of mismatches
and n is the text.

%A D. Leven
%A M. Sharir
%T On the Number of Critical Free Contacts of a Convex Polygonal
Object Moving in 2-D Polygonal Space
%R 187
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%D OCT 1985
%K AI07

%A J. Burdea
%A H. Wolfson
%T Automated Assembly of a Jigsaw Puzzle Using the IBM 7565 Robot
%R 188
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%D NOV 1985
%K AI07

%A E. Davis
%T Constraint Propagation on Real-Valued Quantities
%R 189
%I New York University, Courant Institute of Mathematical Sciences,
Department of Computer Science
%D NOV 1985
%K AI03

%A N. S. Sridharan
%T Representing Knowledge in Introduction using TAXMAN Examples
%R LRP-TR-12
%D 11/81
%I Rutgers University, Department of Computer Science

%R LRP-TR-13
%D 1/82
%T "A Computational Theory of Legal Argument"
%A L. T. McCarty
%A N. S. Sridharan
%I Rutgers University Department of Computer Science
%K AA24 tax
%X The TAXMAN project is an experiment in the application of artificial
intelligence to the study of legal reasoning and legal argumentation,
using corporate tax law as an experimental problem domain.  Legal
concepts possess what is often termed "open-texture", that is, their
definitions are subject to a continual process of construction and
modification during the analysis of a contested case.  We have
developed a "prototype-plus-deformation" representation for the
structure of such concepts, a representation which facilitates the
formulation of several systematic methods of conceptual modification.
We propose now to construct a cognitive model of the process of legal
argument, using this representation.  The research is aimed at
developing explanations for the persuasiveness of certain strategies
of legal argument, and at developing further the criteria of
conceptual coherence, both task-specific and task-independent, which
seem to constrain the space of plausible arguments.  We emphasize not
only the contributions of this research to Artificial Intelligence,
but also the insights that may result for some of the fundamental
issues in jurisprudence.

%R LRP-TR-14
%D 9/82
%T "A Flexible Structure for Knowledge"
%A N.S. Sridharan
%K AA24 tax  AI04
%I Rutgers University Department of Computer Science
%X Concepts often dealt with in legal reasoning and argumentation are
amorphous.  For TAXMAN II, we have proposed in the past a Prototype
and Deformation model for these amorphous concepts.  In this model, a
concept is represented as a structured space of exemplars, that is as
a set of exemplars, structured by transformations and relationships
among them.  In this paper, the idea of representing a concept as a
structured space of exemplars is extended; suggesting that all
knowledge represented in a computer be organized as structured spaces
and subspaces.  Concepts are represented as spaces; concepts are also
members of spaces.  This duality is exploited to gain flexibility in
the representation, that is, changes to the structure can be effected
through computation.

%R LRP-TR-15
%D 6/83
%T "Concept Learning by Building and Applying Transformations Between
Object Descriptions"
%A Donna Nagel
%K AI04 analogy matching
%I Rutgers University Department of Computer Science
%X The Concept Learning presented here emphasizes the building of a
transformation between an instance of a concept and another instance
which is distinguished as a prototype of the concept.  A recursive
partial matcher is used to pinpoint components of structural object
descriptions of the training instances for matching.  Three procedures
are described for inducing matches:  building simple analogies,
applying primitive transformations, and finding projections of the
instances into domains of knowledge relevant to the concept being
learned.  This research is experimental in nature and directed at
discovering flexible ways to define and represent concepts which are
amorphous and open-textured.

%R LRP-TR-16
%D 3/84
%T "EVOLVING SYSTEMS OF KNOWLEDGE"
%A N.S. Sridharan
%I Rutgers University Department of Computer Science
%K AI01
%X The enterprise of developing knowledge-based systems, is currently
witnessing great growth in popularity.  The central unity of such
programs is that they interpret knowledge that is explicitly encoded
as @i[rules].  This paper is a statement of personal perspective by a
researcher interested in fundamental issues in the symbolic
representation and organization of knowledge.  The discussion covers
the nature of rules (Sec. 3), and methods of rule-handling (Sec. 4).
The paper concludes with a discussion of how most concepts we use are
open-textured and how they continually evolve with use (Sections
5,6,7).  While rule-based programming comes with certain clear
pay-offs, further fundamental advances in research is needed to extend
the scope of tasks that can be adequately represented in this fashion.

%R LRP-TR-17
%D 6/84
%T "Analogy with Purpose in Legal Reasoning from Precedents"
%A S.Kedar-Cabelli
%D 10/84
%I Rutgers University Department of Computer Science
%K AA24 taxman tax AA04
%X One open problem in current artificial intelligence (AI) models of
learning and reasoning by analogy is: which aspects of the analogous
situations are relevant to the analogy, and which are irrelevant?  It
is currently recognized that analogy involves mapping some underlying
causal network of relations between situations [Winston 82], [Gentner
83], [Burstein 83a], [Carbonell 83].  However, most current models of
analogy provide the system with exactly the relevant relations,
tailor-made to each analogy to be performed.  As AI systems become more
complex, we will have to provide them with the capability of
automatically focusing on the relevant aspects of situations when
reasoning analogically.  These will have to be sifted from the large
amount of information used to represent complex, real-world
situations.
.sp 1
In order to study these general issues, we are examining a particular
case study of learning and reasoning by analogy: forming legal
concepts by legal reasoning from precedents.  This is studied within
the TAXMAN II project, which is investigating legal reasoning using AI
techniques [McCarty & Sridharan 82], [Nagel 83].
.sp 1
In this dissertation proposal, we will discuss the problem and a
proposed solution.  We examine legal reasoning from precedents within
the context of current AI models of analogy.  We then add a focusing
capability.  Current work on goal-directed learning [Mitchell 83a],
[Mitchell & Keller 83], and explanation-based learning [Dejong 83]
applies here: the explanation of how the precedent satisfies the
intent of the law (i.e. its goals, or purposes) helps to automatically
focus the reasoning on what is relevant.

------------------------------

End of AIList Digest
********************