Copy Link
Add to Bookmark
Report
AIList Digest Volume 4 Issue 091
AIList Digest Tuesday, 15 Apr 1986 Volume 4 : Issue 91
Today's Topics:
Bibliography - Recent Articles #6
----------------------------------------------------------------------
Date: WED, 10 JAN 84 17:02:23 CDT
From: E1AR0002%SMUVM1.BITNET@WISCVM.WISC.EDU
Subject: Recent Articles #6
%R CTA-TR-2
%D 8/80
%T Computability on Binary Trees - An Extended Abstract
%A A. Yasuhara
%A F. Hawrusik
%A K.N. Venkataraman
%D 1/82
%I Rutgers University
%X We propose an effective method of computation on finite binary trees
that is analogous to the effective computation on the natural numbers
determined by the partial recursive functions. Not surprisingly, the
method is LISP-like. A finitely axiomatizable theory is given that is
shown to be just strong enough to represent the class of functions
computable by this method. Several natural subclasses; of this class
of functions are delineated and they are shown to be different from
one another.
%R CTA-TR-3
%D 3/81
%T Sub Classes of Programs for Computing on Binary Trees
%A K.N. Venkataraman
%D 1/82
%I Rutgers University
%K T01
%X Several sub-classes of the deterministic regular programs that compute
on binary trees are defined and relations of inclusion and inequality
among these classes in terms of functions computable (by these
programs) are established. Certain properties of these classes of
programs are studied. In particular the sets recognized by these
programs are characterized in terms of the domain and range of these
programs. Most of the results that appear in this paper can easily be
extended to programs computing on other recursively defined data
structures.
%R CTA-TR-4
%D 10/81
%T Decidability of the Purely Existential Fragment of the Theory of
Term Algebras
%A K.N. Venkararaman
%X This thesis is concerned with the question of the decidability and
the complexity of the decision problem for certain fragments of the
theory of free term algebras.
.sp 1
The existential fragment of the theory of term algebras is shown to be
decidable by presenting a non-deterministic algorithm which given a
quantifier free formula P, constructs a solution for P if it has one
and indicates failure if there are no solutions. A detailed proof of
the correctness of the algorithm is given. It is shown that the
decision problem is in NP by proving that if a quantifier-free formula
P has a solution then there is one that can be represented as a dag in
space at most cubic in the length of P. The decision problem is
shown to be complete for NP by reducing 3-SAT to that problem. It is
also shown that the @ @ @-[o] hierarchy over a term algebra
corresponds to the polynomial time hierarchy.
.sp 1
The proof of the fact that the introduction of the selector functions
into the first order language does not increase the complexity of the
existential fragment of the theory is indicated. Thus it is
established that the existential fragment of the theory of list
structures in the language of NIL, CONS, CAR, CDR, = , @u[<] is
NP-complete.
.sp 1
It is shown that the equivalence of PB[;@u{<}] straight line programs
is decidable follows easily from the decidability of the existential
fragment of the theory of list structures.
.sp 1
It is also shown that for any quantifier free formula P (in
the language of a term algebra) there is an algorithm which given a
recursive set S of cardinal numbers @u{<} @ @ @-[o], can decide
whether or not the number of solutions of P is in S.
%R ML-TR-1
%D 7/85
%T Purpose-Directed Analogy
%A Smadar Kedar-Cabelli
%I Rutgers University
%X Recent artificial intelligence models of analogical reasoning are
based on mapping some underlying causal network of relations between
analogous situations. However, causal relations relevant for the
purpose of one analogy may be irrelevant for another. We describe
here a technique which uses an explicit representation of the purpose
of the analogy to automatically create the relevant causal network.
We illustrate the technique with two case studies in which concepts of
everyday artifacts are learned by analogy.
%R ML-TR-2
%D 8/85
%T Explanation-Based Generalization: A Unifying View
%A T.M. Mitchell
%A R.M. Keller
%A S.T. Kedar-Cabelli
%X The problem of formulating general concepts from specific training
examples has long been a major focus of machine learning research.
While most previous research has focused on empirical methods for
generalizing from a large number of training examples using no
domain-specific knowledge, in the past few years new methods have been
developed for applying domain-specific knowledge to formulate valid
generalizations from single training examples. The characteristic
common to these methods is that their ability to generalize from a
single example follows from their ability to explain why the training
example is a member of the concept being learned. This paper
proposed a general, domain-independent mechanism, called EBG, that
unifies previous approaches to explanation-based generalization. The
EBG method is illustrated in the context of several example problems,
and used to contrast several existing systems for explanation-based
generalization. The perspective on explanation-based generalization
afforded by this general method is also used to identify open research
problems in this area.
%R RC-5882
%D February 1976
%A John Thomas
%T A Method of Studying Natural Language Dialogue
%I IBM Watson Research Center, User Interface Institute
%K AI02
%R RC-10823
%D November 1984
%A John Thomas:
%T Artificial Intelligence and Human Factors.
%I IBM Watson Research Center, User Interface Institute
%K AI08
%A Carbonell, Jaime
%T Derivational analogy: a theory of reconstructive problem solving
and
expertise acquisition.
%I Carnegie-Mellon University. Department of Computer Science.
%R CMU-CS-85-115.
%D 1985.
%K Case-based reasoning.
%A Kahn, Gary
%A McDermott, John
%T MUD: a drilling fluids consultant
%I Carnegie-Mellon University. Department of Computer Science
%R CMU-CS-85-116
%D 1985
%K Diagnostic systems, Knowledge acquisition AI01 AA03 AA21
%A Doyle, Jon
%T Reasoned assumptions and Pareto optimality
%I Carnegie-Mellon University. Department of Computer Science
%R CMU-CS-85-121
%D 1985.
%K Economic theory Group decision making Inference rules
Non-monotonic reasoning AA11
%A David M. McKeown, Jr
%A Pane, John F
%T Alignment and connection of fragmented linear features in aerial
imagery
%I Carnegie-Mellon University. Department of Computer Science
%R CMU-CS-85-122
%D 1985
%K Cultural features Feature extraction Image segmentation
Region interpolation Spline approximation AI06
%A Dill, David
%A Clarke, Edmund
%T Automatic verification of asynchronous circuits using temporal
logic
%I Carnegie-Mellon University. Department of Computer Science
%R CMU-CS-85-125
%D 1985
%K Circuit design
Timing constraints AA04 AI11
%A Lehr, Theodore
%T The implementation of a production system machine
%I Carnegie-Mellon University. Department of Computer Science
%R CMU-CS-85-126
%D 1985
%K Computer architecture OPS5 Performance improvement Production systems
RISCF Rete algorithm AI01
%A Minton, Steven
%T A game-playing program that learns by analyzing examples
%I Carnegie-Mellon University. Department of Computer Science
%R CMU-CS-85-130
%D 1985
%K Concept acquisition
Constraint based generalization
Forcing configurations
Learning from examples
Machine learning
Tactical combinations
Winning combinations
AI04 AA17
%A Fox, Mark
%A Wright, J. Mark
%A Adam, David
%T Experiences with SRL: an analysis of a frame-based knowledge
representation
%I Carnegie-Mellon University. Robotics Institute
%R CMU-RI-TR-85-10
%D 1985
%K Knowledge representation languages
%A Smith, Stephen
%A Ow, Peng Si
%T The use of multiple problem decompositions in time constrained
planning tasks
%I Carnegie-Mellon University. Robotics Institute
%R CMU-RI-TR-85-11
%D 1985
%K Job shop scheduling
%K Multi-agent planning systems
%K Resource allocation AI10
%A Brost, Randy
%T Planning robot grasping motions in the presence of uncertainty
%I Carnegie-Mellon University. Robotics Institute
%R CMU-RI-TR-85-12
%D 1985
%K Manipulators AI07 O04 AI09
%A Darlington,
%A Field, A.
%A Pull, H.
%T The unification of functional and logic languages
%I Imperial College of Science and Technology. Department of
Computing
%R Research report DOC 85/3
%D 1985
%K Functional programming
Reduction
Resolution AI10
%A Gregory, Steve
%A Neely, Rob
%A Ringwood, Graem
%T Parlog for specification, verification and simulation
%I Imperial College of Science and Technology. Department of
Computing
%R Research report DOC 85/7
%D 1985
%K PARLOG AI10 H03
%A Saint-Dizier, Patrick
%T On syntax and semantics of adjective phrases in logic
programming
%I Institut National de Recherche en Informatique et en Automatique
(INRIA)
%R Rapport de recherche 381
%D 1985
%K AI10
%A Deransart, Pierre
%A Maluszynski, Jan
%T Relating logic programs and attribute grammars
%I Institut National de Recherche en Informatique et en Automatique
(INRIA)
%R Rapport de recherche 393
%D 1985
%K Attribute dependency scheme Data flow analysis Logic programming AI10
%A Gazdar, Gerald
%A Pullum, Geoffrey K
%T Computationally relevant properties of natural languages and their
grammars
%I Stanford University. Center for the Study of Language and
Information
%R CSLI-85-24
%D 1985
%P 45
%K AI02
%A Fagin, Ronald
%A Vardi, Moshe
%T An internal semantics for modal logic: preliminary report
%I Stanford University. Center for the Study of Language and
Information
%R CSLI-85-25
%D 1985
%P 24p
%K AI10
%A Barwise, Jon
%T The situation in logic - III: simulation, sets and the axiom of
foundation
%I Stanford University. Center for the Study of Language and
Information
%R CSLI-85-26
%D 1985
%A van Benthem, Johan
%T Semantic automata
%I Stanford University. Center for the Study of Language and
Information
%R CSLI-85-27
%D 1985
%A Sells, Peter
%T Restrictive and non-restrictive modification
%I Stanford University. Center for the Study of Language and
Information
%R CSLI-85-28
%D 1985
%A Abadi, Martin
%A Manna, Zohar
%T Nonclausal temporal deduction
%I Stanford University. Department of Computer Science
%R STAN-CS-85-1056
%D 1985
%P 17p
%K Nonclausal resolution Propositional temporal logic
AI10 AI11
%A Mason, Ian A
%A Talcott, Carolyn L
%T Memories of S-expressions: proving properties of Lisp-like
programs that destructively alter memory
%I Stanford University. Department of Computer Science
%R STAN-CS-85-1057
%D 1985
%K Computations over memory structures Correctness proofs
Robson copying algorithm AI11 AA08
%A Taubenfeld, G
%A Francez, N
%T Proof rules for communication abstractions
%I TECHNION - Israel Institute of Technology. Department of Computer
Science
%R Technical report 332
%D 1984
%K Concurrent programming Deadlock Invariants Program verification
%K Scripts AA08
%A Shmueli, O
%A Tsur, S
%A Zfira, H
%T Rule supporting in PROLOG
%I TECHNION - Israel Institute of Technology. Department of Computer
Science
%R Technical report 337
%D 1984
%K T02
%A Shapiro, Ehud
%T A subset of Concurrent Prolog and its interpreter
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS83-06
%D 1983
%K T02 H03
%X "This is a revised version of technical report TR-003,
ICOT-Institute
for New Generation Computing Technology.";
%A Shapiro, Ehud
%A Takeuchi, Akikazu
%T Object oriented programming in Concurrent Prolog
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS83-08
%D 1983
%K H03 T02
%A Harel, David
%A Peleg, David
%T Process logic with regular formulas
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS83-11
%D 1983
%A Hellerstein, L
%A Shapiro, Ehud Y
%T Implementing parallel algorithms in Concurrent Prolog
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS83-12
%D 1983
%K T02 H03
%X Summary/draft, August 1983
%A Manna, Zohar
%A Pnueli, Amir
%T How to cook a temporal proof system for your pet language
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS83-13
%D 1983
%K AA08 AI11
%A Harel, David
%A Peleg, David
%T On static logics, dynamic logics and complexity classes
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS83-15
%D 1983
%K AI11
%A Feldman, Yishai A
%T A decidable propositional probabilistic dynamic logic
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS83-18
%D 1983
%K AI11
%A Barringer, Howard
%A Kuiper, Ruurd
%A Pnueli, Amir
%T Now you may compose temporal logic specifications
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS84-09
%D 1984
%K AI11
%A Shapiro, Ehud Y
%T The Bagel: a systolic Concurrent Prolog machine (lecture notes)
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS84-10
%D 1984
%K H03 T02
%A Peleg, David
%T Concurrent dynamic logic
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS84-14
%D 1984
%K T02 H03
%A Mierowsky, Colin
%T Design and implementation of flat Concurrent Prolog
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS84-21
%D 1984
%K H03 T02
%X Thesis (M.S.)
%A Bloch, Charlene
%T Source-to-source transformations of logic programs
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS84-22
%D 1984
%K AI10
%X Thesis (M.S.)
%A Viner, Omri
%T Distributed constraint propagation
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS84-24
%D 1984
%K H03
%X Thesis
%A Peleg, David
%T Concurrent program schemes and their logics
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS84-25
%D 1984
%K H03 T02
%A Lichtenstein, Orna
%A Pnueli, Amir
%T Checking that finite state concurrent programs satisfy their
linear specification
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS84-26
%D 1984
%K AA08
%A Nygate, Yossi
%T Python: a bridge expert on squeezes
%I Weizmann Institute of Science. Department of Applied Mathematics
%R CS84-27
%D 1984
%A Nixon, I. M.
%T I.F.: an Idiomatic Floorplanner
%I University of Edinburgh. Department of Computer Science
%R CSR-170-84
%D 1984
%K VLSI AA04
%A Sannella, Donald
%A Tarlecki, Andrzej
%T On observational equivalence and algebraic specification
%I University of Edinburgh. Department of Computer Science
%R CSR-172-84
%D 1984
%A Prasad, K. V. S
%T Specification and proof of a simple fault tolerant system in CCS
%I University of Edinburgh. Department of Computer Science
$R CSR-178-84
%D 1984
%K AA08 AI11
%A Blake, Andrew
%T Inferring surface shape by specular stereo
%I University of Edinburgh. Department of Computer Science
%R CSR-179-84
%D 1984
%K AI06
%A Dolan, Charles
%T Memory based processing for cross contextual reasoning: reminding
and
analogy using thematic structures
%I University of California, Los Angeles. Computer Science
Department
%R CSD-850010
%D 1985
%X Thesis (M.S.)
%A Hooper, Richard
%T An application of knowledge-based systems to electronic
computer-aided
engineering, design, and manufacturing data base transport
%I University of California, Los Angeles. Computer Science
Department
%R CSD-850011
%D 1985
%K AA05 AA04
%X Thesis (Ph.D.)
%A Rendell, Larry
%T Induction, of and by probability
%I University of Illinois, Urbana-Champaign. Department of Computer
Science
%R UIUCDCS-R-85-1209
%D 1985
%K Conceptual clustering Inductive inference AI04
Noise management Probabilistic learning systems
%A Rendell, Larry
%T Genetic plans and the probabilistic learning system: synthesis and
results
%I University of Illinois, Urbana-Champaign. Department of Computer
Science
%R UIUCDCS-R-85-1217
%D 1985
%K Conceptual clustering AI12 AI04
%A Anderson, James W.
%T Portable Standard LISP on the Cray
%I Los Alamos National Laboratory
%R LA-UR-84-4049
%D 1984
%K T01 H04 PSL
%A Arnon, Dennis S.
%T Supercomputers and symbolic computation
%I Purdue University. Department of Computer Sciences
%R CSD-TR-481
%D 1984
%K AI14 H04
%A J. Schwartz
%T A Survey of Program Proof Technology
%I New York University, Courant Institute, Department of Computer
Sciences
%D SEP 1978
%R 001
%K AA08 AI11
%A S. Stolfo
%A M. Harrison
%T Automatic Discovery of Heuristics for Non-Deterministic Programs
%D JAN 1979
%I New York University, Courant Institute, Department of Computer
Sciences
%R 007
%K AI04 AI03
%A M. Sharir
%T Algorithm Derivation by Transformations
%D OCT 1979
%I New York University, Courant Institute, Department of Computer
Sciences
%R 021
%K AA08
%A A. Walker
%T Syllog: A Knowledge Based Data Management Systems
%D JUN 1981
%I New York University, Courant Institute, Department of Computer
Sciences
%R 034
Sciences
%K AA09
%A J. Schwartz
%A M. Sharir
%T On the Piano-Movers Problem, I. Case of A Two Dimensional Rigid
Polygonal Body Moving Amidst Polygonal Barriers
%D OCT 1981
%I New York University, Courant Institute, Department of Computer
Sciences
%R 039 R1
Sciences
%K AI07
%A J. T. Schwartz
%A M. Sharir
%T On the Piano Movers Problem, II General Techniques for Computing
Topologic Properties of Real Algebraic Manifolds
%D FEB 1982
%R 041 R2
%I New York University, Courant Institute, Department of Computer
Sciences
%K AI07
%A J. Schwartz
%A M. Sharir
%T On the Piano Movers Problem III Coordinating the Motion of Several
Independent Bodies: The Special Bodies Moving Amidst Polygonal Bariers
%D SEP 1982
%R 052 r3
%I New York University, Courant Institute, Department of Computer
Sciences
%K AI07
%A C. O'Dunlaing
%A C. Yap
%T The Voronoi Diagram Method of Motion-Planning: I. The Case of a Disc
%D MAR 1982
%R 053 R4
%I New York University, Courant Institute, Department of Computer
Sciences
%K AI07
%A M. Sharir
%A E. Azriel-Sheffi
%T On the Piano Movers Problem IV Various Decomposable Two-Dimensional
Motion Plannings Problems
%D FEB 1983
%I New York University, Courant Institute, Department of Computer
Sciences
%R 058 R6
%K AI07
%A J. Schwartz
%T Structured Light Sensors for 3-D Robot Vision
%D MAR 1983
%R 065 R8
%I New York University, Courant Institute, Department of Computer
Sciences
%K AI06 AI07
%A C. Yap
%T Complexity of Motion Coordination
%R R12
%I New York University, Courant Institute, Department of Computer
Sciences
%K AI07
%A J. Schwartz
%A M. Sharir
%T On the Piano Movers Problem: V. The Case of a Rod Moving in
Three Dimensional Space Amidst Polyhedral Obstacles
%R 083 R13
%I New York University, Courant Institute, Department of Computer
Sciences
%D JUL 1983
%K AI07
%A R. Cole
%A C. Yap
%T Shape from Probing
%R 104 R15
%I New York University, Courant Institute, Department of Computer
Sciences
%D OCT 1983
%K AI07 AI06
%A J. Schwartz
%A M. Sharir
%T Some Remarks on Robot Vision
%R 119 R25
%I New York University, Courant Institute, Department of Computer
Sciences
%D APR 1984
%K AI07 AI006
%A C. Bastuscheck
%A J. Schwartz
%T Preliminary Implementation of a Ratio Depth Sensor
%R 124 R28
%I New York University, Courant Institute, Department of Computer
Sciences
%D JUN 1984
------------------------------
End of AIList Digest
********************
