Copy Link
Add to Bookmark
Report
AIList Digest Volume 4 Issue 202
AIList Digest Monday, 29 Sep 1986 Volume 4 : Issue 202
Today's Topics:
Bibliography - Recent Reports
----------------------------------------------------------------------
Date: WED, 20 apr 86 17:02:23 CDT
From: E1AR0002%SMUVM1.BITNET@WISCVM.WISC.EDU
Subject: Recent Reports
%A Ru-qian Lu
%T Expert Union: United Service of Distributed Expert Systems
%R 85-3
%I University of Minnesota-Duluth
%C Duluth, Minnesota
%D June, 1985
%K H03 AI01
%X A scheme for connecting expert systems in a network called an {\nit
expert union} is described. Consultation scheduling algorithms used to
select the appropriate expert(s) to solve problems are proposed, as
are strategies for resolving contradictions.
%A J. C. F. M. Neves
%A G. F. Luger
%A L. F. Amaral
%T Integrating a User's Knowledge into a Knowledge Base Using a Logic
Based Representation
%I University of New Mexico
%R CS85-2
%K AA08 AI10
%A J. C. F. M. Neves
%A G. F. Luger
%T An Automated Reasoning System for Presupposition Analysis
%I University of New Mexico
%R CS85-3
%K AI16
%A J. C. F. M. Neves
%A G. F. Luger
%A J. M. Carvalho
%T A Formalism for Views in a Logic Data Base
%I University of New Mexico
%R CS85-4
%K AA08
%A Franz Winkler
%T A Note on Improving the Complexity of the Knuth-Bendix Completion
Algorithm
%I University of Delaware
%R 85-04
%K AI14
%A Claudio Gutierrez
%T An Integrated Office Environment Under the AI Paradigm
%I University of Delaware
%R 86-03
%K AA06
%A Amir M. Razi
%T An Empirical Study of Robust Natural Language Processing
%I University of Delaware
%R 86-08
%K AI02
%A John T. Lund
%T Multiple Cause Identification in Diagnostic Problem Solving
%I University of Delaware
%R 86-11
%K AA05 AA21
%A D. Nau
%A T.C. Chang
%T Hierarchical Representation of Problem-Solving Knowledge in a Frame-Based
Process Planning System
%I Production Automation Project, University of Rochester
%R TM-50
%C Rochester, New York
%K AA26
%T INEXACT REASONING IN PROLOG-BASED EXPERT SYSTEMS
%A Koenraad G. Lecot
%R CSD-860053
%I University of California, Los Angeles
%K AI01 O04 T02
%$ 13.75
%X Expert systems are only worthy of their name if they can cope in a
consistent and natural way with the uncertainty and vagueness that is
inherent to real world expertise. This thesis explores the current
methodologies, both in the light of their acceptabiity and of their
implementation in the logic programming language Prolog. We treat in depth
the subjective Bayesian approach to inexact reasoning and describe a
meta-level implementation in Prolog. This probabilistic method is compared
with an alternative theory of belief used in Mycin. We describe an
implementation of Mycin's consultation phase. We argue further that the
theory of fuzzy logic is more adequate to describe the uncertainty and
vagueness of real world situations. Fuzzy logic is put in contrast with
the probabilistic approaches and an implementation strategy is described.
%T DISTRIBUTED DIAGNOSIS IN CAUSAL MODELS WITH CONTINUOUS VARIABLES
%A Judea Pearl
%R CSD-860051
%I University of California, Los Angeles
%$ 1.50
%K O04 H03 AA21
%X We consider causal models in which the variables form a linearly coupled
hierarchy, and are subject to Gaussian sources of noise. We show that if
the number of circuits in the hierarchy is small, the impact of each new
piece of evidence can be viewed as a perturbation that propagates through a
network of processors (one per variable) by local communication. This mode
of diagnosis admits flexible control strategies and facilitates the
generation of intuitively meaningful explanations.
%T RELAXATION PROBLEM SOLVING
(with input to Chinese input problem)
%A Kam Pui Chow
%I University of California, Los Angeles
%R CSD-860058
%$ 12.00
%K AI02
%X Two fundamental problem solving techniques are introduced to help automate
the use of relaxation: multilevel frameworks and constraint generation.
They are closely related to iterative relaxation and subproblem relaxation.
.sp 1
In multilevel problem solving, the set of constraints is partitioned
vertically into different levels. Lower level constraints generate
possible solutions while higher level constraints prune the solutions to
reduce the combinatorial explosion. Subproblem relaxation at first relaxes
the high level constraints; the solution is then improved by strengthening
the relaxed constraints.
.sp 1
The constraint generation technique uses iterative relaxation to generate a
set of constraints from a given model. This set of constraints with a
constraint interpreter form an expert system. This is an improvement over
most existing expert systems which require experts to write down their
expertise in rules.
.sp 1
These principles are illustrated by applying them to the Chinese input
problem, which is to transform a phonetic spelling, without word breaks, of
a Chinese sentence into the corresponding Chinese characters. Three
fundamental issues are studied: segmentation, homophone analysis, and
dictionary organization. The problem is partitioned into the following
levels: phonetic spelling, word, and grammar. The corresponding
constraints are legal spellings, legal words, and legal syntactic
structures. Constraints for syntactic structure are generated from a
Chinese grammar.
%T RELAXATION PROCESSES: THEORY, CASE STUDIES AND APPLICATIONS
%A Ching-Tsun Chou
%R CSD-860057
%$ 6.25
%I University of California, Los Angeles
%K O02 T02 AA08
%X Relaxation is a powerful problem-solving paradigm in coping with problems
specified using constraints. In this Thesis we present a study of the
nature of relaxation processes. We begin with identifying certain typical
problems solvable by relaxation. Motivated by these concrete examples, we
develop a formal theory of relaxation processes and design the General
Relaxation Semi-Algorithm for solving general Relaxation Problems. To
strengthen the theory, we do case studies on two relaxation-solvable
problems: the Shortest-Path Problem and Prefix Inequalities. The principal
results of these studies are polynomial-time algorithms for both problems.
The practical usefulness of relaxation is demonstrated by implementing a
program called TYPEINF which employs relaxation techniques to
automatically infer types for Prolog programs. Finally we indicate some
possible directions of future research.
%A J. R. Endsor
%A A. Dickinson
%A R. L. Blumenthal
%T Describe - An Explanation Facility for an Object Based System
%I Carnegie Mellon Computer Science Department
%D DEC 1985
%K AI01 O01
%A Kai-Fu Lee
%T Incremental Network Generation in Template-Based Word Recognition
%I Carnegie Mellon Computer Science Department
%D DEC 1985
%K AI05
%A J. Quinlan
%T A Comparative Analysis of Computer Architectures for Production
System Machines
%I Carnegie Mellon Computer Science Department
%D MAY 1985
%K AI01 H03 OPS5
%A M. Boggs
%A J. Carbonell
%A M. Kee
%A I. Monarch
%T Dypar-I: Tutorial and Reference Manual
%I Carnegie Mellon Computer Science Department
%D DEC 1985
%K AI01 AI02 Franz Lisp
%A Paola Giannini
%T Type Checking and Type Deduction Techniques for Polymorphic Programming
Languages
%I Carnegie Mellon Computer Science Department
%D DEC 1985
%K O02 lambda-calculus let construct
%A M. Dyer
%A M. Flowers
%A S. Muchnick
%T Lisp/85 User's Manual
%I University of Kansas, Computer Science Department
%R 77-4
%K T01
%A M. Flowers
%A M. DYer
%A S. Muchnick
%T LISP/85 Implementation Report
%I University of Kansas, Computer Science Department
%R 78-1
%K T01
%A N. Jones
%A S. Muchnick
%T Flow Analysis and Optimization of LISP-like Structures
%I University of Kansas, Computer Science Department
%R 78-2
%K T01
%A U. Pleban
%T The Standard Semantics of a Subset of SCHEME, A Dialect of LISP
%I University of Kansas, Computer Science Department
%R 79-3
%K T01 O02
%A S. Muchnick
%A U. Pleban
%T A Semantic Comparison of LISP and SCHEME
%I University of Kansas, Computer Science Department
%R 80-3
%K T01 O02
%A M. Jones
%T The PEGO Acquisition System Implementaiton Report
%I University of Kansas, Computer Science Department
%R 80-4
%A Gary Borchardt
%A Z. Bavel
%T CLIP, Computer Language for Idea Processing
%I University of Kansas, Computer Science Department
%R 81-4
%A Marek Holynski
%A Brian R. Gardner
%A Rafail Ostrovsky
%T Toward an Intelligent Computer Graphics System
%I Boston University, Computer Science Department
%R BUCS Tech Report #86-003
%D JAN 1986
%K T01 AA16
%A Joyce Friedman
%A Carol Neidle
%T Phonological Analysis for French Dictation: Preliminaries to an Intelligent
Tutoring System
%I Boston University, Computer Science Department
%R BUCS Tech Report #86-004
%D APR 1986
%K AI02 AA07
%A Pawel Urzyczyn
%T Logics of Programs with Boolean Memory
%I Boston University, Computer Science Department
%R BUCS Tech Report #86-006
%D APR 1986
%K AI16
%A Chua-Huang
%A Christian Lengauer
%T The Derivation of Systolic Implementatons of Programs
%R TR-86-10
%I Department of Computer Sciences, University of Texas at Austin
%D APR 1986
%K AA08 AA04 H03 H02
%A E. Allen Emerson
%A Chin-Laung Lei
%T Model Checking in the Propositional Mu-Calculus
%R TR-86-06
%I Department of Computer Sciences, University of Texas at Austin
%D FEB 1986
%K O02 AA08
%A R. D. Lins
%T On the Efficiency of Categorical Combinators as a Rewriting System
%D NOV 1985
%R No 34
%I University of Kent at Canterbury, Computing Laboratory
%K AI11 AI14
%A R. D. Lints
%T A Graph Reduction Machine for Execution of Categorical Combinators
%D NOV 1985
%R No 36
%I University of Kent at Canterbury, Computing Laboratory
%A S. J. Thompson
%T Proving Properties of Functions Defined on Lawful Types
%D MAY 1986
%R No 37
%I University of Kent at Canterbury, Computing Laboratory
%K AA08 AI11
%A V. A. Saraswat
%T Problems with Concurrent Prolog
%D JAN 1986
%I Carnegie Mellon University, Department of Computer Science
%K T02 H03
%A K. Shikano
%T Text-Independent Speaker Recognition Expertiments using Codebooks in Vector
quantization
%D JAN 1986
%I Carnegie Mellon University
%K AI05
%A S. Nakagawa
%T Speaker Independent Phoneme Recognition in Continuous Speech by
a Statistical Method and a Stochastic Dynamic Time Warping Method
%D JAN 1986
%I Carnegie Mellon University
%K AI05
%A F. Hau
%T Two Designs of Functional Units for VLSI Based Chess Machines
%D JAN 1986
%I Carnegie Mellon University
%K AA17 H03
%X Brute force chess automata searching 8 piles (4 full moves) or deeper have
been dominating the computer Chess scene in recent years and have reached
master level performance. One intereting question is whether 3 or 4 additional
piles couples with an improved evaluation scheme will bring forth world
championship level performance. Assuming an optimistic branching ratio of 5,
speedup of at least one hundred fold over the best current chess automaton
would be necessary to reach the 11 or 12 piles per move range.
%A Y. Iwasaki
%A H. A. Simon
%T Theories of Causual Ordering: Reply to de Kleer and Brown
%D FEB 1986
%I Carnegie Mellon University
%K Causality in Device Behavior AA04
%A H. Saito
%A M. Tomita
%T On Automatic Composition of Stereotypic Documents in Foreign Languages
%D DEC 1985
%I Carnegie Mellon University
%K AI02
%A T. Imielinski
%T Query Processing in Deductive Databases with Incomplete Information
%R DCS-TR-177
%I Rutgers University, Laboratory for Computer Science Research
%K AA09 AI10 Horn Clauses Skolem functions
%A T. Imielinski
%T Abstraction in Query Processing
%R DCS-TR-178
%I Rutgers University, Laboratory for Computer Science Research
%K AA09 AI11
%A T. Imielinski
%T Results on Translating Defaults to Circumscription
%R DCS-TR-179
%I Rutgers University, Laboratory for Computer Science Research
%K AA09
%A T. Imielinski
%T Transforming Logical Rules by Relational Algebra
%R DCS-TR-180
%I Rutgers University, Laboratory for Computer Science Research
%K AA09 AI10 Horn clauses
%A T. Imeielinski
%T Automated Deduction in Databases with Incomplete Information
%R DCS-TR-181
%I Rutgers University, Laboratory for Computer Science Research
%K AA09
%A B. A. Nadel
%T Representationi-Selection for Constraint Satisfaction Problems: A Case
Study Using n-queens
%R DCS-TR-182
%I Rutgers University, Laboratory for Computer Science Research
%K AI03 AA17
%A B. A. Nadel
%T Theory-Based Search Order Selection for Constraint Satisfaction
Problems
%R DCS-TR-183
%I Rutgers University, Laboratory for Computer Science Research
%K AI03
%A C. V. Srinivasan
%T Problems, Challenges and Opportunities in Naval Operational Planning
%R DCS-TR-187
%I Rutgers University, Laboratory for Computer Science Research
%K AI09 AA18
%A M. A. Bienkowski
%T An Example of Structured Explanation Generation
%I Princeton University Computer ScienceDepartment
%D NOV 1985
%K O01
%A Bruce G. Buchanan
%T Some Approaches to Knowledge Acquisition
%I Stanford University Computer Science Department
%R STAN-CS-85-1076
%D JUL 1985
%$ $5.00
%K AI16
%A John McCarthy
%T Applications of Circumscription to Formalizing Common Sense Knowledge
%I Stanford University Computer Science Department
%R STAN-CS-85-1077
%D SEP 1985
%$ $5.00
%K AI15
%A Stuart Russell, Esq.
%T The Compleat Guide to MRS
%I Stanford University Computer Science Department
%R STAN-CS-85-1080
%D JUN 1985
%$ $15.00
%K AI16
%A Jeffrey S. Rosenschein
%T Rational Interaction: Cooperation among Intelligent Agents
%I Stanford University Computer Science Department
%R STAN-CS-85-1081
%D OCT 1985
%$ $15.00
%K AI16
%A Allen Van Gelder
%T A Message Passing Framework for Logical Query Evaluation
%I Stanford University Computer Science Department
%R STAN-CS-85-1088
%D DEC 1985
%$ $5.00
%K AI10 Horn Clauses relational data bases H03 AA09 acyclic database schemas
%A Jeffrey D. Ullman
%A Allen Van Gelder
%T Parallel Complexity of Logical Query Programs
%I Stanford University Computer Science Department
%R STAN-CS-85-1089
%D DEC 1985
%$ $5.00
%K AI10 H03 AA09
%A Kaizhi Yue
%T Constructing and Analyzing Specifications of Real World Systems
%I Stanford University Computer Science Department
%R STAN-CS-86-1090
%D SEP 1985
%K AI01 AA08
%X available in microfilm only
%A Li-Min Fu
%T Learning Object-Level and Metal-Level Knowledge in Expert Systems
%I Stanford University Computer Science Department
%R STAN-CS-86-1091
%D NOV 1985
%$ $15.00
%K jaundice AI04 AI01 AA01 condenser
%A Devika Subramanian
%A Bruce G. Buchanan
%T A General Reading List for Artificial Intelligence
%I Stanford University Computer Science Department
%R STAN-CS-86-1093
%D DEC 1985
%$ 10.00
%K AT21
%X bibliography for students studying for AI qualifying exam at Stanford
%A Bruce G. Buchanan
%T Expert Systems: Working Systems and the Research Literature
%I Stanford University Computer Science Department
%R STAN-CS-86-1094
%D DEC 1985
%$ 10.00
%K AT21 AI01
%A Jiawei Han
%T Pattern-Based and Knowledge-Directed Query Compilation for Recursive Data
Bases
%I The University of Wisconsin-Madison Computer Sciences Department
%R TR 629
%D JAN 1986
%$ 5.70
%K AA09 AI01 AI09
%X Abstract: Expert database systems (EDS's) comprise an interesting class of
computer systems which represent a confluence of research in artificial
intelligence, logic, and database management systems. They involve
knowledge-directed processing of large volumes of shared information and
constitute a new generation of knowledge management systems.
Our research is on the deductive augmentation of relational database
systems, especially on the efficient realization of recursion. We study
the compilation and processing of recursive rules in relational database
systems, investigating two related approaches: pattern-based recursive rule
compilation and knowledge-directed recursive rule compilation and planning.
Pattern-based recursive rule compilation is a method of compiling and processing
recursive rules based on their recursion patterns. We classify recursive rules
according to their processing complexity and develop three kinds of algorithms
for compiling and processing different classes of recursive rules: transitive
closure algorithms, SLSR wavefront algorithms, and stack-directed compilation
algorithms. These algorithms, though distinct, are closely related. The more
complex algorithms are generalizations of the simpler ones, and all apply the
heuristics of performing selection first and utilizing previous processing
results (wavefronts) in reducing query processing costs. The algorithms are
formally described and verified, and important aspects of their behavior are
analyzed and experimentally tested.
To further improve search efficiency, a knowledge-directed recursive rule
compilation and planning technique is introduced. We analyze the issues raised
for the compilation of recursive rules and propose to deal with them by
incorporating functional definitions, domain-specific knowledge, query
constants, and a planning technique. A prototype knowledge-directed relational
planner, RELPLAN, which maintains a high level user view and query interface,
has been designed and implemented, and experiments with the prototype are
reported and illustrated.
%A A. P. Anantharman
%A Sandip Dasgupta
%A Tarak S. goradia
%A Prasanna Kaikini
%A Chun-Pui Ng
%A Murali Subbarao
%A G. A. Venkatesh
%A Sudhanshu Verma
%A Kumar A. Vora
%T Experience with Crystal, Charlotte and Lynx
%I The University of Wisconsin-Madison Computer Sciences Department
%R TR 630
%D FEB 1986
%K H03 T02 Waltz constraint-propagation
%X Abstract: This paper describes the most recent implementations of
distributed algorithms at Wisconsin that use the Crystal multicomputer, the
Charlotte operating system, and the Lynx language. This environment is an
experimental testbed for design of such algorithms. Our report is meant to
show the range of applications that we have found reasonable in such an
environment and to give some of the flavor of the algorithms that have been
developed. We do not claim that the algorithms are the best possible for
these problems, although they have been designed with some care. In
several cases they are completely new or represent significant
modifications of existing algorithms. We present distributed
implementations of B trees, systolic arrays, prolog tree search, the
travelling salesman problem, incremental spanning trees, nearest-neighbor
search in k-d trees, and the Waltz constraint-propagation algorithm. Our
conclusion is that the environment, although only recently available, is
already a valuable resource and will continue to grow in importance in
developing new algorithms.
%A William J, Rapaport
%T SNePS Considered as a Fully Intensional Propositional
Semantic Network
%R TR 85-15
%I Univ. at Buffalo (SUNY), Dept. of Computer Science
%D October 1985
%K Semantic Network Processing System, syntax, semantics,
intensional knowledge representation system, cognitive
modeling, database management, pattern recognition, expert
systems, belief revision, computational linguistics
aa01 ai09 ai16
%O 46 pages
%X Price: $1.00 North America, $1.50 Other
%A William J. Rapaport
%T Logic and Artificial Intelligence
%R TR 85-16
%I University at Buffalo (SUNY), Dept. of Computer Science
%D November 1985
%K logic, propositional logic, predicate logic, belief systems AA16
%O 44 pages
%X Price: $1.00 North America, $1.50 Other
%A William J. Rapaport
%T Review of "Ethical Issues in the Use of Computers"
%R TR 85-17
%I University at Buffalo, Dept. of Computer Science
%D November 1985
%K computer ethics O06
%O 6 pages
%X Price: $1.00 North America, $1.50 Other
%A Radmilo M. Bozinovic
%T Recognition of Off-line Cursive Handwriting:
a Case of Multi-level Machine Perception
%I Univ. at Buffalo (SUNY), Dept. of Computer Science
%D March 1985
%R TR 85-01
%K Cursive script recognition, artificial intelligence,
computer vision, language perception, language understanding
%O 150 pages
%X Price: $2.00 North America, $3.00 other
%A R. Hookway
%T Verification of Abstract Types Whose Representation Share Storage
%D April 1980
%I Case Western Reserve University, Computer Engineering and Science Department
%R CES-80-02
%K AA09
%$ $2.00
%A G. Ernst
%A J. K. Vavlakha
%A W. F. Ogden
%T Verification of Programs with Procedure-Type Parameters
%I Case Western Reserve University, Computer Engineering and Science Department
%R CES-80-11
%D 1980
%K AA09
%$ $2.00
%A G. Ernst
%A F. T. Bradshaw
%A R. J. Hookway
%T A Note on Specifications of Concurrent Processes
%I Case Western Reserve University, Computer Engineering and Science Department
%R CES-81-01
%D FEB 1981
%K AA09
%$ $2.00
%A J. Franco
%T The Probabilistic Analysis of the Pure Literal Heuristic in Theorem
Proving
%I Case Western Reserve University, Computer Engineering and Science Department
%R CES-81-04
%D 1981
%K AI03 AI11
%$ $2.00
%A E. J. Branagan
%T An Interactive Theorem Prover Verification
%I Case Western Reserve University, Computer Engineering and Science Department
%R CES-81-09
%D AUG 1981
%K AI11
%$ $2.00
%A G. W. Ernst
%T A Method for verifying Concurrent Processes
%I Case Western Reserve University, Computer Engineering and Science Department
%R CES-82-01
%D FEB 1982
%K AA09
%$ $2.00
%A Chang-Sheng Yang
%T A Computer Intelligent System for Understanding Chinese Homonyms
%I Case Western Reserve University, Computer Engineering and Science Department
%R CES-83-10
%D AUG 1983
%K AI02
%$ $2.00
%A G. Ernst
%T Extensions to Methods for Learning Problem Solving Strategies
%I Case Western Reserve University, Computer Engineering and Science Department
%R CES-84-02
%D MAY 1984
%K AI04
%$ $2.00
%A R. J. Hookway
%T Analysis of Asynchronous Circuits Using Temporal Logic
%I Case Western Reserve University, Computer Engineering and Science Department
%R CES-84-07
%D JUL 1984
%K AA04
%$ $2.00
%A Sterling, Leon
%T Explaining Explanations Clearly
%I Case Western Reserve University, Computer Engineering and Science Department
%R CES-85-03
%D MAY 1985
%K O01
%$ $2.00
------------------------------
End of AIList Digest
********************
