Article View: mod.techreports
Article #4(none)
From: The devil himself
Date: Fri, 24 Jan 1986 07:07
Date: Fri, 24 Jan 1986 07:07
2358 lines
102850 bytes
102850 bytes
>From smu!leff Mon Jan 20 15:15:28 1986 remote from convex
Received: by convex (4.12/4.7)
id AA01284; Mon, 20 Jan 86 15:15:28 cst
Received: by csevax.smu (4.12/4.7)
id AA16599; Mon, 20 Jan 86 14:18:59 cst
Date: Mon, 20 Jan 86 14:18:59 cst
From: convex!smu!leff (Laurence Leff)
Message-Id: <8601202018.AA16599@csevax.smu>
To: ucbvax!post-techreports
Subject: Rutgers Tech reports
R U T G E R S U N I V E R S I T Y
Department of Computer Science
TECHNICAL REPORTS AND TECHNICAL MEMOS
* * *
CBM-TM-84
\4/80
\"An Experiment in Extracting Some Properties of Binary Relations"
\D. Nagel
\
\
\1/82
\A method of overlaying training instances generated from a database
in a graph representation is used to learn definitional information
about the relations in the database. An experiment is described where
algebraic properties of relations such as functionality and symmetry
are discovered in a simple family database using this method. Once
these properties are discovered the capability for making inferences
in the database is extended. The efficiency of answering queries may
be improved and new insights into the data may be developed.
\*
CBM-TM-85
\4/80
\"Some Considerations on Extracting Definitional Information about
Relations"
\D. Nagel
\
\
\1/82
\I. @u(Introduction)
Several of the current systems in Artificial Intelligence are
represented in binary relational databases and rely on the semantics
of relations as a source of knowledge for information retrieval.
Examples of these systems include those developed by Lindsay [5,6],
Raphael [10], Elliott [2], Brown [1], and Sridharan [11]. In these
systems inferences can be made from a set of properties specified for
each relation. Inferences can also be made from specified
associations between relations. One interesting aspect is the degree
to which making these inferences can be automated. Some methods are
proposed in this paper for using machine learning to extract
relational properties and recognize semantic ties between relations so
that this definitional information will not have to be prespecified.
In some cases these methods may not technically be categorized as
learning because they primarily involve summarization. It is also
difficult to pin down what is encompassed by semantics. However, this
paper discusses concepts of learning, and the presentation is directed
at capturing semantics.
Extracting definitional information or more broadly, learning
semantics of relations, provides a base for the study of interesting
databases. This could be done in a symbiotic system where the
interaction between the researcher and the system provides a means for
improving the performance of the system in general and
obtaining new insights in the scientific data. It could also be
coupled with a system for automatic theory formation. Presently,
applications using semantics of relations for making inferences have
been most successful in areas where properties and relationships are
well understood such as kinship relations.
\*
CBM-TM-86
\5/80
\"Representational Facilities of AIMDS: A Sampling"
\N.S. Sridharan
\
\
\1/82
\I. @u(Introduction)
The quest for fundamental and general mechanisms of intelligence,
especially problem solving and heuristic search techniques, that
guided early research in Artificial Intelligence has given way in the
last decade to the search for equally fundamental and general methods
for structuring and representing knowledge. This is the result of the
realization that a duality exists between knowledge and search:
Knowledge of the task domain can abbreviate search and search thru a
problem space can yield new knowledge. AIMDS is one of the recently
developed systems which permits experimentation with knowledge
representation in the course of building an AI program.
\*
CBM-TM-87
\6/80
\"The Role of Object Knowledge in Human Planning"
\C.F. Schmidt
\
\
\1/82
\AI research on planning provides an important reference point from
which the cognitive psychologist can build an understanding of human
planning. It is argued that the human planning context differs from
this reference point due to the incomplete knowledge that persons
typically possess about the situation within which the plan will be
executed. Various types of general functional knowledge about objects
are then defined. This knowledge serves as a source of default
assumptions for use in the planning process, and thus allows planning
to continue despite the absence of complete knowledge of the planning
situation. However, such assumption-based expectations must be
tested. From this point of view, planning must also include a process
for a kind of hypothesis testing and plan revision. The implications
of this claim are briefly discussed.
\*
CBM-TM-88
\9/80
\"Initial Thoughts on Characterization of Expert Systems"
\S. Amarel
\
\
\1/82
\Expertise in a given domain is commonly characterized by skillful,
high performance, problem solving activity in the domain. An expert
solves problems in a domain more rapidly, more accurately, and with
less conscious deliberation about his plan of attack than a novice
does. An excellent discussion of general characteristics of expert
behavior appears in a recent article in @u(Science) by Larkin et al.
[1].
Expert behavior is equivalent to high performance problem solving
behavior in a specific domain. It requires: knowledge of the domain,
knowledge of problem solving schemas and methods, knowledge/experience
about solution of specific problems in the domain with given methods,
knowledge about special properties and regularities in the problem
space, and highly effective ways of @u(using) all these bodies of
knowledge in approaching the solution of new problems in the domain.
Essentially, expert problem solving requires the
conceptualization/formulation of a given problem within a framework
wherein knowledge is embodied in definitions of states, moves,
constraints, evaluation functions, etc. in such a way that solutions
are attained with very little search. In other words, an expert
problem solver works within a highly 'appropriate' problem
representation: he describes situations and problem types within
'appropriate'conceptual frameworks, he specifies problem
decompositions that minimize subproblem interactions, he often uses
hierarchies of abstractions in his planning, he uses 'macromoves'
where a novice would painstakingly have to piece together elementary
moves, and he has rules for early recognition of unpromising as well
as of promising developments. An expert problem solver behaves as if
the great variety of knowledge sources needed for his
solution-construction activities are available to him in a
@u(compiled) procedural form.
Usually, expertise in a domain requires @u(problem solving experience)
in the domain. One can be scholar in a domain, and not an expert--if
he does not know how to effectively @u(apply) domain knowledge to a
variety of specific situations. Also, expertise implies a certain
amount of robustness in performance-- which means that it is not
sufficient to know how to handle a few 'textbook' cases; it is
important to be able to handle a broad range of variations.
\*
CBM-TM-89
\3/81
\"Review of Characteristics of Current Expert Systems*"
\S. Amarel
\
\
\1/82
\This report does not cover all current work in the area of Expert
systems. It is intended to introduce a set of dimensions for
characterizing Expert systems and to describe some of the important
Expert systems that are now in existence (or are under active
development) in terms of these dimensions.
We have a dual purpose: (a) to illustrate via concrete examples the
dimensions that are being introduced, and (b) to show what is the
current state of the field from the perspective of this system of
dimensions.
We are using here ten main dimensions, and an optional eleventh called
@ux(Special Features), which provides added flexibility for the
presentation of relevant information about a system. Two of the main
dimensions, @ux(Performance) and @ux(Utility), are concerned with the
quality of the system's behavior and the impact of the system on the
domain of application and on AI. Another two dimensions are concerned
with the system's scope, its ability to handle situations that are
outside its area of major expertise, and its ability to improve: they
are called @u(Breadth, Intelligence, Robustness) and @u(Expertise
improvement ability). The remaining six dimensions are concerned with
the type of tasks performed by the system, its structure and its means
of interacting with users: they are called @u(Task type, Main Method,
Mode of Knowledge Representation, User Interface for main task,
Explanation facilities) and @u(Reasoning under Uncertainty).
The systems considered are DENDRAL, CASNET/GLAUCOMA, MACSYMA, MYCIN,
INTERNIST, PROSPECTOR and CRYSALIS.
*This report covers material which was prepared for inclusion in the
Chapter 'What are Expert Systems' (co-authored with Ron Brachman, Carl
Engelman, Robert Engelmore, Edward Feigenbaum and David Wilkins) of a
book on Expert Systems which is currently under preparation; the book
is based on the Rand Workshop on Expert Systems which took place in
San Diego, California on August 25-28, 1980.
\*
CBM-TM-90
\3/81
\"A Precedence Scheme for Selection and Explanation of Therapies"
\John Kastner
Sholom M. Weiss
\
\
\1/82
\A general scheme to aid in the selection of therapies is described. A
topological sorting procedure within a general production rule
representation is introduced. The procedure is used to choose among
competing therapies on the basis of precedence rules. This approach
has a degree of naturalness that lends itself to automatic explanation
of the choices made. A system has been implemented using this
approach to develop an expert system for planning therapies for
patients diagnosed as having ocular herpes simples. An abstracted
example of the system's output on an actual case is given.
\*
CBM-TM-91
\3/81
\"A System for Empherical Experimentation with Expert Knowledge
\ P. Politakis
S.M. Weiss
\
\
\1/82
\An approach to the acquisition of expert knowledge is presented based
on the comparison of dual sources of knowledge: expert-modeled rules
and cases with known conclusions. A system called SEEK has been
implemented to give to the expert interactive advice about rule
refinement. SEEK uses a simple frame model for expressing
expert-modeled rules. The advice takes the form of suggestions of
possible experiments in generalizing or specializing rules in the
model. This approach has proven particularly valuable in assisting
the expert in domains where two diagnoses are difficult to
distinguish. Examples are given from an expert consultation system
being developed for rheumatology.
\*
CBM-TM-92
(new)
\10/81
\Knowledge-Based Acquisition of Rules for Medical Diagnosis
\C. Kulikowski,
G. Drastal
\
\
\1/82\Medical consultation systems in the EXPERT framework contain rules
written under the guidance of expert physicians. We present a
methodology and preliminary implementation of a system which learns
compiled rule chains from positive case examples of a diagnostic class
and negative examples of alternative diagnostic classes. Rule
acquisition is guided by the constraints of physiological process
models represented in the system. Evaluation of the system is
proceeding in the area of glaucoma diagnosis, and an example of an
experiment in this domain is included.
\*
CBM-TM-93
\1/82
\AIMDS: Applications and Performance Enhancements
\N.S. Sridharan
\
\
\1/82
\AIMDS is a programming environment (language, editors, display drivers, file
system) in which several programs are being constructed for modeling
commonsense reasoning and legal argumentation. The main obstacle to realistic
applications in these and other areas is system performance when the knowledge
bases used are scaled up one or two orders of magnitude. The other obstacle
is user performance resulting from the complexity of constructing and debugging
large scale knowledge bases. This proposal argues that performance enhancement
of AIMDS as a system is needed and that the usual solutions of software tuning
have been exhausted and that new hardware ideas fitted to the characteristics
of the task need to be experimented with. We adopt as important constraints:
the requirement that existing programs should receive graded enhancement of
performance, maintaining continuity of application programs; that user programs
should not reflect changing machine configurations or architectures. Redesign
and recoding of AIMDS should provide the necessary opacity to the user.
With these constraints in mind, we suggest interim solutions and long-term
solutions. The interim solutions include: converting large-address space
personal Lisp machines with bit-mapped graphics; fast coding of low-level
functionalities via microprogramming. The long-term solutions include the
building and testing of multiprocessors. The long-term solutions open up
a number of rather difficult software and hardware research problems whose
solutions depend upon having good facilities to experiment in the search for
answers.
\*
CBM-TM-94
\9/82
\"The AIMDS Interactive Command-Parser"
\B. Lantz
\
\
\9/82
\Characters entered by the user are parsed immediately in order to provide
interactive services to the user while he is entering comands. Services
provided to the user include immediate verification of syntax, supplying the
user with information about the correct syntax and semantics of a command,
completion of long descriptive atom names, pretty printing the entered
command, and defining special functions for selected characters. The parser
accepts user defined grammars, thus providing a useful command parser for a
great variety of applications.
\*
CBM-TM-95
\9/82
\"The AIMDS On-Line Documentation Facility"
\B. Lantz
\
\
\9/82
\The documentation system for the AIMDS language is designed to be suitable
for both beginning and expert users, and to be capable of serving the needs
of a changing system such as AIMDS. The documentation must be quickly and
easily updatable, and the updated information should be available to, and
easily used by, a wide variety of users.
This paper is a short description of the documentation system for the
AIMDS language. It includes a discussion of the considerations taken during
the design of the documentation system, a description of the implemented
system, and instructions for using the system for other documentation tasks.
\*
CBM-TM-96
\9/82
\"Implementing Aimds on a Multiprocessor Machine. Some Considerations"
\J. Roach
N.S. Sridharan
\
\
\4/83
\As a possible long term solution for performanc enhancement of AIMDS,
a Lisp based multiprocessor system was proposed. Converting an
existing AI knowledge based system from the current uniprocessor
environment into a multiprocessor based regime is a largely unexplored
research question. This report discusses some of the issues raised by
such a proposal and attempts to evaluate some of the current models of
parallel processing in regards to implementing an AIMDS based system.
An extensive bibliography with commentary is included.
\*
CBM-TM-97
\1/82
\"Knowledge-Based Acquisition of Rule for Medical Diagnosis"
\George A. Drastal
Casimir A. Kulikowski
\11/82
\
\
\Medical consultation systems in the EXPERT framework contain rules written
under the guidance of expert physicians. We present a methodology and
preliminary implementation of a system that learns compiled rule chains
from positive case examples of a diagnostic class and negative examples
of alternative diagnostic classes. Rule acquisition is guided by the
constraints of physiological process models represented in the system.
Evaluation of the system is proceeding in the area of glaucoma diagnosis,
and an example of an experiment in this domain is included.
\*
CBM-TR-94
\5/81
Revised
\"A Guide to the Use of the EXPERT Consultation System"
\S. Weiss
K. Kern
C. Kulikowski
M. Uschold
\
\
\1/82
\EXPERT is a system for designing and applying consultation models.
An EXPERT model consists of hypotheses (conclusions), findings
(observations), and rules for logically relating findings to
hypotheses. Three phases of model development are outlined for users
of the system. These include: the design of a decision-making model,
compilation of the model, and consultation using the model. The
facilities of the system are described, and examples of models and
consultation sessions are presented.
\*
CBM-TR-107
\1/80
\"Description Languages and Learning Algorithms:
A Paradigm for Comparison"
\R. Banerji
T. Mitchell
\
\@u(Keywords:) Inductive inference, learning, generalization, description languages.
\
\1/82
\We propose and apply a framework for comparing various methods for
learning descriptions of classes of objects given a set of training
exemplars. Such systems may be usefully characterized in terms of
their descriptive languages, and the learning algorithms they employ.
The basis for our characterization and comparison is a
general-to-specific partial ordering over the description language,
which allows characterizing learning algorithms independent of the
description language with which they are associated. Two existing
learning systems are characterized within this framework, and
correspondences between them made clear.
\*
CBM-TR-108
(NOT ISSUED)
\"Plausible Inference in a Structured Concept Space"
\
\
\
\1/82
\
\*
CBM-TR-109
\5/80
\"The Role of World Knowledge in Planning"
\N.S. Sridharan
C.F. Schmidt
J.L. Goodson
\
\
\1/82
\Common-sense planning demands a rich variety of world knowledge. We
have examined here the view that world knowledge can be structured to
form the interface between a hierarchy of action types and a hierarchy
of types of objects. World knowledge forming this interface includes
not only the traditional statements about preconditions and outcomes
of actions, but also the normal states of objects participating in the
actions and normative actions associated with the objects.
Common-sense plans are decomposed into goal-directed, preparation, and
the normative components. This has heuristic value and may serve to
simplify the planning algorithm. The algorithm invokes world
knowledge for goal customization, action specification, computation of
preconditions and outcomes, object selection, and for setting up
subgoals.
\*
CBM-TR-110
\5/80
\"An Experimental Transformation of a Large Expert Knowledge-Base"
\R.N. Goldberg
S.M. Weiss
\
\
\1/82
\An experiment is described in which a significant part of the
INTERNIST knowledge base for diagnosis in internal medicine is
translated into an EXPERT model. INTERNIST employs the largest and
broadest knowledge base of all the medical consultation systems which
have been developed in recent years. EXPERT is a general system for
designing consultation models. The translated model shows reasonable
competence in the final diagnostic classification of 431 test cases.
There are differences in the internal representation and reasoning
strategies of the two systems. However, when a knowledge base has
been encoded in a relatively uniform manner, this experiment
demonstrates the feasibility of transfer of knowledge between
large-scale expert systems.
\*
CBM-TR-111
\6/80
\"A Process for Evaluating Tree-Consistency"
\J.L. Goodson
\
\
\1/82
\General knowledge about conceptual classes represented in a concept
hierarchy can provide a basis for various types of inferences about an
individual. However, the various sources of inference may not lead to
a consistent set of conclusions about the individual. This paper
provides a brief glimpse at how we represent beliefs about specific
individuals and conceptual knowledge, discusses some of the sources
of inference we have defined, and describes procedures and structures
that can be used to evaluate agreement among sources whose conclusions
can be viewed as advocating various values in a tree partition of
alternate values.
\*
CBM-TR-112
\9/80
\"A Methodology for the Construction of Natural
Language Front Ends for Medical Consultation Systems"
\V. Ciesielski
\
\
\1//82
\A methodology for constructing natural language front ends for
Associational Knowledge type (AK-type) medical consultation systems is
described. AK-type consultation systems use associational knowledge
of the form "if A and B and C then conclude D with a weight of w" to
perform diagnostic reasoning. It is shown that the knowledge needed
to "understand" patient description is not the associational knowledge
in the consultation system but rather knowledge of structural
relations and the way they are expressed in surface language. The two
main structural relations involved are: (1) ATTRIBUTE of OBJECT =
VALUE. Surface forms of this relation are variants and augmentations
of the template "The X of Y is V". (2) OBJECT have-component
COMPONENT. Surface forms of this relation are variants and
augmentations of the template "The X has/contains/includes Y". This
kind of knowledge can be represented in the
Attribute-Component/Structured Object (AC/SO) package which was
developed as part of this research. The AC/SO package is given a
definition of the @u(concept) "PATIENT" for a disease area and the
corresponding lexicon.
\*
CBM-TR-113
\9/80
\"Designing Consistent Knowledge Bases: An Knowledge Acquisition" Approach to Expert
\P. Politakis
\S. Weiss
\
\
\3/82
\This paper reports on an empirical evaluation approach to assist in
the acquisition of expert knowledge for high performance
knowledge-based consultation systems. A framework is provided by a
general consultation system EXPERT and a tabular scheme for acquiring
expert decision rules. Two levels of abstraction are identified in
the knowledge acquisition process: logical analysis of the tables and
expectation-driven analysis of the knowledge base. Possible ways of
recognizing redundancy and "gaps" in knowledge within a table are
illustrated. Tools are described which facilitate the recognition of
potential problems in the knowledge base. These include the
extraction of incorrectly diagnosed cases organized by their known
conclusions; the grouping of rules with a tabulation of their utility
on all cases; and the determination of the impact of rule changes on
all cases. Possible approaches to learning and modifying rules in the
knowledge base are described.
\*
CBM-TR-114
\9/80
\"Learning Problem-Solving Heuristics by Experimentation"
\T. Mitchell
P. Utgoff
R. Banerji
\
\
\1/82
\This paper concerns building heuristic problem solvers capable of
improving their performance through experience. Specifically, we
consider improving performance by learning domain-specific heuristics
for directing the problem solving search. Each heuristic
characterizes conditions under which a specific operator will be
useful in leading to problem solutions.
The discussion takes the form of a progress report on the design of a
computer program, called LEX, to acquire problem solving heuristics by
experimentation. LEX is designed to (1) propose practice problems,
(2) attempt to solve them, (3) analyze the steps it performed in
solving the problem, then (4) formulate domain-specific heuristics
designed to improve its performance on subsequent problems. The major
results reported here are an initial design for LEX in the domain of
symbolic integration, a hand trace illustrating its operation, and an
analysis of the successes and failures of this initial design.
\*
CBM-TR-115
\9/80
\"Plan Recognition and Revision: Understanding Another Actor" the Observed Actions of
\C.F. Schmidt
\
\1/82
\@u(Introduction)
In Heider's (l959) classic work in cognitive social psychology he
developed the claim that a naive or comonsense theory of social
causation underlies our understanding of the observed actions of
others. Heider arrived at this conclusion largely by carefully
considering the systematic ways in which linguistic terms that refer
to persons and actions are used. More recently philosophers,
linguists, logicians, and computer scientists in the area of
artificial intelligence have contributed to our understanding of the
relations between the concepts that we use to describe behavior from
an intentional point of view. This includes terms such as can,
believe, know, want, and the various verbs of action.
These investigations alert us to the structure of intentional terms
but tell us nothing about the processes that are involved in using
these intentional concepts to understand and describe the actions of
others. Process models of knowledge-directed cognitive tasks such as
action understanding can be constructed, evaluated, and tested if we
adapt the tools of AI research to this task.
\*
CBM-TR-116
\10/80
\"FOCUSER: A Strategic Interaction Paradigm for Language Acquisition"
\D. Smith
\
\
\1/82
\FOCUSER learns language: it acquires lexicon, syntax, and semantics
from a cooperative teacher using a strategic interaction paradigm.
The system uses knowledge of teaching/learning strategies to establish
and maintain the foci of the interaction. This paper presents several
focusing mechanisms and demonstrates the use of these mechanisms in a
teaching/learning environment.
\*
CBM-TR-117
\5/80
\The Need for Biases in Learning Generalizations"
\T.M. Mitchell
\
\
\1/82
\The ability to make an appropriate "inductive leap" when generalizing
from a small set of @u(training) instances is possible only under a
priori biases for choosing an appropriate generalization out of the
many possible. Understanding the origins and justification of such
biases is critical to further progress in the field of machine
learning. The notion of an UNbiased learner is defined, then the
notion of bias, its usefulness, and some classes of justifiable biases
are considered.
\*
CBM-TR-118
\2/81
\"Problems of Representation in Heuristic Problem Solving;
Related Issues in the Development of Expert Systems"
\S. Amarel
\
\
\1/82
\The problem of representation in problem solving is concerned with the
choice of formulation of a problem for a system which is organized in
accordance with a given problem solving schema. Key issues are: (a)
understanding the relationships between such a choice and the
efficiency with which the system can be expected to find a solution to
the problem; (b) finding ways of choosing an 'appropriate' problem
formulation -- from the point of view of minimizing the computational
effort needed to construct a solution; and (c) finding ways of
shifting from one problem formulation to another in a manner that
increases problem solving performance. Progress in this difficult
area has been stimulated in recent years by work on expert systems and
by related research on theory formation and expertise acquisition. In
this paper, a conceptual framework is presented for handling problem
representations. The grammatical specification of solutions for a
problem class plays an important role in this framework. A detailed
analysis of representational shifts in a specific class of problems --
the Tower of Hanoi problems -- is presented in terms of the proposed
framework. Ten formulations of this class of problems are considered
in the context of production, reduction and relaxed reduction schemas
of problem solving. Possible developmental paths for moving between
these formulations are explored. The emphasis is on an analysis of
the acquisition and transformation of various bodies of knowledge that
are components of problem formulations, and on the characterization of
problems encountered in trying to mechanize knowledge transformations
that lead to problem formulations of increased power.
\*
CBM-TR-119
\4/81
\"Reasoning by Default"
\N.S. Sridharan
C.F. Schmidt
J.L. Goodson
\
\
\1/82
\Plausible reasoning is used on many occasions when deductive reasoning
fails. One form of such reasoning permits making assumptions that are
consistent with what is known provided there is support for it.
Support refers to the availability of a default rule whose
prerequisites are true or believable. In this paper we relate a
concept hierarchy to default theories, advance several @ux(principles
of default rule formulation) and discuss how these principles may be
partially ordered by their @u(permissiveness).
\*
CBM-TR-120
\4/81
\"A Bibliography on Machine Learning"
\B. Nudel
P. Utgoff
\
\
\1/82
\The following is a bibliography on machine learning. It is
structured by having references labelled with pointers to one or more
of a set of six categories from which we make a taxonomy of the field.
We exclude, or de-emphasize, areas where extensive bibliographies
already exist, such as induction of numerical discriminants (pattern
recognition), the adaptive system approach to learning (within control
theory), and data interpolation and approxmation by curve fitting
(within numerical analysis).
\*
CBM-TR-121
\6/81
\"Developing Microprocessor Based Expert Models Instrument Interpretation"
\S. Weiss
C.A. Kulikowski
R. Galen
\
\
\1/82
\We describe a scheme for developing expert interpretive systems and
transferring them to a microprocessor environment. The scheme has
been successfully implemented and tested by producing a program for
interpreting results from widely used medical laboratory instrument:
a scanning densitometer. Specialists in the field of serum protein
electrophoresis analysis provided the knowledge needed to build an
interpretive model using EXPERT, a general production rule system for
developing consultation models. By constraining a few of the
structures used in the general model, it was possible to develop
procedures for automatically translating the model to a specialized
application program and then to a microprocessor assembly language
program. Thus, the model development can take place on a large
machine, using established techniques for capturing and conveniently
updating expert knowledge structures, while the final interpretive
program can be targeted to a microprocessor depending on the
application. Our experience in carrying out the complete process
illustrates many of the requirements involved in taking an expert
system from its early development phase to actual implementation and
use in a real world application.
\*
CBM-TR-122
\7/81
\"A Research Strategy for Computational Studies of
Event and Action Perception"
\N.S. Sridharan
J.L. Goodson
C.F. Schmidt
\
\
\1/82
\An initial step towards an information processing theory of human event and
action perception can be taken by defining the computational problem
constructing a framework in which plausible processes and representations
can be explored. The problem of event and action perception is defined as
moving from a sequence of "images," descriptions of objects and their
positions, into representations of changes, movements, events, and actions.
A computational framework for exploring various expectation and data-driven
process disciplines is proposed. This framework addresses two problems of
choice posed to the human information processing system: 1) the @b[selection]
of observations; and 2) the selection of @b[grain] or levels of
representation.
\*
CBM-TR-123
\9/81
\"An Interactive Planner that Creates a Structured,
Annotated Trace of its Operation"
\John Bresina
\
\
\3/82
\This report presents a planning system which is capable of performing
commonsense reasoning in incompletely specified real world domains.
The major focus is on the plan generation/extension component -
PLANX10 which makes plausible assumptions, is capable of being
restarted, and is guided by plan critics and/or interactively by the
user. PLANX10 creates and uses an explicit structured, annotated
trace of its planning process.
\*
CBM-TR-124
\ll/81
\"Common Virtual Arrays in PDP-11 Fortran: An Exercise in Software
Engineering"
\R. Schwanke
\
\
\1/82
\DEC has added @i(virtual arrays) to RSX-11 Fortran-IV-Plus, as a means
of allowing user programs to contain more than 32K words of code and
data. However, these arrays may not be used in COMMON or EQUIVALENCE
statements, which severely limits their usefulness. The Expert
consultation system at Rutgers ran headlong into the 32K word limit
when it was transported from a DECSystem-20 to a PDP-11/60 running
RSX-11M. This provided the impetus to make virtual arrays more
useful. I describe a simple program which, in combination with
existing DEC software and a simple programming standard, makes virtual
arrays behave as if they resided in an unnamed COMMON block of virtual
storage. The mechanism imposes no additional run time overhead. This
technique is an example of modifying a language by means of simple
auxiliary processors, and of applying software engineering principles
to a severely constrained program adaptation problem.
\*
CBM-TR-125
ALSO LISTED AS LRP-TR-12
\11/81
\"Representing Knowledge in AIMDS: Introduction using TAXMAN Examples"
\N.S. Sridharan
\
\
\1/82
\This report begins with a quick overview of artificial intelligence;
and come to focus on the idea of knowledge as being the essence of how
our intelligence operates. Representation of knowledge in a machine
is the sytematic expression of knowledge as for representing knowledge
as symbol structures. The remaining sections illustrate the
facilities, of the language AIMDS, for representing knowledge
in a machine. Examples and illustrations are drawn from the TAXMAN
application, so that you will see some representation of legal
concepts and facts. The main representations are of objects, object
classes, intension and extension of classes, class hierarchies, state
changes, actions and patterns of actions forming action hierarchies.
These are the elements of a "logical template" representation of those
concepts of law that are precise unambiguous. The report is aimed at
a multi-disciplinary audience comprised of logicians, philosophers,
lawyers, politicians and computer scientists, who gathered for a
conference, "Logica, Informatica, Diritto" [Logic, Informatics and
Law] in Florence, Italy held in April 1981. Therefore, I have tried
to keep my presentation at a very simple level. My purpose will be
served if I arouse enough interest in you that you will follow up the
newly developing field of Artificial Intelligence.
\*
CBM-TR-126
\2/82
\"Expert Behavior and Problem Representations"
\S. Amarel
\
\
\1/82
\Expert behavior is characterized by high-performance problem solving
behavior in a specific domain. Commonly, this type of behavior
requires the conceptualization/formulation of a given problem within a
highly 'appropriate' representational framework - where
'appropriateness' refers to a computational efficiency, and it is task
specific. The problem of how to choose an 'appropriate' problem
formulation and how to change it to fit the characteristics of a task,
is it at the heart of the problem of problem representations in AI. In
this paper, relationships between characteristics of 'intelligent
expert' systems and developmental processes of problem reformulation
are discussed. The nature of problem reformulation sequences is
explored in the context of expertise acquisition in the domain of
Tower of Hanoi problems. Our work suggests that 'intelligent expert'
systems must have available large amounts of knowledge of various
kinds - both domain independent and domain specific; they must have
the ability to maintain several alternative formulations of a problem
class and to move among them in a flexible manner as required by the
specific problem on hand; and they must be able to perform a variety
of theory formation and program synthesis tasks in order to improve
their performance with experience.
\*
CBM-TR-127
\3/82
\"Plan Formation in Large, Realistic Domains"
\N.S. Sridharan and J.L. Bresina
\
\
\3/82
\In this paper we focus on the engineering issue of how a planning system may
be organized to work effectively in large and realistic task domains. We
consider three aspects of this issue: (i) generating and manipulating large
and complex plans, (ii) handling large and complex knowledge bases, and (iii)
operating with an incomplete knowledge base and/or world model. A knowledge
description formalism is introduced, which allows a rule base to be
well-structured for efficient retrieval by inheritance. An interactive
planning system, PLANX10, is described which builds an explicit plan graph,
that allows interactive guidance, plan refinement and revision.
\*
CBM-TR-128
\9/82
\"Evolution of a Plan Generation System"
\NS Sridharan
JL Bresina
CF Schmidt
\
\
\9/82
\We begin by discussing the role of a plan generation system in a plan
recognition process. A planning system in this context should be able
to plan robustly despite the absence of specific plan relevant
knowledge, making assumptions where appropriate, be capable of
revising plans and be able to make no more committments to specifics
than needed. Three plan generators (PGEN, PLANX10, and PLANX10-D),
forming stages in the evolution, are described and critiqued. The
sequence moves toward plan representations supporting greater
flexibility and modularity of the planner's control structure,
containing appropriate information (annotations, constraint
descriptions and ordered description spaces) to enable plan revision.
Out of this emerges a set of uniform plan modification operators
usable for plan generation as well as plan revision. We then discuss
briefly plan execution monitoring and revision within this framework.
\*
CBM-TR-129
\9/82
\"A Future for Knowledge Representation Systems"
\N.S. Sridharan
\
\
\9/82
\
\*
CBM-TR-130
\1/83
\"Using Empirical Analysis to Refine Expert System Knowledge Bases"
\P.G. Politakis
\
\
\11/82
\This thesis describes a system that provides a unified design
framework for building and empirically verifying an expert system
knowledge base. SEEK is a system which gives interactive advice about
rule refinement during the design of an expert system. The advice
takes the form of suggestions for possible experiments in generalizing
or specializing rules in a model of reasoning rules produced by an
expert. Case experience, in the form of stored cases with known
conclusions, is used to interactively guide the expert in refining the
rules of a model. This approach is most effective when a model of the
expert's knowledge is relatively accurate and small changes in the
model may improve performance. The system is interactive; we rely on
the expert to focus the system on those experiments that appear to be
most consistent with his domain knowledge. The design framework of
SEEK consists of a tabular model for expressing expert-derived rules
and a general consultation system for applying a model to specific
cases. The system has been used in building large-scale expert
medical consultation systems, with examples taken from an expert
consultation model for the diagnosis of rheumatic diseases.
\*
CBM-TR-131
\10/82
\"Multiple Strategies of Reasoning for Expert Systems"
\Yao Yuchuan
Casimir A. Kulikowski
\
\
\11/82
\In expert systems the heuristics used for combining the weight of evidence
can be based on probabilistic, fuzzy set, or subjective confidence factors.
Although the underlying assumptions for each of the methods differ, it can
be shown that there are correspondences between them and that it is possible
to develop a model of expert reasoning for medical consultation using any one
of the methods. We have developed a system for representing expert knowledge, called ESMES which is an outgrowth of the EXPERT scheme developed earlier at
Rutgers. ESMES allows the use of alternative strategies in the solution of
a consultation problem. In this paper we report on the performance of ESMES
for a prototype glaucoma consultation model, using reasoning mechanisms
similar to those of the EXPERT, MYCIN, INTERNIST I, and PROSPECTOR systems.
\*
CBM-TR-132
\9/82
\"Treatment Selection and Explanation in Expert Medical Consultation:
Application to a Model of Ocular Herpes Simplex"
\John K. Kastner
Sholom M. Weiss
Casimir A. Kulikowski
\11/82
\
\
\This paper describes a general scheme for use in expert consultation systems
to aid in the selection of therapies. The scheme consists of a topological
sorting procedure within a general production rule representation. The
procedure is used to choose among competing therapies on the basis of
precedence rules. This approach has a degree of naturalness that lends itself
to automatic explanation of the choices made. An expert system for planning
therapies for patients diagnosed as having ocular herpes simplex has been
implemented using this approach. Examples of the system's output on actual
cases are given.
\*
CBM-TR-133
\7/83
\"Knowledge Structures for a Modular Planning System"
\N.S. Sridharan
\J.L. Bresina
\
\
\7/83
\In this paper, we discuss knowledge structures used in a modular
system for user-interactive planning in realistic task domains. A
theme which is reflected throughout the paper is the policy of
developing common representations useful in many modules of the
planning system. We believe thse representations will be useful in
other Artificial Intelligence systems with similar demands on
knowledge and reasoning skills. We present uniform representations
for (i) descriptions of objects and actions, including partial and
indefinite descriptions, (ii) world knowledge of task domains, (iii) a
trace of the planning process which includes alternate solutions, and
(iv) an organizational mechanism for both the world knowledge as well
as the knowledge gathered during the planning process (e.g., the
constraints among the objects and actions contained in a plan solution).
\*
CBM-TR-134
\7/83
\"A Mechanism for the Management of Partial and Indifinite
Descriptions"
\N.S. Sridharan
\J.L. Bresina
\
\
\7/83
\Schemes of knowledge representation are designed to represent
definite and indefinite descriptions. We relate here our experieince
in using partial and indefinite descriptions of actions and objects
arising in a planner. We identify three sources of indefinite
descriptions: (i) need to refer to objects and actions that are yet
unrealized (even in a complete world model, (ii) the incompleteness of
the world model, and (iii) the need for the planner to postpone
choices by expressing constraints on the selection of objects and the
sequencing of actions. We demonstrate a uniform mechanism for the
representation of descriptions that allows computing referents,
maintaining co-references and the detection of inconsistent indefinite
descriptions. The mechanism allows the grouping of object and action
descriptions, structured by @i[specificity] and equivalence
relationships. It is hoped that our experiencxe may be valuable to
anyone concerend with knowledge representation, whether it is applied
to planning, natural language processing, knowledge acquisition, or
expert system engineering.
\*
CBM-TR-135
\10/83
\"Program Synthesis as a Theory Formation Task-- Problem
Representations and Solution Method"
\Saul Amarel
\
\
\10/83
\This paper is concerned with theory formation processes in the
context of a program synthesis task. The problem is to synthesize a
program, in a given programming language, that satisfies a given set
of input-output data associations in the domain of finite partially
ordered structures. The associations are presented in a data-space,
and the possible solutions/programs, i.e., the programming language,
define a program-space. Several formulations of the theory formation
problem are presented. The movement to formulations of higher
effectiveness involves structuring of program-space in a way that
facilitates links to be established with data-space, and increasing
the amount of reasoning that takes place in data-space. The role of
models (algebraic, geometric) is extremely important in the strong
problem formulations. Three main approaches are discussed. The first
two were developed in previous work: One is based on heuristic hill
climbing in program-space; and the second is more goal-oriented, and
it involves "navigation" in program-space under the guidance of an
algebraic model. Work on the third approach is more recent, and it is
based on detailed reasoning in data-space. Two methods are presented
in connection with the data-driven approach: a combination method and
an elimination method. By shifting the reasoning towards the
data-space, several interesting domain-dependent problems of concept
specialization and generalization are encountered. Basic AI issues
that are identified, and on which more work is needed, include: the
formation of macromoves in "appropriate" representations of
program-space and data-space; development of methods for combining
"partially correct" programs, and for modifying "almost correct"
programs; and exploring the interplay between the choice of a domain
of a theory and the formation of an "interesting" theory for the domain.
\*
CBM-TR-136
\"Strategies for Expert Consultation in Therapy Planning"
\John. Karl Kastner
\
\
\1/84
\This thesis deals with the problem of designing tools for building
consultation systems for therapy planning. In the past, several
therapy planning systems have been developed for which the necessary
code was specially crafted for a particular problem or a paticular
domain. In contrast, this work presents a set of procedures that have
been found to be useful in the development of consultation models for
several different problems in several different domains. In
addition, the procedures are applicable to a general class of problems
known as "classification problems".
\*
CBM-TR-137/LCSR-TR-53
\3/84
\N.S. Sridharan
J.L. Bresina
\
\
\3/84
\The problem solving ability of an AI program is critically dependent on the
nature of the symbolic formulation of the problem given to the program.
Improvement in performance of the problem solving program can be made not only
by improving the strategy of directing search but also by shifting the problem
formulation to a more appropriate form. Certain formulations are more
amenable to incremental acquisition of problem solving strategy than others.
With this in mind, an @i{extensible problem reduction method} is developed
that allows @i{incremental strategy construction}.
The overall objective of our present research is to study strategy acquisition
and problem reformulation for planning problems. We illustrate the combined
use of @i{analytical} and @i{empirical} methods. We demonstrate @i{Case
Study} and @i{Plan Recognition} as techniques that permit improvement of
problem solving strategy using @i{single} problem instances. The work we
propose here builds on our earlier work on Plan Recognition and on Plan
Generation.
CBM-TR-138
\5/84
\"Hardware Fault Diagnosis & Expert Systems"
\Allen Ginsberg
\
\
\5/84
\Recent research in Expert Systems has begun to deal with problem
domains that do not fit into the "classification problem" mode, the
latter being the sort of problems that have been most amenable to
Expert System technology. Hardware Fault Diagnosis(HFD) is an example
of such a problem domain. Problems in HFD typically involve a
"localization" problem as a component, i.e., @i[where] is the location
of the fault? This paper takes a critical look at some current work
in HFD, viz. Genesereth, Davis, with a view towards determining the
differences between classification and localization problems that are
likely to necessitate new approaches to knowledge representation and
acquisition if Expert Systems are to be sucessful in such a domain.
\*
CBM-TR-139
\5/84
\"Localization Problems and Expert Systems"
\Allen Ginsberg
\
\
\5/84
\Expert systems approaches to problem solving have recently had
enormous success and influence in the field of AI. The most
successful of these systems tend to deal with a certain kind of
problem type which have been called "classification problems." Very
recently, we have seen the emergence of a number of expert systems
that deal with a different category of problem, a category that I will
call "localization problems." The purpose of this paper is to
characterize this class of problems, contrast it with the
classification problem category, give some examples of localization
problems, and suggest some new avenues for expert system research
dealing with problems in this category.
\*
CBM-TR-140
\5/84
\"Investigations in the Mathematical Theory of Problem Space
Representations and Problem Solving Methods"
\Allen Ginsberg
\
\
\5/84
\In this paper I address the issue of how a system that has the ability
to do problem solving and planning - in the sense of being in
possession of generalized schemas or templates for carrying out these
activities - can know whether a particular type of planning or, if you
will, problem solving strategy, is a "good" one to employ in solving
problems in a particular domain? It seems to me that, in general, in
order to make such judgements in a reasonable fashion a problem solver
must either be in possession of some general theoretical facts
concerning the nature and structure of problem types, i.e., a theory
of problem types, or at the very least, have been programmed by
someone having such a theory. This paper is a step in the direction
of constructing such a theory.
The structure of the paper is as follows. First I discuss the nature
of problem solving and planning in general, and give a preliminary
description of a particular planning template. Next I describe and
illustrate a mathematical framework within which one can formulate
problem representations. Finally I deal with the question of what
facts about the structure of a problem representation are relevant to
the determination of whether or not the aforementioned planning
template is applicable to the problem at hand.
\*
CBM-TR-141
\5/84
\"Representation & Problem Solving: Theoretical Foundations"
\Allen Ginsberg
\
\
\10/84
\The word "representation" and its cognates is probably the most
popular word in AI today. If anything qualifies as "the fundamental
assumption of AI," it is probably the view that intelligence is
essentially the ability to construct and manipulate symbolic
@i[representations] of some "reality" in order to achieve desired
ends. Furthermore, probably every researcher in AI would agree that
the key to AI's success lies with the general area known as "knowledge
representation." This point of view has been buttressed not only by
the failures of early "general purpose" AI systems, but much more so
by the recent success of expert systems. The philosophy behind the
expert systems approach is one that has, rightfully come to infect the
entire field of AI: intelligence essentially depends upon the ability
to @i[represent] and store a potentially vast amount of knowledge in ways
that enable it to be easily accessed and utilized in the performance
of various tasks. The key concept here is @i[representation].
Given the fact that AI has come to embrace these doctrines, and the
likelihood that there is a good deal of truth in them, it is incumbent
upon us to examine their foundations, for better or for worse. It
would be nice to have answers to questions such as What is a
representation?, When are two or more representations representations
of the same or different real world situations?, What are the ways in
which representations can be "manipulated?" It would be even nicer if
the answers to such questions were provided by a general formal theory
of representation. In this paper I attempt to lay some of the
groundwork for such a theory, with emphasis on the role of
representation in problem solving.
\*
CBM-TR-142
\5/84
\"A Model for Automated Theory Formation for Problem Solving Systems"
\A. Ginsberg
\
\
\5/84
\The goal of this paper is to contribute towards the understanding and
eventual mechanization of the processes whereby an @i[intelligent]
problem solver @i[learns] to improve its performance in a given task
domain by formulating and using @i[theories] regarding that domain. In
order to achieve this goal it is necessary for us, as designers of
such a system, to have a fairly good idea of a) the various sorts of
knowledge that are required for a problem solver to acquire new
knowledge that will hopefully improve performance, and of b) how each
of these types or sources of knowledge comes into play in this
process. In this paper I give an abstract description of the domains
of knowledege required for theory formation, and also illustrate the
ideas with a concrete example. The type of system contemplated in
this paper incorporates ways of structuring background knowledge that
are natural and will, I believe, prove to be useful in designing
self-improving AI programs.
In this paper I address the issue of how a system that has the ability
to do problem solving and planning - in the sense of being in
possession of generalized schemas or templates for carrying out these
activities - can know whether a particular type of planning or, if you
will, problem solving strategy, is a "good" one to employ in solving
problems in a particular domain? It seems to me that, in general, in
order to make such judgements in a reasonable fashion a problem solver
must either be in possession of some general theoretical facts
concerning the nature and structure of problem types, i.e., a theory
of problem types, or at the very least, have been programmed by
someone having such a theory. This paper is a step in the direction
of constructing such a theory.
The structure of the paper is as follows. First I discuss the nature
of problem solving and planning in general, and give a preliminary
description of a particular planning template. Next I describe and
illustrate a mathematical framework within which one can formulate
problem representations. Finally I deal with the question of what
facts about the structure of a problem representation are relevant to
the determination of whether or not the aforementioned planning
template is applicable to the problem at hand.
\*
CBM-TR-143
\5/84
\"A Knowledge Representation Framework for Expert Control of
Interactive Software Systems"
\Apte, C.
S. Weiss
\
\
\10/84
\Expert problem solving strategies in many domains make use of
detailed quantitative or mathematical techniques coupled with
experiential knowledge about how these techniques can be used to solve
problems. In many such domains, these techniques are available as part
of complex software packages. In attempting to build expert systems
in these domains, we wish to make use of these existing packages, and
are therefore faced with an important problem: how to integrate the
existing software, and knowledge about its use, into a practical
expert system. We define a framework of a @i[hybrid model] for
representing problem solving knowledge in such domains. A hybrid
model consists of a @i[surface] and a @i[deep] model. The surface
model is the production rule-based expert subsystem that is driven by
domain specific control and interpretive knowledge. The deep model is
the existing software, reorganized as necessary for its interpretation
by the surface model. We present an outline of a specialized
form-based system for acquisition and representation of expert
knowledge required for this hybrid modeling.
\*
CBM-TR-144 (THESIS)
\9/84
\"A Framework for Expert Control of Interactive Softweare Systems"
\C.V. Apte
\
\
\10/84
\Expert problem-solving strategies in many domains require the uise of
detailed mathematical techniquers coupled with experiential knowledge
about how and when to use the appropriate techniques. In many of
these domains, such techniques are made available to experts in large
software packages. In attempting to build expert systems for these
domains, we wish to make use of these existing packages, and are
therefore faced with an important problem: how to integrate the
existing software, and knowledge about its use, into a practical
expert system. The expert knowledge is used, in dynamic selection of
appropriate programs and parameters, to reach a successful goal in the
problem-solving. This kind of expert problem-solving is achieved
through two interacting bodies of knowledge; problem domain knowledge,
and knowledge about the programs that comprise the software package.
This thesis describes the framework of a @i[hybrid expert system] for
representing problem-solving knowledge in these domains. This hybrid
system may be characterized as consisting of a @i[surface] model and a
@i[deep] model. The surface model is a production-rule based expert
subsystem that consists of heuristics used by an expert. The deep
model is a collection of methods, each parameterized by a set of
controlling and observed parameters. The method and their results are
reasoned about using their parameter sets. The existing software is
reorganized as necessary to map it into the deep model structure of a
hybrid system. This framework has evoled out of an effort to build an
expert system for performding well-log analysis (ELAS - @i[Expert Log
Analysis System]). A generalized expert-system building methodology
based upon principles drawn from ELAS is introduced. The use of
@i[method-abstractions] in assembling a hybrid system is discussed.
The notion of @i[worksheet-reasoning] is defined, and discussed.
\*
CBM-TR-145 (THESIS)
\10/84
\"Shift of Bias for Inductive Concept Learning"
\Paul E. Utgoff
\
\
\ll/84
\We identify and examine the fundamental role that bias plays in
inductive concept learning. Bias is the set of all influences,
procedural or declarative, that causes a concept learner to prefer one
hypothesis to another. Much of the success of concept learning
programs to date results from the program's author having provided the
learning program with appropriate bias. To date there has been no
good mechanical method for shifting from one bias to another that is
better. Instead, the author of a learning program has himself had to
search for a better bias. The program author manually generates a
bias, from scratch or by revising a previous bias, and then tests it
in his program. If the author is not satisfied with the induced
concepts, then he repeats the manual-generate and program-test cycle.
If the author is satisfied, then he deems his program successful. Too
often, he does not recognize his own role in the learning process.
Our thesis is that search for appropriate bias is itself a major part
of the learning task, and that we can create mechanical procedures for
conducting a well-directed search for an appropriate bias. We would
like to understand better how a program author does about doing his
search for appropriate bias. What insights does he have? What does
he learn when he observes that a particular bias produces poor
performance? What domain knowledge does he apply?
We explore the problem of mechanizing the search for appropriate
bias. To that end, we develop a framework for a procedure that shifts
bias. We then build two instantiations of the procedure in a program
called STABB, which we then incorporate in the LEX learning program.
One, called "constraint back propagation" uses analytic deduction. We
report experiments with the implementations that both demonstrate the
usefulness of the framework, and uncover important issues for this
kind of learning.
\*
CBM-TR-146
\5/85
\"A Framework for Representation of Expertise in Experimental Design
for Enzyme Kinetics"
\Von-Wun Soo, Casimir A. Kulikowski, David Garfinkel
\
\
\5/85
\In this paper, we present part of our current research on expert
systems in enzyme kinetics. Because of the richness and diversity of
the problem solving knowledge required in this domain, we have found
it to be an excellent vehicle for studying issues of knowledge
representation and expert reasoning in AI. Biochemical experimental
design, the focus of this paper, is a major problem solving activity
of the enzyme kineticist that has not been explored by expert systems
researchers. Their problem solving expertise can usually be described
as the application of a sequence of methods. In designing a
complicated biochemical experiment, the experimenter has several
methods to choose from at any stage. These methods are represented as
computer programs which can be organized into a hierarchy. This paper
proposes a structure for these problem solving methods and an expert
consultation system for experimental design.
We have found that problem solving expertise in experimental design
can be divided into three phases. In the first phase, we deal with
problems of selecting the experimental methods that satisfy an
experimenter's goal, given certain postulated models. The
experimental conditions and optimal design points can be derived if
the model is given and the goal and the assumptions of the optimal
design criterion are satisfied. In the second phase, we deal with the
problems of preparing an enzyme assay. The interactions among
experimental conditions and other influencing factors must be
carefully controlled so that the correct concentration of a given
species can be calculated. In the third phase, we face the problem of
analyzing and interpreting the experimental data and recommending
further refinement of the experiment.
\*
DCS-TM-13
\5/80
\"A Guide to Applying to Graduate School"
\Don Libes
\
\
\1/82
\I. @u(Introduction)
As a senior at Rutgers, you should have some idea of what interests
you. Start having serious conversations with yourself about what you
want to do for the next few years of your life. If you liked school,
liked the atmosphere, the people, the freedom to pick and choose
projects to be involved with and the challenge of stimulating
intellectual problems, graduate school should be heavily considered.
In this sense, graduate school provides a similar environment to the
one that you have just passed through though it is much more intense.
You only take courses in your major. You are surrounded by people who
think, talk and dream about Computer Science (and not just hacking,
but research).
The advantages of a graduate degree in CS are almost guaranteed to
include a better chance of choosing the job that you want or perhaps,
to command a higher salary. "Satisfactory employment" of last year's
Computer Science Ph.D. graduates in the United States is currently
100%.
Its drawbacks should be considered, too. Dedicating at least 4 years
of your life to schooling is not necessary to your survival and it
should be recognized that billions of people are alive today without
the help of an advanced degree. If school life is not the life for
you or you are sick and tired of studying, graduate school might not
be the path to follow, at least in the immediate future. Putting off
graduate school will also give you the opportunity to earn a nice pad
of wealth that you probably wouldn't accumulate as a student.
\*
DCS-TM-14
\7/80
\ "Software Design Issues in the Architecture and Implementation
of Distributed Text Editors"
\R. Goldberg
\
\
\1/82
\Conventional text editors consist of a program which runs on a single
host machine and utilizes the CPU, disk, and other resources of the
host to process every character that the user types on his terminal.
This arrangement has several serious drawbacks, namely the
@u(computational load on the host) (CPU cycles and I/O interrupts),
the @u(response time seen by the user) (delay in processing user
keystrokes), and the @u(communications cost). These undesirable
aspects of editing files residing at a remote host have become
important issues to users of text editors on large mainframe systems.
The availability of cheap personal microprocessors suggests that they
be used to help solve the problems. Thus the motivation for the
distributed editor capabilities to be proposed in this work results
from the insufficiency of existing editing facilities on timeshared
computers as well as from the trend toward personal computers.
\*
DCS-TM-15
\3/81
\"Some Experiments in Abstraction of Relational Characteristics"
\R.M. Keller
D.J. Nagel
\
\
\1/82
\Two experiments performed in knowledge-based inference are discussed in this paper. The experiments are directed at abstracting
structural regularities and patterns inherent in a database of binary
relations. A novel graph representation to facilitate abstraction is
used in approaching some classical problem areas. This representation
is compact and powerful, and an efficient algorithm has been developed
to help control the exhaustive nature of certain types of inductive
problems.
One area of experimentation concerns the discovery of intensionally definable relations in a
family databse. Another is the recognition of alphabetic characters
using directional relations defined for points on a grid. Within a
test bed system, KBLS, a scheme for computing abstractions is briefly
summarized, and implications for future extensions are discussed in
light of experimental results.
\*
DCS-TM-16
\3/83
\"Solving the Plane Geometry Problem by Learning"
\Liben Xu
\
\
\3/83
\The top-down technique for solving a geometry problem is described.
The top-down method uses "general rules," they are obtained by
learning. This report focuses on general heuristics to obtain the
general rules for solving a geometry problem.
\*
DCS-TR-89
\5/80
\"Parts I, II, III of KNOWLEDGE BASED LEARNING SYSTEMS DS + CVS = A
Proposal for Research CVS = An Intro. to the Meta-Theory & Logical
Foundations"
\D. Sandford
\
\
\1/82
\Current state of the art experience in designing domain specific,
intelligent, automated problem solving systems argues convincingly
that: Firstly, large amounts of what is known as domain dependent or
domain specific knowledge is crucial to achieving acceptable
efficiency in realistic problem solving situations; and secondly that
the task of implementing such systems "from scratch" is such a
formidable one that it has impeded experimental research into the
nature and role of domain specific knowledge in problem solving.
This project is directed towards attaining an understanding of the
processes and types of organizations required for an automated system
to be able to learn for itself the relevant domain dependent
knowledge from its experience with the domain. The research is based
on a meta-theory of knowledge based learning systems, systems that can
discover domain knowledge and use it to solve problems in a domain.
The research project will employ both experimentation with implemented
systems and theoretical analysis of systems. The goals are to shed
light on both the detailed mechanisms by which domain dependent
knowledge increases search efficiency, and to understand the type of
innate biases that an automated system needs, to be able to analyze a
domain and discover the appropriate domain knowledge. The research is
based on a meta-theory of systems that are both knowledge based
systems and learning systems.
The research focusses on two kinds of systems: Systems that can build
and use empirical theories of domains, and systems that use Axiomatic
theories and theorem proving. The nature of domain knowledge and ways
of using it in both these systems are investigated.
\*
DCS-TR-90
\5/80
\"Knowledge-based learning, an Example"
\C. V. Srinivasan
\
\
\1/82
\I. @u(Introduction)
How may a machine "learn" from examples of situations that are
presented to it? What may constitute the "knowledge" of a set of such
situations? How should the examples be presented to the machine? Are
there general principles which a machine can use to acquire the
knowledge automatically by examining the examples presented to it, and
to use the knowledge so obtained to solve problems in a domain? These
are the general concerns of my research.
\*
DCS-TR-91
\7/80
\"Policy Function Scheduling"
\M. Ruschitzka
\
\
\1/82
\Scheduling disciplines have traditionally been specified in terms of
queues and algorithms for routing jobs between the queues.
Alternatively, a discipline may be formally defined by a policy
function, a function of job and system parameters. A policy function
scheduler is a parameterized scheduler that - when supplied with a
specific policy function - behaves like the specified discipline. The
formal definition allows performance measures of a discipline (e.g.,
the response function) to be expressed in terms of the defining policy
function. We review the principles of formal definitions, summarize
previous queueing-theoretical results concerning response functions of
policy function schedulers, and extend them to multiple preemptive job
classes with processor-sharing subclasses. For a large variety of
disciplines and job classes, we also express the policy functions in
terms of the resulting response functions. Given a desired realizable
performance goal, this relation serves to determine the discipline
that achieves it. Policy function schedulers with their explicit
relation between policy and response functions, which we plot for
several different job characteristics, thus offer increased precision
in controlling the performance of a computer system.
\*
DCS-TR-92(received it, but elsie gave it back to him to be done over)
\4/80
\"Average Case Behavior of the Alpha-Beta Tree Pruning Algorithm"
\George Shrier
\
\
\1/82
\
\*
DCS-TR-93
\8/80
\A Dialogue Moderation for Program Specification - Dialogues in
the PSI System"
\L. Steinberg
\
\
\1/82
\
\*
DCS-TR-94
\9/80
\"On The Existence of Approximate Solutions for Singular Integral
Equations of Cauchy Type Discretized by Gauss-Chebyshev Quadrature
Formulae"
\A. Gerasoulis
\
\
\1/82
\It is shown that the direct Gauss-Chebyshev method used for the
numerical solution of singular integral equations of Cauchy-type
possesses a unique solution for any n,as long as @w( ) is not an
eigenvalue of the equation.
\*
DCS-TR-95
\10/80
\A Mini-Max Problem"
\W.L. Steiger
\
\
\1/82
\"Determine an algorithm, better than complete enumeration, for the
following problem: given a non-negative integer matrix, permute the
entries in each column independently so as to minimize the largest row
sum. This problem had arisen in determining an optimal scheduling
for a factory work force."
\*
DCS-TR-96
\1/81
\A Comparison of Methods for Discrete L1 Curve-Fitting
\W.L. Steiger
\
\
\1/82
\We study discrete L1 curve-fitting of n points in k dimensional space.
Execution times for the algorithms of Barrodale-Roberts (BR),
Bartels-Conn-Sinclair (BCS), and Bloomfield-Steiger (BS) - three of
the best LAD curve-fitting procedures - are compared over a variety of
deterministic and random curve-fitting problems. Analysis of the
results allows us to make surprisingly precise statements about the
computational complexity of these algorithms.
In particular, BR is in a different complexity class than BCS and BS
as the number of points, n, increases. All algorithms are linear in
the dimension, k, and BS is less complex than BCS.
\*
DCS-TR-97
\5/81
\"Linear Programming via Discrete L1 Curve-fitting"
\W.L. Steiger
\
\
\1/82
\A bounded linear programming problem with feasible solutions may be
cast as a discrete L1 curve-fitting problem of the same size. This
may be usefully exploited in solving dense LP problems: On the
average, a recent L1 algorithm solves the equivalent L1 curve fit in
far fewer steps, and taking far less time, than that which would be
required by the one-phase Simplex method applied to the original
problem. The relative advantage increases with problem size and the
comparison is even more favorable against the two-phase Simplex
method. Finally, the Klee-Minty problems on which the Simplex method
is of exponential complexity, seem to be "easy" problems as equivalent
L1 curve fits.
\*
DCS-TR-98
\11/80
\Partitioning Methods for Block-Diagonal Linear Systems and Programs
\M. D. Grigoriadis
\
\
\1/82
\
\*
DCS-TR-99
\12/80
\Network Optimization Problems and Algorithms: An Annotated Bibliography
\M. D. Grigoriadis
\
\
\1/82
\This annotated bibliography is intended as a repository of notes and
reminders of contributions to the field of network optimization and it
is by no means historically or topically complete. It represents the
current state of a computerized bibliography database and the author's
attempt to track the large number of technical papers in specific
areas of network optimization. While it may never reach perfect
completeness, future versions of this report will be released with
updates and additional references.
\*
DCS-TR-100
\2/81
\"Energy and Group Velocity in Semi Discretizations of
Hyperbolic Equations"
\R. Vichnevetsky
\
\
\1/82
\Propagation properties of a numerical semi-discretization of
hyperbolic equation are analyzed, using time-Fourier Transforms. It
is shown that numerical solutions are of two types, corresponding to
the two roots of a characteristic equation which is associated with
the semi-discretization. The properties of those two types of
solutions in terms of phase velocity, wavelength and group velocity
are derived. While solutions of the first type converge to genuine
solutions of the equation, solutions of the second type have group
velocities opposite to the direction of flow, and are entirely
spurious.
\*
DCS-TR-101
\2/81
\"Propagation Through Numerical Mesh Refinement for Hyperbolic
Equations"
\R. Vichnevetsky
\
\
\1/82
\Spurious reflection that occurs at the interface between coarse and
fine mesh in the numerical finite-difference approximation of
hyperbolic equations is analyzed. By using time-Fourier Tranforms, a
reflection ratio at the interface can be derived. It is then possible
to describe exactly the reflection that occurs, in the form of a
Fourier integral using this reflection ratio. Energy conservation and
convergence rates are examined for a "standard" and a "modified"
treatment of the interface point in the mesh refinement.
\*
DCS-TR-102
\5/81
\"On The Solvability of Singular Integral Equations Via Gauss-
Jacobi Quadrature"
\A. Gerasoulis
R.P. Srivastav
\
\
\1/82
\It is shown that the coefficient matrix obtained by the discretization
of singular integral equations using Gauss-Jacobi quadrature formulae
is non-singular for any n, if @ @ is not an eigenvalue of the equation.
\*
DCS-TR-103
\8/81
\"Numerical Upstream Boundary Conditions that Reduce
Spurious Reflection"
\R. Vichnevetsky
E. Sciubba
Y. Pak
\
\
\1/82
\It is commonly (but erroneously) assumed that the best way to treat
upstream boundaries for hyperbolic equations is to let the numerical
value be equal to the imposed value. What is erroneous in this
assumption is that it ignores the presence of spurious numerical
solutions which may have originated inside of the computational domain
and which may be present near the boundary. Such spurious solutions
are characterized by short wavelength spatial oscillations, with a
group velocity which is opposed to the direction of flow and are
therefore moving as "packets" toward the boundary. They are reflected
by the "standard" treatment whereas a better numerical treatment of
the boundary should attempt to absorb them.
This paper describes two methods for the modified numerical treatment
of upstream boundaries of hyperbolic equations, which are effective in
absorbing those spurious solutions with a remainder which decreases as
@w( ) and @w( ) respectively, where @w( ) is the
frequency and @w( ) is the mesh size.
\*
DCS-TR-104
\8/81
\"A New Lad Curve Fitting Algorithm: Slightly Overdetermined Equation
Systems in L1"
\E. Seneta
W.L. Steiger
\
\
\1/82
\We present a new algorithm for the discrete LAD curve-fitting problem
for n points in k less than or equal to n dimensional space. When k
is about n/3 it begins to out-perform the best current methods, and
the advantage increases with k. The algorithm should be of interest
in approximation theory and in robust regression. Moreover our
approach may be useful in linear optimization, especially in linear
programming.
\*
DCS-TR-105
\3/81
\"User's Guide for MEDIT, A Machine Independent Text Editor"
\R. Goldberg
\
\
\1/82
\A text editor is a program used to create and modify text files stored
in the computer. Text editors are useful for creating and modifying
computer programs, documentation, data files, letters, and many other
kinds of text.
MEDIT is a text editor written in MAINSAIL. It can run on any
computer for which a MAINSAIL implementation exists, and on any
terminal type. Both with regard to the computer on which it runs and
the terminal used, it is machine-independent.
The basic line editing commands have been adopted from the powerful
SOS text editor for the PDP-10. The intraline editing capability of
SOS has been extended in MEDIT to a video editor which keeps the
screen of the terminal constantly updated to reflect the true state of
the file as modifications are made. Video editing greatly increases
user productivity, especially in editing of English and other
unrepetitive text. On hard copy terminals and on unsupported CRT
terminals, MEDIT cannot provide video editing, but it knows how to
utilize full duplex capabilities to provide character by character
modifications within a line of text. The commands for making changes
within a line are the same for all terminals.
This document contains both an introductory user's manual and as a
reference manual to MEDIT. The introductory manual introduces the
user to the editor while the reference manual provides complete,
detailed specifications of the editor's features. The style of the
introductory manual is informal to aid the learning process. For
clarity, when examples of interaction with MEDIT are given, those
parts that were typed by the user will be shown in @i(italics) while
those parts typed by MEDIT will be in a more standard font.
\*
DCS-TR-106
\10/81
\"Knowledge Representation and Problem Solving in MDS"
\C. V. Srinivasan
\
\
\1/82
\This work presents a new approach for using a first order theory to
generate procedures for solving goal satisfaction problems without
using general thorem proving. The core of the problem solving system
has three basic components: an inferencing mechanism based on
@u(residues), a control structure for "means-end" analysis that uses
@u(natural deduction), and a generalization scheme that is based on
the structure of statements in the domain theory itself.
The work represents a beginning in the development of knowledge based
systems that can generate their own problem solving programs, evolve
with experience and adapt to a changing domain theory.
\*
DCS-TR-107
\10/81
\"Note on Learning in MDS Based on Predicate Signatures"
\C.V. Srinivasan
\
\
\1/82
\This note illustrates a simple learning scheme in the context of two
examples. In the first example the system learns the distinguishing
features of the letters in the English alphabet, where each letter is
described in terms of a relational system of features. In the second
example the domain is a set of family relationships. In this case the
system identifies invariant properties like
"father.father=grandfather" that exist in the domain.
In both examples the system first creates an abstraction of the given
set of relations and uses the abstraction to identify invariant (or
distinguishing) features of the given set of relations. The
abstraction scheme is based on the concept of "predicate signatures"
that is described in the note.
The method is a general one. It can be used to identify large classes
of invariant (or distinguishing) features of sets of objects where
each object is described in terms of a set of relations that hold true
for the object.
\*
DCS-TR-108
\10/81
\"Singular Integral Convergence of the Nystrom Interpolant
of the Gauss-Chebyshev Method"
\A. Gerasoulis
\
\
\1/82
\Nystrom's interpolation formula is applied to the numerical solution
of singular integral equations. For the Gauss-Chebyshev method, it is
shown that this approximation converges uniformly, provided that the
kernel and the input functions possess a continuous derivative.
Moreover, the error of the Nystrom interpolant is bounded from above
by the Gaussian quadrature errors and thus converges fast, especially
for smooth functions. For C@w( ) input functions, a sharp upper bound
for the error is obtained. Finally numerical examples are considered.
It is found that the actual computational error agrees well with the
theoretical derived bounds.
\*
DCS-TR-109
\12/81
\Equations - The "Improved Constraint Satisfaction Algorithms
using Inter-Variable Compatibilities"
\B. Nudel
\
\
\1/82
\This report addresses the problem of improving algorithms for solving
@b(consistent-labeling) (also called @b(constraint-satisfaction)
problems. The concept of @b(compatibility) between variables in such
problems is introduced. How to obtain compatibilities analytically
and empirically is discussed, and various compatibility-based
heuristics (as well as some useful but less effective non
compatibility-based heuristics) are developed to improve a version of
the Waltz algorithm which was found best of a set of consistent-labeling
problem algorithms tested by Haralick [5]. Empirical results with
these heuristics are very encouraging, with over an order of magnitude
improvement in performance with respect to the basic algorithm on a
set of randomly generated consistent-labeling problems.
\*
DCS-TR-110
(Thesis)
\12/81
\"Software Design Issues in the Architecture and Implementation of
Distributed Text Editors" (Thesis)
\R. Goldberg
\
\
\1/82
\This thesis analyzes the performance improvements achieved by
distributing text editing software between a dedicated microprocessor
and a timeshared host computer. Theoretical analysis of the problem
coupled with detailed simulations of possible architectures, using
data collected from over 15,000 actual editing sessions, provide
strong evidence that simple, easily implemented schemes produce
significant improvements of response time to user commands,
communications bandwidth requirements, and host CPU utilization.
\Consisting of an editor server program running on a host and a local
editor running on a microprocessor, a distributed editor would a)
provide general, flexible editing capabilities that are functionally
indistinguishable from those of conventional video editors, b) provide
the same average response on 1200 baud communications lines as
conventional editors running at 9600 baud, c) isolate the user from
most delays due to host timesharing pauses and communications network
slowdowns, and d) reduce considerably the number of program
activations and CPU cycles at the host, making distributed video
editors consume fewer host resources than conventional line editors.
The implementation of a prototype distributed editor based on the
conclusions of the study demonstrates the practicality of implementing
the required software on existing, inexpensive microprocessors such as
those found in conventional terminals.
\*
DCS-TR-111
\3/82
\"NYSTROM'S INTERPOLATION FORMULA IN THE SOLUTION OF SINGULAR INTEGRAL
EQUATIONS DISCRETIZED BY THE GAUSS-JACOBI QUADRATURE
\Apostolos Gerasoulis
\
\
\3/82
\The numerical solution of Singular Integral Equations of Cauchy-type
at a discrete set of points t@-[i], is obtained through discretization
of the original equation with the Gauss-Jacobi quadrature. The
natural or Nystrom's interpolation formula is used to approximate the
solution of the equation for points different than t@-[i]. Uniform
convergence of the interpolation formula is shown for C@+[1]
functions. Finally, error bounds are derived and for smooth function
it is shown that Nystrom's formula converges faster than Lagrange's
interpolation polynomials.
\*
DCS-TR-112 (forthcoming)
\
\"Understand Consistent-Labelling Problems and Their Algorithms: Part I"
\B. Nudel
\
\
\4/82
\
\*
DCS-TR-113
(REVISED): 2/83
\4/82
\"Consistent-Labeling Problems and Their Algorithms: Part II"
\B. Nudel
\
\
\10/82
\A new parameter is introduced to characterize a type of search
problem of broad relevance in Artificial Intelligence, Operations
Research and Symbolic Logic. This paramter, which we call
inter-variable @b[compatibility] is particularly important in that
complexity analyses incorporating it are able to capture the
dependence of problem complexity on search order used by an algorithm.
Thus compatibility-based theories can provide a theoretical basis for
the extraction of heuristics for choosing good search orderings - a
long-sought goal for such problems, since it can lead to significant
savings during search. We carry out expected complexity analyses for
the traditional Backtrack algorithm as well as for two more recent
algorithms that have been found empirically to be significant
improvements, Forward Checking and word-wise Forward Checking. We
extract compatibility-based ordering-heuristics from the theory for
Forward Checking. Preliminary experimental results are presented
showing the large savings that result from their use. Similar savings
can be expected for other algorithms when heuristics taking account of
inter-variable compatibilities are used. Our compatibility-based
theories also provide a more precise way of predicting which algorithm
is best for a given problem.
\*
DCS-TR-114
\3/82
\"The Control of Inferencing in Natural Language Understanding"
\Abe Lockman
\David Klappholz
\
\4/82
\The understanding of a natural language text requires that a reader
(human or computer program) be able to resolve ambiguities at the
syntactic and lexical levels; it also requires that a reader be able
to recover that part of the meaning of a text which is over and above
the collection of meanings of its individual sentences taken in
isolation.
The satisfaction of this requirement involves complex inferencing from
a large database of world-knowledge. While human readers seem able to
perform this task easily, the designer of computer programs for
natural language understanding faces the serious difficulty of
algorithmically defining precisely the items of world-knowledge
required at any point in the processing, i.e., the problem of
@i[controlling inferencing]. This paper discusses the problems
involved in such control of inferencing; an approach to their solution
is presented, based on the notion of determining where each successive
sentence "fits" into the text as a whole.
\*
DCS-TR-115
\4/82
\"A Survey of Research in Strategy Acquisition"
\R. Keller
\
\
\7/82
\This paper surveys literature in the area of strategy acquisition for
artificial and human problem solving systems. A unifying view of the
term "strategy" is suggested which places strategies along a continuum
from abstract to concrete. Major concerns of strategy acquisition
research are described, including (i) strategic component learning,
(ii) strategy applicability recognition, (iii) strategy customization
and (iv) strategy transformation. Various researchers' approaches to
these issues are reviewed and open problems are discussed.
\*
DCS-TR-116
\3/82
\"Group Velocity and Reflection Phenomena in Numerical Approximations
of Hyperbolic Equations: A Survey"
\R. Vichnevetsky
\
\
\6/82
\Recent analyses of spurious phenomena near interfaces and boundaries
of numerical approximations of hyperbolic equations have produced a
host of interesting, concrete results which are reviewed in this
paper.
What characterizes these analyses is that they rely on tools of
mathematical physics, in particular in the systematic use of Fourier
transforms and the concept of sinusoidal wave propagation this leads
to a description of numerical inaccuracy in terms of dispersion, and a
description of spurious numerical solutions in terms of wave packets
and group velocities.
It is in providing the mathematics needed to describe spurious
reflection at numerical boundaries and at interfaces in mesh
refinement that the most applied results of this theory are obtained.
\*
DCS-TR-117
\9/82
\"Incremental Data Flow Analysis Based on a Unified Model of
Elimination Algorithms"
\Barbara Gershon Ryder
\
\
\9/82
\In this thesis we present our work on the development
of incremental update algorithms for global data flow analysis,
algorithms which modify a known data flow solution to reflect
changes in the problem. We have shown that
given a data flow problem defined on a
digraph, the effects of a set of localized program changes
can be determined
@b<without> full re-analysis by some global data flow algorithm.
Our major research contributions fall into three
categories. First, we have modelled three elimination methods for
global data flow analysis: Allen/Cocke interval analysis,
Hecht/Ullman T1-T2 analysis, and Tarjan interval analysis.
Our models allow comparison among the methods and highlight the
sources of worst case complexity improvement. Second, we have designed
two incremental update data flow algorithms based on the Allen/Cocke
algorithm (@b<ACINCF, ACINCB>) and the Hecht/Ullman algorithm (@b<HUINC>).
The complexity and correctness of these algorithms is demonstrated.
Third, we have studied our incremental algorithm
performance on a robust, Algol-like structured programming language
@i<L>.
We have identified program structures which affect the complexity of
incremental updating and established their effects singly and in
concert.
Specifically, for reducible digraphs we have shown that the
elimination phase of @b<ACINCF> (and/or @b<ACINCB>) updates on each
linear system
in the derived sequence, a set of interval head equations and
@b<at most> the equations in @b<one> interval. Further, we
have considered program changes within one interval in a
nested loop in a program in @i<L> and have characterized the set of all
variables whose equations may be affected, in terms
of each variable's corresponding program structure and its relation
to the original change site. Thus, we have ascertained all the
data flow solutions affected
by the changes. Our result enables us to analyze a digraph in @i<L>
with a set of possible changes identifying @i<a priori>, nodes whose
equations will be affected by these changes.
\*
DCS-TR-118
\9/82
\"Transformational Programming--Applications to Algorithms and
Systems"
\Robert Paige
\
\
\9/82
\Transformational programming is a nascent software development
methodology that promises to reduce programming labor, increase
program reliability, and improve program performance. Our research
centers around a prototype transformational programming system called
RAPTS (Rutgers Abstract Program Transformation System), developed
during the past several years at Laboratory for Computer Science
Research. Experiments in RAPTS with algorithm derivations are
expected to lead to pragmatic applications to algorithm design,
program development, and large system construction.
\*
DCS-TR-119
\9/82
\"Fast Minimal Distance Enumeration of Small Combinations"
\W.L. Steiger
P.M. Neuss
\
\9/82
\We give a history dependent algorithm that satisfies the claims of
the title. It has other desirable attributes as well. It is
computationally much simpler than algorithms studied in recent work of
Payne and Ives when, in enumerating n objects k at a time, k is small
compared to n. In fact SN(n,k) decreases n @k[rightarrow]
@k[infinity] where SN denotes the complexity of the present method and
PI, that of Payne-Ives. This is probably due to the savings in
overhead required by historyless enumeration.
\*
DCS-TR-120
\11/82
\"Incremental Data Flow Analysis"
\B.G. Ryder
\
\
\11/82
\In this paper we present @b[ACINCF] and @b[ACINCB], incremental
update algorithms for forward and backward data flow problems,
which are based on a linear equations model of Allen/Cocke interval
analysis [Allen 77, Ryder 82]. We have studied their performance on a
robust structured programming language @i[L]. Given a set of
localized program changes in a program in @i[L], we can identify a
@i[priori] the nodes in its flow graph whose corresponding data flow
equations will be affected by the changes. We can characterize these
affected nodes by their corresponding program structures and their
relation to the original change sites.
\*
DCS-TR-121
\12/72
\"Finding the Two-Core of a Tree"
\Ronald I. Becker
Yehoshua Perl
\
\
\12/82
\The 1-core of a graph is a path minimizing the sum of the distances
of all vertices of the graph from the path. A linear algorithm for
finding a 1-core of a tree was presented by Morgan and Slater. The
problem for general graphs is NP-Hard.
A 2-core of a graph is a set of two paths minimizing the sum of the
distances of all vertices of the graph from any of the two paths. We
consider both cases of disjoint paths and intersecting paths for a
tree.
Interesting relations between 1-core and 2-core of a tree are found.
These relations imply efficient algorithms for finding the 2-core.
The complexity of the algorithms is 0(|V|.d(T)) where d(T) is the
number of edges in the diameter of the tree. These algorithms are
applicable for routing highways in a system of roads.
A w-point core is a path minimizing the sum of the distances of all
vertices of the graph from either the vertex w or the path. A linear
algorithm for finding a w-point core of a tree is presented. It is
applied as a procedure for the previous algorithms.
\*
DCS-TR-122
\12/82
\"Circuit Partitioning with Size and Connection Constraints"
\Yehoshua Perl
Marc Snir
\
\
\12/82
\The problem of partitioning a circuit into subcomponents with
constraints on the size of each subcomponent and the number of
external connections is examined. While this problem is shown to be
NP complete even for very restricted cases, a pseudo-polynomial
dynamic programming algorithm is given for the case where the circuit
has a tree structure.
\*
DCS-TR-123
\2/83
\"The Bitonic and Odd-Even Networks are more than Merging"
\Y. Perl
\
\
\2/83
\The known bitonic and odd-even merging networks are reinvestigated.
For both networks the following results are obtained:
The input vectors sorted by the network are characterized. Those
vectors are recursively balanced for some definition of balance. The
set of those vectors is much larger than the set of vectors known to
be sorted by the network. The output vectors obtainable by applying
the network to an arbitrary input vector are also characterized.
Those vectors satisfy recursive dominance for some definition of
dominance.
\*
DCS-TR-124
\2/83
\"Efficient Implementation of a Shifting Algorithm"
\Y. Perl and U. Vishkin
\
\
\2/83
\An efficient implementation of the shifting algorithm (BPS]) for
min-max tree partitioning is given. The complexity is reduced from
O(Rk@+[3]) + kn) to O(Rk(k + logd) + n) where a tree of n vertices,
radius of R edges, and maximum degree d is partitioned into k+ 1
subtrees. The improvement is mainly due to the new junction tree data
structure which suggests a succinct representation for subsets of
edges, of a given tree, that preserves the interrelation between the
edges on the tree.
\*
DCS-TR-125
\3/83
\"Optimum Split Trees"
\Y. Perl
\
\
\3/83
\A split tree is a special kind of a binary search tree introduced by
Sheil [S]. He conjectured that constructing an optimum split tree is
an intractable problem since there is a difficulty in applying the
dynamic programming technique. We realize that the difficulty arise
since top down decisions are required while applying the bottom up
dynamic programming technique.
We demonstrate that it is possible in this case to overcome such a
difficulty, and present a polynomial algorithm for constructing an
optimum split tree. This algorithm incorporates top down decisions
into a dynamic programming procedure similar to Knuth's [K2] algorithm
for constructing an optimum binary search tree. An improved algorithm
of complexity 0(n4) is finally presented. A modification for the case
that equiprobable keys are permitted is discussed.
\*
DCS-TR-126
\3/83
\"Heuristics for Finding a Maximum Number of Disjoint Bounded Paths"
\D. Ronen
\Y. Perl
\
\
\4/83
\We consider the following problem: Given an integer k and a network
G with two distinct vertices s and t, find a maximum number of vertex
disjoint paths from s to t of length bounded by k.
In a recent work [IPS] it was shown that for length greater than four
this problem is NP-Hard. In this paper we present a polynomial
heuristic algorithm for the problem for general length. The algorithm
is proved to give optimal solution for length less than five.
Experiments show very good results for the algorithm.
\*
DCS-TR-127
\3/83
\"THE BALANCED SORTING NETWORK"
\M. Dowd
Y. Perl
L. Rudolph
M. Saks
\
\
\3/83
\This paper introduces a new sorting network, called the @u[balanced
sorting network]. To sort input vectors of size n=2@+[k] the network
requires 0([lg n]@+{2}) time and uses n(lg n)@+[2]/2 comparators, which
are comparable to the bounds for the well known odd even and bitonic
networks of Batcher [Ba]. On the other hand our network has certain
advantages over these two networks. In particular the balanced
sorting network consists of a sequence of k @u[identical] blocks called
@u[balanced merging networks]. Thus implementations of the network as a
hardware network or on the shuffle exchange interconnection model have
some advantages over the corresponding implementations of the other
networks mentioned above.
\*
-------
Technical Details
Message-ID:
<8601240707.AA14143@ucbvax.berkeley.edu>Path:
arc1-ca.pugleaf.net!utzoo!decvax!ittatc!dcdwest!sdcsvax!ucbvax.berkeley.edu!daemonShow Full Headers
Complete Article Headers
Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.berkeley.edu.BERKELEY.EDU Path: arc1-ca.pugleaf.net!utzoo!decvax!ittatc!dcdwest!sdcsvax!ucbvax.berkeley.edu!daemon From: daemon@ucbvax.berkeley.edu.BERKELEY.EDU (The devil himself) Newsgroups: mod.techreports Subject: (none) Message-ID: <8601240707.AA14143@ucbvax.berkeley.edu> Date: Fri, 24-Jan-86 02:07:33 EST Article-I.D.: ucbvax.8601240707.AA14143 Posted: Fri Jan 24 02:07:33 1986 Date-Received: Sat, 25-Jan-86 04:57:42 EST Organization: The ARPA Internet Lines: 2358 Approved: techreports@smu.csnet