Article View: mod.techreports
Article #3(none)
From: UNIX Copy
Date: Fri, 24 Jan 1986 08:15
Date: Fri, 24 Jan 1986 08:15
2510 lines
102991 bytes
102991 bytes
>From smu!leff Wed Jan 22 19:15:07 1986 remote from convex
Received: by convex (4.12/4.7)
id AA24456; Wed, 22 Jan 86 19:15:07 cst
Received: by csevax.smu (4.12/4.7)
id AA25515; Wed, 22 Jan 86 18:26:44 cst
Date: Wed, 22 Jan 86 18:26:44 cst
From: convex!smu!leff (Laurence Leff)
Message-Id: <8601230026.AA25515@csevax.smu>
To: ucbvax!post-techreports
Subject: Rutgers Tech Reports
DCS-TR-128
\6/83
\Solving the General Consistent Labeling (or Constraint Satisfaction)
Problem: Two Algorithms and their Expected Complexities
\Bernard Nudel
\
\
\6/83
\The Consistent Labeling Problem is of considerable importance in
Artificial Intelligence, Operations Research and Symbolic Logic. It
has received much attention, but most work has addressed the
specialized @i[binary] form of the problem. Furthermore, none of the
relatively few papers that treat the general problem have dealt
analytically with the issue of complexity. In this paper we present
two algorithms for solving the @i[general] Consistent Labeling Problem
and for each of these the expected complexity is given under a simple
statistical model for the distribution problems. This model is
sufficient to expose certain interesting aspects of complexity for the
two algorithms. Work currently in progress will address more subtle
aspects by extension to more refined statistical models.
\*
DCS-TR-129
\4/83
\FOURIER METHODS IN COMPUTATIONAL FLUID AND FIELD DYNAMICS
\R. Vichnevetsky
\
\
\4/83
\This paper is a review, with examples, of those areas where the
theory of Fourier transforms has played a role in the development of
computational methods in fluid and field dynamics. These may be
separated into (i) the development of computing algorithms using
Fourier transforms and (ii) the analysis of standard finite difference
and finite element algorithms by Fourier methods.
Recent results in the analysis of spurious reflection phenomena at
computational boundaries of fluid flow simulation, which invoke the
theory of wave propagation and the concept of group velocity are
given.
\*
DCS-TR-130
\4/83
\"Design and Analysis of Protection Schemes Based on the Send-Receive
Transport Mechanism" (Thesis)
\Ravinderpal Singh Sandhu
\
\
\4/83
\In a protection mechanism based on authorization, the ability of a
@b[subject] (i.e., a user or a process) to operate on the system is
determined by @b[privileges] in its @b[domain]. A mechanism for
transport of privileges must accommodate a variety of policies, while
permitting analysis of the privileges which a given subject might
obtain. The @b[send-receive transport mechanism] was designed by
Minsky with these objectives in mind. In this mechanism, a transport
operation is explicity authorized at both the source and destination,
and the authorization is selective with respect to which privileges
can be transported.
Here we study a restricted version of this mechanism. Under our
restrictions a protected system is designed in two stages. Firstly, a
@b[protection scheme] is defined by specifying the values of certain
parameters, which determine the static component of every subject's
domain. Secondly, the @b[initial state] is defined by specifying the
dynamic component of every subject's domain. This state then evolves
as permitted by the protection scheme.
We formulate the @b[flow-analysis problem] which is concerned with
determining a bound on the authorization for transport of privileges,
given a protection scheme and an initial state. We develop techniques
for deriving and improving the desired bound. The major complication
in doing so is the create operation, which permits the protection
state to evolve in an unbounded manner. We investigate conditions
which enable us to ignore the create operation. We also investigate
conditions under which the initial authorization for transport of
privileges remains invariant in every derived state.
We study additional analysis issues in the context of sub-classes of
our design framework. The questions raised in such detailed analysis
depend on the structure of these sub-classes.
\*
DCS-TR-131
\7/83
\"Incremental Data Flow Analysis Algorithms"
\Marvin C. Paull
\Barbara G. Ryder
\
\
\7/83
\ACINCF and ACINCB are two incremental update algorithms for global
data flow analysis which are based on our linear equations models of
Allen/Cocke interval analysis. 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 @i[a
priori] the nodes in its flow graph whose corresponding data flow
equations may be affected by the changes. We can characterize these
affected nodes by their corresponding program structures and their
relation to the original change sites, and do so without actually
performing the incremental uipdate algorithm. Our results can be
refined to characterize the reduced equations affected when the
structured loop exit mechanisms are used singly or together, thereby
relating the richness of programming language usage to the ease of
incremental updating.
\*
DCS-TR-132 -(Revised: October, 1983)
\8/83
\"HIGH ORDER NUMERICAL SOMMERFELD BOUNDARY CONDITIONS: THEORY AND EXPERIMENTS"
\R. Vichnevetsky
E.C. Pariser
\
\
\8/83
\We develop high-order, non-reflecting boundary equations for a
semi-discrete approximation of the simple (hyperbolic) advection
equation U@-[1] + cU@-[x] = 0. These boundary equations are based on
a discrete interpretation of Sommerfeld's radiation condition for a
second order wave equation which is associated with the semi-discrete
equations. The performance of these schemes is expressed by an exact
measure of the energy reflected at the boundary. For low order cases,
the discrete Sommerfeld boundary equations are identical with the
standard finite difference equations, but for high orders of
approximation (starting with 4 points), the discrete Sommerfeld
schemes differ from standard finite differences. It is shown, and
verified experimentally, that the discrete Sommerfeld schemes are
optimal, in the sense that they produce the least amount of reflected
energy.
Moreover, it is known theoretically, and we verify experimentally,
that the reflected energy remains invariant when the semi-discrete
equations are time-discretized with the trapezoidal (Crank-Nicolson)
method. The corresponding fully discrete boundary equations are thus
also optimal in the sense that they minimize the reflected energy.
\*
DCS-TR-133
\7/83
\"Singular Integral Equations-The Singular Value Decomposition of the
Gauss-Chebyshev and Lobatto-Chebyshev Matrices"
\A. Gerasoulis
\
\
\8/83
\A closed form expression for the singular values and singular vectors
of the Gauss-Chebyshev and Lobatto-Chebyshev matrices is obtained and
the singular value decomposition for both matrices is derived. We use
the singular value decomposition to investigate the convergence of an
iterative method applied in the solution of Singular Integral
Equations of Cauchy type. We show that this iterative method
converges only under very restrictive conditions.
\*
DCS-TR-134
\4/83
\"Knowledge Representation in Mathematics a Case Study in Graph Theory"
\S. L. Epstein
\
\
\9/83
\In this dissertation we present our work on representational
languages for graph theory. We have shown that a knowledge
representation can be structured to provide both expressive and
procedural power.
Our major research contributions are three. First, we have defined
representations of infinite sets and recommended that mathematical
concepts be considered as sets of objects with relations among them.
Second, we have demonstrated how a carefully controlled hierarchy of
representations is available through formal languages. Third, we have
employed a recursive formulation of concepts which enables their
application to many of the behaviors of a research mathematician.
Two major families of representations are described: edge-set
languages and recursive languages. The edge-set languages have finite
expressive power and an interesting potential for hashing digraphs,
characterizing classes of graphs and detecting differences among them.
The recursive languages have extensible expressive power and
impressive procedural power. Recursive languages appear to be an
excellent implementation technique for artificial intelligence
programs in mathematical research.
Our results enable us to complare the complexity of mathematical
concepts (via floors). Concepts represented in our languages can be
inverted (to test for the presence of a property) and merged (to
combine properties). Conjectures are available through simple search,
and most theorems easily proved under the representation.
\*
DCS-TR-135
\10/83
\"Clustering and Domination in Perfect Graphs"
\D.G. Corneil
\Y. Perl
\
\
\10/83
\A @i[k]-cluster in a graph is an induced subgraph in @i[k]-vertices which
maximizes the number of edges. Both the @i[k]-cluster problem and the
@i[k]-dominating set problem are NP-complete for graphs in general. In
this paper we investigate the complexity status of these problems on
various subclasses of perfect graphs. In particular, we examine
comparability graphs, chordal graphs, bipartite graphs, split graphs,
cographs and @i[k]-trees. For example, it is shown that the @i[k]-cluster
problem is NP-complete for both bipartite and chordal graphs and the
independent @i[k]-dominating set problem is NP-complete for bipartite
graphs. Furthermore, where the @i[k]-cluster problem is polynomial we
study the weighted and connected versions as well. Similarly we also
look at the minimum @i[k]-dominating set problem on families which have
polynomial @i[k]-dominating set algorithms.
\*
DCS-TR-136
\11/83
\R. Vichnevetsky
\"THE ENERGY FLOW EQUATION"
\
\
\11/83
\An equation which describes the flow of energy in energy conservative
semi- and full discretizations of hyperbolic equations is derived.
While the form of this equation for semi-discretizations verifies
known principles of group velocity and wave propagation in periodic
structures, its form and strict applicability to
discrete-space-discrete-time systems like those resulting from the
full discretization of hyperbolic equations are new results.
\*
DCS-TR-137
\12/83
\"INVARIANCE THEOREMS CONCERNING REFLECTION AT NUMERICAL BOUNDARIES"
\R. Vichnevetsky
\
\
\12/83
\In the numerical approximation of hyperbolic equations, outflow
boundaries are in general not transparent, and they create spurious
reflection. A useful measure of this is given by the energy (or usual
sum of squares) of the reflected solution in response to an arbitrary
solution which originates from within the computing domain.
We prove, in that respect, a somewhat unexpected property: Namely
that for those full discretizations which are obtained by applying to
a space-discretization of the problem an energy conservative discrete
time-marching method, the energy reflected at the boundary is
independent of which time-marching method is used, of the value of
delta-t, and is strictly equal to the reflected energy in the
semi-discrete case. This is also verified by numerical experiments.
Optimal boundary equations may be defined in the semi-discrete case of
those which maximize the rate of convergence to zero of the reflected
energy when h->0. A corollary of the preceding result is that those
boundary equations remain optimal, in the same sense, when used in an
energy conservative full discretization.
\*
DCS-TR-138
\12/83
\"A Finite Element Method for Hyperbolic Equations"
\G. Richter
\
\
\12/83
\
\*
*
DCS-TR-139
\4/84
\"Exploring the Structure of Incremental Algorithms"
\Berman
Paull
Cheng
\
\
\8/84
\A study of the general properties of incremental algorithms is
presented. First, it is shown that within certain limitations it is
not possible for an incremental algorithm to be of complexity less
than @i[1/n] of that of the best non-incremental algorithm for any
given function. Next we describe a model for incremental algorithms
based on a generalization of finite state machines. It is
demonstrated that all finite state machines have either constant or
linear complexity, and this is extended to a subclass of incremental
algorithms. Then the requirements for machines with good incremental
algorithms are discussed, and two classes are presented, one which can
be updated in constant time, and one in @Sqrt[n] time, when averaged
over a sequence of changes.
\*
DCS-TR-140
\1/84
\"A Unified Model of Elimination Algorithms"
\B.G. Ryder
M.C. Paull
\
\
\1/84
\A data flow algorithm is one which gathers information about the
deifnition and use of data in a program or a set of programs. A
unified model of a family of data flow algorithms called elimination
methods is presented. The algorithms are characterized by the manner
in which they solve the systems of linear equations which describe
data flow problems of interest. These implementation independent
descriptions of the algorithms facilitate comparisons among them and
illustrate the sources of worst case complexity improvement. This
tutorial is valuable as a study in algorithm design and improvement;
it presents a new view of these algorithms and their interrelations.
\*
DCS-TR-141
\2/84
\"On Scheduling the Construction of a Treelike Communication Network"
\A. Israeli
Y. Perl
\
\
\2/84
\In a treelike communication network, transmission equipment is
required for the internal vertices. We consider optimal schedules for
the construction of the edges of the network, minimizing the cost of
hiring the transmission equipment during the construction process.
Properties of optimal schedules are investigated. It is shown that an
optimal schedule is constructed in three parts: The initial matching,
the stars part and the residual subgraph. Rules concerning the
construction of each one of the parts are presented. Efficient
algorithms are presented for some special cases of paths of stars.
\*
DCS-TR-142
\4/84
\"Towards a Flexible User Interface to Relational Database Systems:
Processing Simple Second Order Queries"
\T. Imielinski
D. Rozenshtein
\
\
\4/84
\In this paper, we present a mechanism for answering simple second
order queries of the form "retrieve connection between attributes A
and B." By "connection between A and B" we mean any and all
meaningful relationships that can be established between A and B in a
given database.
What gives our queries their second order nature is the fact that
semantics of connections is independent of a particular set of
predicates comprising the database scheme. The answers to them,
however, depend on which relationships are considered meaningful;
this, in turn, depends on the particular structure of the database
scheme and, also, on additional semantic information carried by roles.
While we can treat our queries as intentionally second order queries
directed at the database instance, we can also treat them as
incompletely specified queries posed by a user whose knowledge of the
data base structure is partial.
In this paper, we present a formal characterization of "meaningful
relationships," present algorithms for computing connections, and
describe how our method can be extended to sets containing any number
of attributes.
\*
DCS-TR-143
\5/84
\"Propation and Reflection in Discrete-Space-Discrete-Time Structures"
\R. Vichnevetsky
\
\
\5/84
\We describe the essential mathematics that are to be invoked to
arrive at a coherent description of energy conservation, propagation
and reflection in discrete-space-discrete-time structures. These are
the structures which occur when hyperbolic equations are approximated
numerically on a regular mesh in space-time.
The combined use of discrete Fourier Transforms and energy measures
produces a set of new and particularly elegant results relating to
spurious reflection at computational boundaries. These results are
sketched in this paper.
\*
DCS-TR-144
DCS-TR-145
DCS-TR-146 6/84 S. Kedar-Cabelli Analogy - From a Unified
NOT RECEIVED YET Perspective
6/29/84
DCS-TR-147 9/85 B. Kalantari "An Algorithm for large-scale
REVISED J.B. Rosen global minimization of
NOT RECEIVED YET linearly constrained concave
quadratic functions"
DCS-TR-148
\9/84
\"Penalty Formulation for Zero-One Programming"
\B. Kalantari
J.B. Rosen
\
\
\9/84
\Raghavachari has shown the equivalence of zero-one integer
programming and a concave quadratic penalty function for a
sufficiently large value of the penalty. A lower bound for this
penalty was found by Kalantari and Rosen. It was also shown that this
penalty could not be reduced in specific cases. We show that the
results generalize to the case where the objective function is any
concave function. Equivalent penalty formulation for non-concave
functions is also considered.
\*
DCS-TR-149
\11/84
\"Algorithms and Complexity for a statistical problem.
Minimum median residual fitting"
\J.M. Steele
W.L. Steiger
\
\
\11/84
\Given n points {(x@-[1],y@-[i])} in the plane we study the problem of
fitting the minimum median squared residual (@b[MM@+{2}R]) line. This
involves the study of the function f(@g[a],@g[b]) = median (|y@-[y] -
(@g[a] + @g[b] x@-[i])|); it is piecewise linear and can have a
quadratic number of local minima. Several algorithms that locate a
minimizer of f are presented. The best of these has time complexity
O(n@+[3]) in the worst case. Our most practical algorithm appears to
be one which has worst case behavior of only O(n@+[3] log(n)), but
which we conjective to have expected time complexity O((n
log(n))@+[2]). Generalizations to k dimensions arae mentioned.
\*
DCS-TR-150
\11/84
\"Modular Verification of Communicating Sequential Processes"
\E.A. Akkoyunlu
R.M. Nemes
\
\
\11/84
\The semantics of communication in a distributed computing environment
without shared objects are investigated from the viewpoint of
modularity and hierarchial system structure. Communicating Sequential
Processes (CSP), Hoare's language for parallel programming, is
modified and expanded to support process modularity and hierarchial
structure using a port construction. A formal axiomatic verification
methodology for partial correctness is developed that extends the
Hoare axiomatic proof methodology for sequential (nonparallel)
programs to CSP-like programs, without resort to global invariants.
Hierarchial structure and modularity are fully supported within the
proof system. Processes are verified against an abstract entity, the
interface, thereby achieving a formal notion of process specification
and plug-compatibility. Alongside maintenance to a system is
maintenance to its correctness proof, the two evolving side by side in
an isomorphic fashion. The formalism is broadened further to include
shared ports by the introduction of a universal assertion termed
Kirchhoff's Law. Several examples are provided that demonstrate the
methodology, including a modular proof of the generic single-entry,
multiple-user CSP subroutine process.
\*
DCS-TR-151
\1/85
\"The Mathematics of
Energy Propagation in
Numerical Approximations
of Hyperbolic Equations"
\Vichnevetsky
\
\2/85
\This paper is mostly a review and discussion of tools: there are
errors in the numerical approximations of hyperbolic equations which
manifest themselves by the appearance of spurious waves. It is not
until one introduces in the analysis the concepts of energy and group
velocity (which originated in physics) that a reasonably complete
analytic description of those phenomena can be reached.
To produce results (in particular those concerning energy) which are
consistent with the mathematics of numerical analysis, one must select
carefully the setting and the tools which are used. It is on this
selection process that the emphasis of the following is placed.
\*
DCS-TR-152
\1/85
\"Tensor Form of Numerical
Diffusion in Multi-Dimensional Flow Computations"
\Vichnevetsky
Venkatakrishnan
\
\
\2/85
\The numerical approximation of hyperbolic equations describing
advection often introduces spurious diffusion. In the two and three
dimensional case, this spurious diffusion is anisotropic, and may be
described by a matrix or a tensor. After briefly describing the
corresponding theory (a detailed derivation is given elsewhere [9]),
we show experimental results which verify the theoretical results.
\*
DCS-TR-153
\9/84
\"CK-LOG, A Calculus for Knowledge Processing in Logic"
\C.V. Srinivasan
\
\
\2/85
\This paper introduces the principal concepts in the organization and
operation of the logic based knowledge processing system, called
CK-LOG (A Calculus for Knowledge in LOGic). CK-LOG uses the @i[frame]
based system MDS (the Meta Description System) for knowledge
representation and for modelling world states. It uses an inference
engine based on @i[Natural Deduction] for stating and solving
problems.
\*
DCS-TR-154
\3/85
\"Proving Relative Lower Bounds for Incremental Algorithms"
\A. Michael Berman
Marvin C. Paull
Barbara G. Ryder
\
\
\6/85
\A general, powerful method that permits simple proofs of @b[relative
lower bounds] for incremental update algorithms is presented. This
method is applied to derive a hierarchy of relative incremental
complexity, which classifies functions by relative lower bounds. We
demonstrate our technique by bounding a number of incremental
algorithms drawn from various domains. The method described expands
upon work by Paull, Berman, and Cheng [7] and generalizes a result of
Even and Gazit [2]. Our results have interesting implications with
respect to the optimality of an incremental algorithm previously
developed by Ryder in [9, 10]. We also show that for certain graphs,
Frederickson's update algorithm for minimum spanning tree is nearly
optimal [3]. Perhaps most importantly, the proof method and hierarchy
suggest which type of problems are likely to yield good incremental
algorithms (i.e., of lower complexity) and which cannot be improved
by an incremental approach.
DCS-TR-155
\3/85
\"Integrity Checking for Multiple Updates"
\Hsu Arding
Tomasz Imielinski
\
\
\3/85
\In this paper we generalize methods for fast checking of integrity
constraints to deal with multiple (multiple-tuple and multiple-range)
updates. This enables us to consider practically important cases when
updates are neither restricted to single range (relation) nor to
single tuple and could be grouped in possibly complex transactions.
We provide simplification method for arbitrary transactions, and also
for arbitrary constraints expressed in prenex normal form in
relational tuple calculus with no restrictions on the number of
variables ranging over the same relation. Based on the prefix of a
constraint, our simplification algorithms transform the constraint
into an AND-OR combination of simpler constraints which are easier to
check. The analysis of certain patterns in the prefixes of
constraints enables us to conclude when for a given type of updates no
simplification is possible at all and when a significant improvement can
be achieved.
In effect we can recommend this method as a fast tool for a possibly
preliminary but fast simplification of a constraint when not much of the
structure of a transaction (update) is known. In case further
simplification is needed, one must look for methods requiring more
information about updates and constraints.
\*
DCS-TR-156
\3/85
\"Piecewise-Polynomial Quadratures for Cauchy Singular Integrals"
\Apostolos Gerasoulis
\
\
\3/85
\In this paper we propose piecewise-polynomial methods for the
approximation of Cauchy principal value integrals and develop a
simple, efficient and numerically stable algorithm for the evaluation
of the weights of the resulting piecewise-polynomial quadratures. We
present two examples to illustrate the advantages of these quadratures
versus the Gauss-Jacobi quadratures.
\*
DCS-TR-157
\4/85
\"Communication Denial in CSP
\Richard. M. Nemes
\
\
\4/85
\In Communicating Sequential Processes CSP), Hoare's language for
concurrent programming using synchronous message-passing,
nondeterministic process synchronization is expressed by including I/0
commands in the guards of guarded commands. When the guards of a
repetitive command contain only I/0 commands - a common paradigm
occurring in many well-known problems (producer-consumer, for example)
- then loop termination is controlled solely by the termination of
addressed processes, the so-called distributed termination convention
(DTC). If loop termination is to be controlled by external processes
without resorting to DTC, then additional guarded commands and boolean
flags are required. The result is an excessively complex loop with
diminished readability.
In this paper we explore a new communication primitive, the i[DENY]
command, that causes false evaluation of a matching I/0 command
contained in a loop guard. The results are loops with the clarityy of
DTC, but with more explicit control structuring than DTC. Artificial
flag mechanisms and extra guarded commands are avoided. We describe
the formal proof-rule semantics of the @i[DENY] command and show its
integration into the modular proof system developed by the author.
We show how the establishment of loop postconditions is simplified.
\*
DCS-TR-158
\7/85
\"Incremental Algorithms for Software Systems"
\B. G. Ryder
\
\
\7/85
\This report is a 2 year NSF research proposal in the area of
incremental algorithms for analyzing software systems. The systems of
interest can be characterized as large and complex, in the sense that
they are written and maintained by many people. The algorithms we are
designing will enable people to alter the intermodular structure of
such systems and @i[a prior] see the side effects of such changes.
\*
DCS-TR-159
\8/85
\"Applicability of Incremental Iterative Algorithms"
\T. Marlowe
M.C. Paull
B.G. Ryder
\
\
8/85
\In computer science there has been much interest in iteration as a
procedure for obtaining the solution of a system of equations. The
applicability of iteration does not depend strongly on the form or
properties of the system of equations. Its use ranges from solution
of numerical equations to data-flow analysis. Also the problem of
finding incremental algorithms which adjust a solution to a small
change in parameters has received much attention recently and is of
particular importance for large problems such as arise in data-flow
analysis.
In this paper we show that one cannot always continue iterating from a
previous solution after even a small change in parameters; we give
conditions under which it is legitimate to do so. This result follows
a brief discussion of iteration in general.
We consider finding a fixed point, X, by iteration of a monotonic
function, W, on a partially ordered set Q. This differs somewhat from
previous developments in that, beyond monotonicity, W is no further
constrained, Q need not be a semi-lattice and X need not be reachable
by a finite number of iterations.
\*
DCS-TR-160
2/84
\"Knowledge Processing vs Programming: CK-LOG vs PROLOG"
\C.V. Srinivasan
\
\
\9/85
\This paper introduces the concept of knowledge processing as one that
involves both problem solving and learning, and contrasts knowledge
processing in CK-LOG with programming in PROLOG. CK-LOG is a logic
based knowledge processing system just as PROLOG is a logic based
programming system. CK-LOG uses the frame representation system, MDS
for knowledge representation and uses a general theorem proving system
based on natural deduction for problem solving. The theorem proving
system uses the truth maintenance system of MDS to build an evolving
set of partial models during the theorem proving process, and uses
these models to guide its search for proofs. The truth maintenance
system works in three valued logic of T, ? (unknown) and F, which
gives CK-LOG the capability to use model based default reasoning, and
the capability to function effectively in the context of incomplete
knowledge. Knowledge in CK-LOG pertains to a universe which may
consist of objects, actions and time. CK-LOG has the capability to
represent and reason about dynamically changing world states in which
multiple simultaneous actions may occur. The organization, logic and
operation of CK-LOG is discussed here. It is argued that the kinds of
knowledge processing capabilities exhibited by CK-LOG are fundamental
to knowledge processing in general, and it is impossible to
incorporate them into PROLOG.
\*
DCS-TR-161
\"A Note on Unmerging"
\B. Reed, J.S. Salowe, and W.L. Steiger
\
\
\9/85
\In the Summer '85 issue of SIGACT News, N. Santoro enquired about the
space-time complexity of unmerging. Suppose that lists A and B, each
of size n/2, are merged to produce the list L. The problem is to
separate L into A and B in their original order. By studying a
simple, but non optimal merging algorithm, we obtain an unmergng
algorithm which, using extra space 0(k), runs in time 0(nlog@-[k]n).
Thus, given @k[Elementof] > 0, the algorithm can unmerge in linear
time provided 0(n@+[@k{Elementof}]) space is available.
\*
DCS-TR-162
\"Stable Unmerging in Linear Time and Constant Space"
\J.S. Salowe
W.L. Steiger
\
\
\9/85
\In the Summer 1985 issue of SIGACT news, N. Santoro inquired about
the space-time complexity of unmerging. Suppose that two sorted lists
A and B, each of size n/2, are merged to produce the list L. The
problem is to separate L into A and B in sorted order. An optimal
algorithm is presented which unmerges in time 0(n) using 0(1) extra
space, and which is stable.
\*
DCS-TR-163
\9/85
\"Subset Size in Parallel"
\L. Rudolph
W. Steiger
\
\
\9/85
\In this paper we consider the problem of counting and packing the
elements of a subset using a shared memory model of parallel
processing. That is, given a set of n items, (i) compute the
cardinality of the subset of items that satisfy some predicate and
(ii) place all the items in the subset contiguously in the first k
locations of an array, where k is the cardinality. Using n
processors, it is easy to solve this problem in 0(min[k,log(n)])
parallel time. Our solution is a probabilistic algorithm that uses only
k processors and 0(k) storage. With high probability its running time
is logarithmic in k, the size of the subset, so it is independent of
n. The analysis of the expected running time uses a technique which
may be interesting in its own right and might be applicable to the
analysis of other parallel algorithms.
\*
LCSR-TR-8
\8/80
[REVISED 12/81]
\"Finite Differencing of Computable Expressions"
\R. Paige
S. Koenig
\
\
\1/82
\One of the fundamental problems of protection is the exercise of
control over the movement of rights in a system. The Take-Grant
model, which captures certain essential aspects of several popular
protection schemes, suffers from a serious limitation in its
implementation of such control: @u(any channel established for the
movement of rights may be reversed). This property limit the
applicability of this model and by implication the protection schemes
which it models. We analyze the nature and ramifications of this
limitation and demonstrate that it is due to the manner in which the
GRANT operation is authorized by the grant right. We propose an
alternative, "Receive-Right" model in which this limitation is
eliminated, thus enabling the implementation of more useful protection
disciplines. The properties of the Receive-Right model are discussed
and results are presented on the analysis of the dynamic behavior of
its protection states.
\*
LCSR-TR-9
\1/81
\(pending)
\R. Paige
\
\
\1/81
\
\*
LCSR-TR-10
(THIS RPT # HAS BEEN CHANGED TO 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.
\*
LCSR-TR-11
\3/81
\"Representations for Reasoniing about Digital Circuits"
\T.M. Mitchell
L. Steinberg
R.G. Smith
P. Schooley
V. Kelly
\
\
\1/82
\We are interested in developing programs that reason about digital
electronic circuits, in order to design, redesign, and debug them.
The first step toward developing such programs is to determine a
useful way of representing the design and operation of circuits. A
useful representation must make apparent the roles of various circuit
components in implementing the overall circuit function, and must
allow a program to reason about the operation of the circuit at
various levels of abstraction. This paper summarizes our efforts to
develop such a representation. This work is closely related to other
AI work on representing plans and on representing and reasoning about
complex physical processes.
\*
LCSR-TR-12
\1980
\"Privileges for Distributed Authorization"
\N. Minsky
\
\
\1/82
\This paper deals with two kinds of authorization policies which we
call "distributed" and "knowledge based" policies. The attempt to
support these policies leads to a deeper understanding of the concept
of privilege, which contributes to the design of more powerful and
more efficient authorization schemes. The specific type of privileges
being proposed in this paper is a simplification of the "Activator",
which is the main privilege used in the Operation Control scheme, and
in the ongoing COINS (Controlled Information System) project in
Rutgers University.
\*
LCSR-TR-13/CBM-TR-137
\6/81
\"Unidirectional Transport of Rights and Take-Grant Control*"
\N. Minsky
A. Lockman
\
\
\1/82
\One of the fundamental problems of protection is the exercise of
control over the movement of rights in a system. The Take-Grant
model, which captures certain essential aspects of several popular
protection schemes, suffers from a serious limitation: it cannot
enforce strictly unidirectional channels for the flow of rights. This
property limits the applicability of this model and therefore that of
the protection schemes which it models. We analyze the nature and
ramifications of this limitation and demonstrate that its root cause
is the fact that a right residing in the sender suffices to authorize
a movement of rights. We propose an alternative, "Take-Receive",
model in which this limitation is eliminated, thus enabling the
implementation of more useful protection disciplines. We prove this
result by analyzing the dynamic behavior of the proposed model.
*This paper is a revision of a report entitled "How to Control
Grants", July 1979.
\*
LCSR-TR-14
\5/81
\"Synergistic Authorization in Database Systems"
\N. Minsky
\
\
\1/82
\We say that an authorization scheme exhibits @i(synergistic effects)
if it allows for the power provided by the union of two privileges to
be larger than the union of the powers of the individual privileges.
This phenomenon where @i(the whole is larger than the sum of its
parts) is shown to be essential for the support of some important
classes of authorization policies, and useful for the optimization of
the enforcement of authorization-based rules. An authorization scheme
which exhibits synergistic effects is introduced and some of its
applications are discussed.
\*
LCSR-TR-15
\7/81
\"Learning Problem-Solving Heuristics through Practice"
\T.M. Mitchell
P.E. Utgoff
B. Nudel
R. Banerji
\
\
\1/82
\We are interested in automatic improvement of problem solving
strategies through practice. A computer program called LEX is
described, which acquires problem solving heuristics in the domain of
symbolic integration. LEX learns heuristics from a sequence of
presented training problems by (1) using available heuristics to solve
the practice problem, (2) analyzing the steps it performed in solving
the problem, and (3) proposing and refining domain-specific heuristics
designed to improve its performance on subsequent problems. We
describe the methods used by LEX, results obtained by the program, and
strengths and weaknesses in the current system.
\*
LCSR-TR-16
\7/81
\"System Design and Programming Methodology for a CAM-based
General-purpose Computer"
\J.S. Hall
\
\
\1/82
\VLSI makes feasible the massive use of content addressable memory in
a general purpose computer. This report presents a design for memory
which is addressable conventionally and by content, and which supports
low-level bit-serial word-parallel algorithms. CAM provides one of
the most easily understood and programmed frameworks for massively
parallel computations. We present a programming methodology for the
use of our design. A programming language, CAML, which provides
higher-level constructs to take advantage of the capabilities of CAM,
is discussed in detail. A number of algorithms from various fields
which demonstrate the generality of the design and the language, and
techniques for transforming algorithms from conventional to CAM-based
structures and methods, indicate the feasibility of the
general-purpose use of CAM.
\*
LCSR-TR-17
(REVISED) - 3/84
\7/81
\"Selective and Locally Controlled Transport of Privileges"
\N. Minsky
\
\
\3/84
\In a system based on authorization, the ability of a subject to
operate on the system is a function of the @i(privileges) that he
possesses. In this paper we introduce and study a mechanism, called
Send-Receive Mechanism, for the @i(transport) of such privileges. The control
provided by this mechanism over the movement of privileges has two
notable properties.
@begin(itemize)
The control is @i(selective), in the sense that it permits the creation
of transport-channels which allow for the movement of only certain
types of privileges and only between certain kinds of subjects.
The control is @i(local), in the sense that every movement of
privileges into and out of the domain of a given subject must be
authorized by privileges already in his domain.
@end(itemize)
We show that the proposed transport mechanism allows one to impose a @i(local
upper bound) on the @i[power] of any given subject. This bound which
is independent of the rest of the system and can, therefore, be viewed
as an @i[intrinsic property of the subject]. The ability to impose
such bounds is considered essential for effective modularization of
computer systems. In addition, the locality of our control has
beneficial @i(global effects) on the flow of privileges. In
particular, it helps remove the undesirable @i(symmetry) of transport,
exhibited by the conventional Take-Grant mechanism.
\*
LCSR-TR-18
\8/81
(forthcoming)
\"Problem Solving in the Meta Description System"
\C.V. Srinivasan
\
\
\1/82
\
\*
LCSR-TR-19
\7/81
\"Notes on Object Centered Associative Memory Organization"
\C.V. Srinivasan
\
\
\1/82
\An associative memeory organization is proposed here that incorporates
features of "pages" and "chapters", which are used to organize the
information in a relational database in a manner that facilitates
efficient evaluation of relational algebra expressions: Set
intersection and union operations are done in one memory access time,
independent of the size of the sets, limited only by the size of the
memory. Join operations and cross products may be done in atmost
three memory accesses for binary relations, and on the average in
3(k/2) memory accesses for k-ary relations, when k > 2. The basic
organizational concepts are briefly described in this memo.
\*
LCSR-TR-20
\10/81
\"Semantic Integrity Transactions in Design Databases"
\Charles M. Eastman
Gilles M.E. Lafue
\
\
\11/82
\This paper views engineering design as a task involving simultaneously
defining and assigning values to a database. Such a database (called
a @i[design database]), represents the artifact being designed
throughout many phases, from early specifications all the way to
manufacturing instructions. This paper examines some of the semantic
integrity requirements of design databases in relation with current
research, and proposes a refinement of the notion of integrity
transaction, i.e., a structure to manage the semantic integrity of a
database without necessarily guaranteeing it all the time. Semantic
integrity is also discussed within the larger framework of confidence
in data values of design databases.
\*
LCSR-TR-21
\SEE LCSR-TR-27
\"Combining Empirical and Analytical Methods for Inferring Heuristics"
\T.Mitchell
\
\
\1/82
\
\*
LCSR-TR-22
\12/81
\"A File Organization Based on Extensible Hashing"
\Richard King
\
\
\1/82
\Direct access secondary storage organization allows a record
corresponding to a given key to be obtained in approximately one
access to secondary storage. Direct access is accomplished by
choosing a hash function, H, that maps a key space, K, into an address
space, A. Usually, the record with a given key, k, can be located in
a single access at address H(k) of secondary storage.
However, a straightforward direct access method has two shortcomings:
@begin(enumerate)
(collision problem) The number of different records mapped to the
same secondary storage address can exceed the available space.
(allocation problem) The amount of space reserved for the file must
be chosen in advance to fit the range size of the hash function.
@end(enumerate)
We propose a novel way to maintain dynamic files efficiently. We
believe that this method has particular relevance to very high level
languages and query languages where sets and maps are important. Our
algorithm will be compared to several other algorithms that have been
proposed to partially overcome the shortcomings mentioned above.
\*
LCSR-TR-23
\12/81
\"A Transformational Framework for Automatic Derived Data
ontrol and its Applications in an Entity-Relationship Data Model"
\Shaye Koenig
\
\
\1/82
\This thesis investigates the specification, implementation and
application of derived data in the context of MADAM, an
entity-relationship oriented, map-based data model/programming
language for database conceptual schema representation and processing.
The data representation and manipulation facilities of MADAM,
described in chapter 2, represent a synthesis of ideas from the areas
of very high level languages, in particular SETL, and the binary
association and entity-relationship approaches to data modeling.
Derived data refers to data that appears to exist in its declared
form, but is actually derived from related data in the database.
Previous approaches to the materialization of derived data have been
based on a global recalculation strategy in which derived data is
recomputed whenever it is referenced. In this thesis we present an
alternative approach in which derived data is explicitly stored and
incrementally maintained. In chapter 3, we describe the definition of
derived data in MADAM; discuss its importance as a means of fostering
logical data independence, providing access control mechanisms, and
supporting semantic relativism; and present a unified framework for
the automatic maintenance of derived data. This framework is based on
the transformational techniques of finite differencing in which
repeated costly computations are replaced by more efficient
incremental counterparts. In addition to the importance of our
incremental maintenance approach for supporting alternative views of
the same data, additional applications of our incremental maintenance
approach to the implementation of summary data, integrity control, and
triggers are discussed in chapter 4.
\*
LCSR-TR-24
\12/81
\The Case for a SetL Based Query Language
\Ravinderpal S. Sandhu
\
\
\1/82
\Lacroix and Pirotte [8] formulated sixty-six queries in nine different
query languages for the relational data model. We augment their study
by formulating these queries in a SETL [6, 9] based query language.
We emphasize the functional notation of SETL and transform a
relational schema into SETL declarations so as to exploit this aspect
of SETL. We also propose additional dictions in SETL for convenience
in query formulation.
\*
LCSR-TR-25
\3/82
\"AI Research at Rutgers"
\Tom M. Mitchell
\
\
\3/82
\Current research at Rutgers covers a broad range of AI concerns--from
the development of expert systems in a variety of domains, to the
study of basic issues of representation and inference. This report
provides summaries of many of the current research projects.
\*
LCSR-TR-26
\3/82
\"Semantic Integrity Dependencies and Delayed Integrity Checking"
\Gilles M.E. Lafue
\
\
\4/82
\This paper's approach to semantic integrity management is that in an
integrity constraint, some variables may be operated on in order to
maintain the constraint, while others may be declaired unaffected by
it. This defines integrity dependencies between variables. Various
examples of integrity dependencies and their meanings are discussed. In
addition to corresponding to real world practice, integrity
dependencies improve the efficiency of checking constraints. This is
achieved by delaying the checking (and maintenance) of data which
depends on, but does not affect, the data currently operated on. It
also gives delayed checking and maintenance a chance to be performed
in parallel with applications. Simulation results are presented to
support this claim.
\*
LCSR-TR-27
\4/82
\"Toward Combining Empirical and Analytical Methods for Inferring Heuristics"
\T.M. Mitchell
\
\
\4/82
\Inferring problem solving heuristics from examples of worked out
solutions is one kind of generalizing from examples. A spectrum of
techniques for this generalization problem is considered, ranging from
purely empirical, data-driven methods, to purely deductive, analytic
methods. It is argued that a combination of empirical and analytical
methods is appropriate for inferring heuristics. One way of combining
empirical and analytical mechanisms for inferring generalizations is
suggested and illustrated for the task of inferring search heuristics
for symbolic integration.
\*
LCSR-TR-28
\5/82
\"Data Base Management Systems and Expert Systems for CAD"
\Gilles M.E. Lafue and Tom M. Mitchell
\
\
\5/82
\This paper examines some issues that Data Base Management Systems
(DBMS) and Expert Systems (ES) begin to share, or will probably share
soon. This convergence is based on the observation that DBMS's take
more active control of database semantic integrity, and ES's are faced
with growing amounts of data to manage. Furthermore, this convergence
is reinforced by applications in Computer-Aided Design. The issues
discussed concern data/knowledge representation and data manipulation
control.
/*
LCSR-TR-29
\9/82
\"Localization of Power in Software Systems"
\N. Minsky
\
\
\9/82
\This paper proposes a technique for what we call @i(localization of
power) in computer systems, which can be viewed as a generalization of
such linguistic disciplines as @i(scope rules, strong typing) and
@i(data-abstraction). Although the proposed technique is conceptually
based on the theory of protection, it is presented as a rather simple
extension of the package construct of the Ada language. This
technique is expected to be beneficial for software engineering in
several ways. In particular:
@begin(enumerate)
It facilitates reasoning about large scale systems, by allowing one to
ignore most of the details of the system when reasoning about specific
aspects of it.
It provides us with a generalization of the conventional concept of
data-abstraction, by allowing the formation of several different
abstractions for the same type of objects, and by supporting
"interactions" between the abstractions of different types.
It allows us to provide parts of a system with a certain ability to
@i(control) the activity of the rest of it.
It supports a broad spectrum of policies for the design and management
of large scale, evolving systems.
@end(enumerate)
\*
LCSR-TR-30
\7/82
\"The Critter System: Analyzing Digital Circuits by Propagating
Behaviors and Specifications"
\Van E. Kelly
Lou I. Steinberg
\
\
7/82
\CRITTER is a system that reasons about digital hardware designs,
using a declarative representation that can represent components and
signals at arbitrary levels of abstraction. CRITTER can derive the
behaviors of a component's outputs given the behaviors of the inputs,
it canderive the specifications a component's inputs must meet in
order for some given specifciations on theoutputs to be met, and it
can verify that a given signal behavior satisfies a given
specification. By combining these operations, it evaluates both the
correctness and the robustness of the overall design.
\*
LCSR-TR-31
\9/82
\"Learning by Experimentation: Acquiring and Modifying
Problem-Solving Heuristics"
\T.M. Mitchell,
P.E. Utgoff,
R. Banerji
\
\
\This chapter concerns learning heuristic problem solving strategies
through experieince. In particular, we focus on the issue of learning
heuristics to guide a forward-search problem solver, and describe a
computer program called LEX, which acquires problem solving heuristics
in the domain of symbolic integration. LEX acquires and modifies
heuristics by iteratively applying the following process: (1) generate
a practice problem, (2) use available heuristics to solve this
problem, (3) analyze the search steps performed in obtaining the
solution, and (4) propose and refine new domain-specific heuristics to
improve performance on subsequent problems. We describe the methods
currently used by LEX, analyze strengths and weaknesses of these
methods, and discuss our current research toward more powerful
approaches to learning heuristics.
\*
LCSR-TR-32
\10/82
\"Semantic Integrity Management of Databases: A Survey"
\Gilles M.E. Lafue
\
\
\10/82
\This is a survey of the state-of-the-art in research on management of
database semantic integrity with an emphasis on automatic integrity
checking. About half a dozen of the most significant approaches are
considered. It is illustrated how these approaches use the major
principles for reducing the cost of automatic integrity checking,
namely, compile-time selection of the constraints to check after
database updates, compile-time simplification of constraints, and use
of redundant data.
\*
LCSR-TR-33
\10/82
\"Some New Sequencings of Groups"
\M. Dowd
\
\
\11/82
\Several new results concerning sequencings of groups are obtained. We
study the classification of sequencings, analyzing their possible
symmetries under automorphisms of the group. We construct some large
families of sequencings of the cyclic group, and show that the
dihedral groups of order 8k+2 are sequenceable. Finally we extend the
list of known sequenceable groups by computer to include the
non-Abelian groups of order 16 and S@-[4].
\*
LCSR-TR-34
\10/82
\"Isomorphism of Complete Sets"
\M. Dowd
\
\
\11/82
\We show that the linear space many one complete sets are linear space
isomorphic; that the polynomial time complete sets are polynomial time
one-one equivalent; and that these facts holds for the sets complete
for certain complexity classes. We show that if the polynomial time
complete sets are not polynomial time isomorphic then P NP. We also
show that linear space one-one equivalence implies linear space
isomorphism.
\*
LCSR-TR-35
\10/82
\"Forcing and the P Hierarchy" (Preliminary Version)
\M. Dowd
\
\
\11/82
\We introduce the notion of a generic oracle, and show that generally
speaking if two relativized complexity classes can be separated by
some oracle then they are separated by every generic oracle. We also
show that if the hierarchy collapses it does so with respect to any
sparse oracle.
\*
LCSR-TR-36
\1182
\"FOCUSER: A Strategic Interaction Paradigm for Language Acquisition (Thesis)
\Donald E. Smith
\
\
\1/82
Acquisition tasks in which the presentation of information to a learning
system (LS) is controlled by a motivated, intelligent presenter are considered.
Techniques are presented that explicitly deal with the structure and strategy
of the presentation. These techniques make use of a layered decision mechanism
that considers the presented information at successive levels of detail. The
first level determines the strategies being employed by the presenter; the
second level, the focus communicated by the presentation; and the last
determines a representation for the acquired knowledge.
The use of strategic techniques within an acquisition task is shown to
increase the acquisition efficiency of LS's whose inputs are constructed by
intelligent presenters while not requiring that the presenter have in-depth
knowledge of the LS.
The use and workings of these techniques are exemplified by a LS named FOCUSER that acquires language for a blocks world domain. The strategic features
employed by FOCUSER and the resultant benefits to the acquisition task, as
well as possible problems, are discussed in detail.
\*
LCSR-TR-37
\11/82
\"Mini-Cost Network Floss, Part I: A Network Simplex Method"
\M.D. Grigoriadis
\
\
\12/82
\
\
\*
LCSR-TR-38
\12/82
\M.D. Grigoriadis
\
\
\12/82
\
\
\*
LCSR-TR-39
\12/82
\M.D. Grigoriadis
\
\
\12/82
\
\
\*
LCSR-TR-40
\9/82
\"Building Expert Systems for Controlling Complex Programs"
\Sholom Weiss
Casimir Kulikowski
Chidanand Apte
Michael Uschold
\11/82
\
\
\Production rule schemes have proven quite effective in concisely representing
expert knowledge in several application areas. Yet, there are many problems
for which one would like to take advantage of additional knowledge that may
not be easily represented in these surface level models. One class of
problems of particular practical interest are those in which we would like
to have a computer-based system give interactive advice on how to control a
and interpret results from a set of complex and interrelated applications
prpograms. The advice may refer to interpretations of current results,
possible experiments that should be performed with the help of the
applications programs, and indications of inconsistencies in specific
analytical procedures and in problem solving sequences followed by the user.
In the present paper we report on our experiences in designing an expert
system (ELAS), of the type described above, for well log analysis in oil
exploration and production. We have integrated a production rule advice
model (using the EXPERT system) with existing Amoco software for well-log
analysis was reorganized so that its knowledge structured according to
the types and sequences of methods used by expert analysts. By varying the
assumptions and parameters used in the different individual analysises.
Our goal is to make available interactive interpretations of the alternative
approaches that an expert might take to a complex problem of well-log analysis.
\*
LCSR-TR-41
\12/82
\"Expert Knowledge Management for Multi-level Modelling" -- with an application
to Well-Log Analysis."
\C. Apte
\
\
\12/82
\Expert problem solving strategies in many problem domains make use of detailed
quantitative or mathematical techniques coupled with experiential knowledge
about how such techniques can be used in solving a problem. Engineering
Analysis and Multiple Signal Interpretation are two instances of this class
of problems. In many such domains, these techniques are available as part of
large software packages. In attempting to build expert systems in these
domains, we wish to make use of such existing packages, and are therefore
faced with an important problem: How to intelligently control large-scale
complex software, during the course of its use, in the analysis of a task.
I am therefore proposing amulti-level model for representing problem solving
knowledge in such domains. These levels capture the mathematical/quantitative methods, associated interpretive knowledge, and control information on how they
interact. I also present an outline of a form-based system, for acquisition and representation of expert knowledge which controls and interprets these methods.
To support this proposal, I can report some preliminary, successful results,
in using these techniques to build an expert system for Well-log analysis,
ELAS [27]. Well logs are the various electromagnetic, sonic and nuclear
signals obtained from instruments placed downhole in a well, which
characterize the properties of the rock and fluid formations around the
borehole. The purpose of the overall analysis is to determine the likely
presence of hydrocarbons in the well for potential production.
This research proposal has evolved within a project concerned with the
introduction of Expert Systems methods in Well-log analysis. Some of the
issues raised by Hart [12], coupled with previous experience in expert
knowledge modelling, are influencing the direction of this research.
\*
LCSR-TR-42
\12/82 N. Minsky
\Principles for Database Authorization
\N. Minsky
A. Lockman
\
\
\12/82
\While most database systems incorporate some sort of authorization
mechanism, we contend that existing mechanisms are not quite adequate
for two tasks which they should support: a) enforcing the complex
authorization policies of real-life organizations; b) presenting
users with useful abstractions of the database. This paper proposes a
number of guiding principles for the design of database authorization
mechanisms which provide better support for these two tasks. We
illustrate how these principles might be implemented by giving
examples from our Operation Control authorization mechanism.
\*
LCSR-TR-43
\4/83
\"Numerical Methods for Basic Solutions of Generalized Flow Networks"
\M. Grigoriadis
Tau Hsu
\
\
\5/83
\A central problem in implementing specializations of the simplex
method for solving large minimum-cost generalized network flow
problems is the accurate and efficient computation of basic solutions.
In general, bases for such problems are block-diagonal, with each
block corresponding to a "one-tree", i.e. a connected graph which
contains exactly one cycle. This paper reviews two previously
proposed techniques for solving such one-tree systems and develops a
new algorithm based on Gaussian elimination for use within a
generalized network flow code. In addition to error bounds, the paper
gives numerical results and a computational comparison for all known
methods.
\*
LCSR-TR-44
\6/83
\"Learning by Re-expressing Concepts for Efficient Recognition"
\R. Keller
\
\
\6/83
\Much attention in the field of machine learning has been directed at
the problem of inferring concept descriptions from excamples. But in
many learning situations, we are initially presented with a
fully-formed concept description, and our goal is instead to
re-express that description with some particular task in mind. In
this paper, we specifically consider the task of recognizing concept
instances efficiently. We describe how concepts that are accurate,
though computationally inefficient for use in recognizing instances,
can be re-expressed in an efficient form through a process we call
@b[concept operationalization]. Various techniques for concept
operationalization are illustrated in the context of the LEX learning
system.
\*
LCSR-TR-45
\6/83
\"Learning and Problem Solving"
\T.M. Mitchell
\
\
\6/83
\One mark of intelligence is the ability to improve one's
problem-solving abilities with experience. Modelling this kind of
learning is an important goal for AI, both because it is bound to lead
to general insights on the nature of intelligence, and because of its
practical importance for developing high-performance problem solving
problems. We discuss some recent progress in the area of learning
problem-solving expertise, as well as some directions in which research
in this area is headed.
\*
LCSR-TR-46
\8/83
\"Stream Processing"
\A. Goldberg
R. Paige
\
\
\8/83
\Stream processing is a database query optimization related to loop
fusion that can improve space and speed by a process of loop
combination. Previous attempts at implementation have been either
highly restrictive, have required manual intervention, or have
involved naive strategies resulting in impractically slow running
times. This paper defines a general stream processing problem that is
formulated graph theoretically and shown to be NP-Hard, even in the
presence of constraints. Two new efficient algorithms will be
presented. One uses a greedy strategy to solve the general problem,
but yields suboptimal solutions on all but a modest class of problem
instances. The other algorithm solves a restricted problem but will
yield optimal results for a wide subclass of problem instances.
\*
LCSR-TR-47
\9/83
\"A Knowledge Based Approach to VLSI CAD"
\L. Steinberg
T. Mitchell
\
\
\2/84
\Artificial Intelligence (AI) techniques offer one possible avenue
toward new CAD tools to handle the complexities of VLSI. This paper
summarizes the experience of the Rutgers AI/VLSI group in exploring
applications of AI to VLSI design over the past few years. In
particular, it summarizes our experience in developing REDESIGN, a
knowledge-based system for providing interactive aid in the functional
redesign of digital circuits. Given a desired change to the function
of a circuit, REDESIGN combines rule-based knowledge of design tactics
with its ability to analyze signal propagation through circuits,
in order to (1) help the user focus on an appropriate portion of the
circuit to redesign, (2) suggest local redesign alternatives, and (3)
determine side effects of possible redesigns. We also summarize our
more recent research toward constructing a knowledge-based system for
VLSI design and a system for chip debugging, both based on extending
the techniques used by the REDESIGN system.
\*
LCSR-TR-48
\11/83
\"CONTROLLING SOFTWARE EVOLUTION: AN OVERVIEW OF DARWIN"
\N. Minsky
\A. Borgida
\
\
\12/83
\There has been considerable past effort expanded on software
engineering techniques which attempt to control the power of one part
of a program to affect other parts, but little or no attention has
been paid to the problem of controlling the @b[evolution] of a
software system.
This report describes a software development environment which
provides a unified, authorization-based regime for controlling both
the operations of a system as well as its evolutionary development.
\*
LCSR-TR-49
\12/83
\"POWER AND ITS DISTRIBUTION IN SOFTWARE SYSTEMS"
\N. Minsky
\
\
\12/83
\This paper introduces what we call a "power-based regime", which can
be viewed as a generalization of such linguistic disciplines as
@i[scope rules, information hiding] and @i[data-abstraction]. This
technique is expected to be beneficial for software engineering in
several ways. In particular:
@begin(enumerate)
It facilitates reasoning about large scale systems, by allowing one to
ignore most of the details of the system when reasoning about specific
aspects of it.
It allows us to provide parts of a system with a certain ability to
@i[control] the activity of the rest of it.
It supports a broad spectrum of policies for the design and management
of large scale, evolving systems.
@end(enumerate)
LCSR-TR-50
\12/83
\Srinivasan, C.
\
\
\
\*
LCSR-TR-51
\12/83
\Srinivasan, C.
\
\
\*
LCSR-TR-52
\12/83
\"FEATURES OF LANGUAGES FOR THE DEVELOPMENT OF INFORMATION SYSTEMS AT
THE CONCEPTUAL LEVEL"
\Borgida, A.
\
\
\1/84
A computer system which stores, retrieves and manipulates information
about some portion of the real world can be viewed as a @i[model] of
that domain of discourse. There has been considerable research
recently on languages which allow one to capture more of the
@i[semantics] of the real world in these computerized Information
Systems -- research which has variously been labelled as Semantic Data
Modeling, Semantic Modeling or Conceptual Modeling. This review paper
presents a list of the features which appear to distinguish these
languages from those traditionally used to describe and develop
database-intensive applications, and considers the motivation for
these features as well as the potential advantages to be gained
through their use. The paper, which is intended for those familiar
with current data processing practices, also compares in greater
detail four programming languages which incorporate semantic modeling
facilities, and discusses some of the methodologies and tools for
Information System development based on these languages.
\*
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.
\*
LCSR-TR-54 3/84 Minsky "The Darwin Programming
(NOT RECEIVED as of Borgida Environment"
3/16/84)
LCSR-TR-55
\5/84
\"The Critter System: Automated Critiquing of Digital Circuit Designs"
\Van E. Kelly
\
\
\9/84
\CRITTER is an exploratory prototype design aid, built using
Artificial Intelligence ("Expert Systems") technology, to aid in
"critiquing" digital circuit designs, encompassing issues of
functional correctness, operating speed, timing robustness, and
circuit sensitivity to changes in device parameters. Its
non-procedural representation for both real-time circuit @b[behavior]
and circuit @b[specifications] has led to a streamlined circuit
modeling formalism based on ordinary mathematical function
composition. In its interactions with the user it strives to be as
concise as possible, concentrating only on findings it judges to be
unexpected or unusual. After successful tests with circuits of up to
a dozen TTL SSI/MSI packages, CRITTER is being extended for use in an
automated VLSI design environment.
\*
LCSR-TR-57
\7/84
\"VEXED: A Knowledge-Based VLSI Design Consultant"
\T. M. Mitchell
L.I. Steinberg
J.S. Shulman
\
\
\9/84
\This paper presents a framework for knowledge-based aids for design
of VLSI circuits. In particular, we describe the design of an
interactive knowledge-based consultant for VLSI design (called
VEXED@foot[VEXED stands for VLsi EXpert EDitor.], a prototype
implementation of VEXED, and several issues that have arisen from
implementing and experimenting with this prototype.
This research is of significance to both the field of Artificial
Intelligence and the field of Computer-Aided Design. Given the
current state of the art of Expert Systems technology, it is now
fairly well understood how to build rule-based expert systems for
diagnostic and classification tasks, and several general-purpose
frameworks are now available for constructing such systems. However,
very few knowledge-based systems for design tasks have been
developed, and as a field we have yet to produce a generic model of
design tasks and generic frameworks for developing knowledge-based
systems for design. VEXED represents an attempt to build a system for
circuit design, in a way which we anticipate should extend to other
design domains as well.
\*
LCSR-TR-58
\9/84
\"The Rectangle Placement Language"
\J.A. Roach
\
\
\9/84
\Constraint-based symbolic layout of VLSI designs has received growing
attention during the past few years. Several systems have been
developed which can offer graphical or textual media for the
expression of designs and can provide automatic compaction to
technology specific design rules. The ability of these systems to
allow for the expression of more generalized relationships is a topic
open for further research. RPL is a constraint-based symbolic layout
language intended to address the problem of providing a more flexible
set of constraints and restraints to the designer for expressing the
relationships and dependencies of the design. This paper describes
some of the ideas behind this work and details some of the progress
that has been made.
\*
LCSR-TR-59 {THIS IS OUT OF PRINT - SEE LCSR-TR-69}
\10/84
\"A Lower Bound to the Complexity of Euclidean Matching Algorithms"
\M.D. Grigoriadis
B. Kalantari
\
\
\10/84
\We show that the time complexity of any exact algorithm for the
Euclidean minimum-weight perfect matching problem over n vertices is,
in the worst-case, bounded below by @g[W](n log n). This lower bound
also applies to any heuristic algorithm whose worst-case ratio of the
weight of the approximate solution it produces to the weight of the
optimal solution depends only on n.
\*
LCSR-TR-60
\11//84
\"Artificial Intelligence and the Social Sciences: A Preliminary Report
\Saul Amarel
\
\
\ll/84
\As part of the work of an NSF-sponsored panel on 'Methodological
Research Frontiers and the Social Sciences' (which met in Washington
D.C. on September 7, 1984) the relevance of Artificial Intelligence
(AI) methodologies to the Social Sciences was reviewed and appraised.
The purpose of this preliminary report is to describe a number of AI
activities that bear on this question, and to anticipate some
contributions that AI methodologies may make to the conduct of social
science research and to professional work in related areas.
\*
LCSR-TR-61
\12/84
\"Knowledge Representation as the Basis for Requirements"
\A. Borgida
S. Greenspan
J. Mylopoulos
\
\
\12/84
\Specification of many kinds of knowledge about the world is essential
to requirements engineering. Research on knowledge representation in
Artificial Intelligence addresses fundamental issues that Software
Engineering must eventually face, and provides a wealth of relevant
techniques which can be incorporated into specification languages. We
elaborate on these claims by using examples from our research on
Requirements Modeling.
*
LCSR-TR-62
\8/84
\"Introduction to the Comtex Microfiche Edition of the Rutgers
University Artificial Intelligence Research Reports"
\S. Amarel
\
\
\12/84
\In this introduction I will provide historical highlights of the
development of AI research at Rutgers, emphasizing the major strands
and themes that brought us to the current state of our research.
Naturally, the story will reflect my personal perspective on this
development. The present collection of reports covers most of our
work in AI from 1970 through 1983.
\*
LCSR-TR-63
\1/85
\"Controlling the Evolution of large scale Software Systems"
\N. Minsky
\
\
\1/85
\This paper deals wih certain fundamental issues involved with the
development and operation of large scale evolving software systems.
We are particularly, but not exclusively, concerened with systems that
evolve @i[in vivo], that is, systems whose development and maintenance
take place in the same environment, and at the same time, in which the
system itself operates. Such evolution involves several serious
difficulties : First, @i[it provides programmers with inordinate
amount of power with respect to the enterprise being served by the
system], such as the power to manipulate money wielded by the
programmers of a computerized financial system, if they are allowed to
change the system on the fly. The second, related, difficulty is the
@i[unpredictability of the behavior of evolving systems], emanating
from the inherent unpredictability of the programmers who manipulate
it.
We argue that in order to be able to treat an evolving system as a
single "organism" that exhibits a reasonable degree of behavior
predictability, it is necessary to control and constrain the process
of system evolution itself. A Software Development Environment,
called DARWIN, which provides such a control is described. Some
implkications of controlled evolution to the management of software
projects, and for the reliability of software, are briefly discussed.
\*
LCSR-TR-64
\1/85
\"LEAP: A Learning Apprentice for VLSI Design"
\T.Mitchell
S. Mahadevan
L.I. Steinberg
\
\
\1/85
\It is by now well-recognized that a major impediment to developing
knowledge-based systems is the knowledge acquisition bottleneck: the
task of building up a complete enough and correct enough knowledge
base to provide high-level performance. This paper proposes a new
class of knowledge-based systems designed to address this
knowledge-acquisition bottleneck by incorporating a learning component
to acquire new knowledge through experience. In particular, we define
a Learning Apprentice System as a knowledge-based system that provides
@i[interactive] aid in solving some problem, and that acquires new
domain knowledge by generalizing from training examples acquired
through the @i[normal course] of its use. This paper describes a
specific Learning Apprentice System, called LEAP, which is presently
being developed in the domain of VLSI design. We also discuss design
issues for Learning Apprentice Systems more generally, as well as
restrictions on the generality of our current approach.
\*
LCSR-TR-65 NOT RECEIVED YET
\1/85
\"A Knowledge-Based Approach to Design"
\T. Mitchell
Steinberg
Shulman
\
\
\1/85
\
\*
LCSR-TR-66
\1/85
\"Verification-Based Learning: A Generalization Strategy for inferring
Problem-Decomposition Methods."
\Sridhar Mahadevan
\
\
\1/85
\A new technique for learning problem-solving operators from examples
is described in this paper. The technique is illustrated by
demonstrating how it can be used to acquire a specific type of
operator, namely a @i[problem-decomposition] method. The important
notion of a @i[verification] is introduced as a basis for obtaining
general problem-decomposition methods from single examples. Two
detailed examples of the application of the technique from the domains
of Circuit Design and Symbolic Integration illustrate the generality
of the technique.
\*
LCSR-TR-67
\1/85
\"Extending Authorization by Adding Obligations to Permissions"
\N.H. Minsky
A. Lockman
\
\
\2/85
\Conventional authorization mechanisms provide actors with
@i[permissions] to act, without the actor ever incurring any
@i[obligations] as a result of executing the permitted action. There
exist, however, many situations where system integrity requires that
certain actions always be followed by others, within some reasonable
time frame. We propose an extension to conventional authorization
that allows the explicit association of obligations with permissions,
and enforces them. We demonstrate that the extended mechanism can be
used to support and enforce several general types of control policies
and integrity constraints which are otherwise difficult or impossible
to support.
\*
LCSR-TR-68
\2/85
\"Unifying the Use and Evolution of Database Systems: A Case Study in Prolog"
\N. Minsky
D. Rozenshtein
J. Chomicki
\
\
\2/85
\This paper presents a model that provides a single uniform mechanism
to control the use, operation and evolution of database systems. This
model unifies several concepts generally considered to be quite
distinct. In particular, it minimizes the formal distinction between
the users of the database, the programs embedded in it, and even the
programmers maintaining it. Furthermore, under this model, the
concepts of subschema and of program module are replaced with a single
concept of @i[frame] which serves as the locus of power and of
activity in the database system. Moreover, the proposed control
mechanism is @i[closed], in the sense that the process of establishing
control is itself controllable by the same mechanism.
Besides its considerable conceptual parsimony, this model supports the
formalization of a wide variety of managerial policies regarding the
operation and evolution of database systems, and has a potential to
enhance their reliability.
\*
LCSR-TR-69 {This replaces LCSR-TR-59}
\2/85
\"A Lower Bound to the Complexity of Euclidean and Rectliniear
Matching Algorithms"
\M.D. Grigoriadis
B. Kalantari
\
\
\2/85
\The worst-case time complexity of any exact algorithm for the
Euclidean or retilinear minimum-weight perfect matching problem which
takes as input the list of coordinates of n points in , is
shown to be bounded below by the infimum of the worst-case time
complexities of all algorithms which sort n real numbers. This result
also applies to any heuristic algorithm for which the worst-case ratio
of the weight of the approximate matching it produces to the weight of
the optimal matching depends only upon n.
\*
LCSR-TR-70
\3/85
\"Language Features for Flexible Handling of Exceptions in Information
Systems"
\A. Borgida
\
\
\3/85
@\We present an exception handling facility suitable for languages
used to implement database-intensive Information Systems. Such a
mechanism facilitates the development and maintenance of more flexible
software systems by supporting the abstraction of details concerning
special or abnormal occurrences. We consider the type constraints
imposed by the schema and various semantic integrity assertions to be
normalcy conditions, and the key contribution of this work is to allow
exceptions to these constraints to persist. To achieve this, we
propose solutions to a range of problems, including the sharing of
exceptional information, computing with exceptional data,
implementation issues, accountability, exception handling by users,
and the logic of constraints with exceptions. We also illustrate the
use of exception handling in dealing with null values, estimates, and
measurements.
\*
LCSR-TR-71
\6/85
\"Towards a Programming Environment for Large Prolog Programs"
\Jan Chomicki
Naftaly H. Minsky
\
\
\6/85
\We discuss here two issues of programming in-the-large in Prolog:
modularization and system evolution. We propose a mechanism, which
controls both module interactions and programmer's actions. In this
way, certain invariants of a large Prolog programs can be maintained
not only during a single execution, but also throughout the lifetime
of the program. Traditional constructs, such as scope rules and
modules can be modelled in our framework. Moreover, various kinds of
managerial policies in software projects can be enforced. An
experimental programming environment, called Elog, incorporating our
ideas has been implemented (in Prolog).
LCSR-TR-72
\6/85
\"The Critter System -- An Artificial Intelligence Approach to Digital
Circuit Design Critiquing"
\Van E. Kelly
\
\
\6/85
\The CRITTER system is an exploratory prototype digital circuit design
aid, built using Artificial Intelligence technology, for comprehensive
'critiquing' of digital circuit designs. This critiquing encompasses
issues of a circuit's functional correctness, operating speed, timing
robustness, and sensitivity to changes in device parameters. In
contrast to most circuit design aids, CRITTER is not only concerned
with modeling circuit performance, but also with reporting the results
of that modeling in the light of the concerns of the circuit designer,
i.e., concisely summarizing only those findings it judges to be unexpected or
unusual.
CRITTER uses a non-procedural, applicative language to describe
real-time circuit behavior, and a predicate calculus notation for
expressing an exhaustive set of specifications a circuit must satisfy,
including both user-specified requirements and constraints arising as
side effects of implementation choices. CRITTER evaluates the
satisfaction of all these specifications by a process of symbolic
constraint propagation, a generalization of traditional constraint
propagation systems which employs symbolic algebra. By detecting,
comparing and classifying all the violated specifications, CRITTER
tries to pinpoint design errors and performance bottlenecks.
Additionally, CRITTER has a performance bounding approach to
evaluating timing specifications in the presence of uncertain timing
information.
CRITTER has been used to validate circuits consisting of up to a dozen
TTL SSI/MSI packages. It successfully detected a marginal timing
design in one of these that had been missed during less formal design
evaluations. CRITTER is currently being adapted for use in an
automated VLSI design environment.
\*
LCSR-TR-73 7/85 Kalantari Quadratic Functions with
\8/85
\"Quadratic Functions with Exponential Number of Local Maxima"
\B. Kalantari
\
\
\8/85
\We demonstrate complexity in quadratic optimization in the following
sense: For each natural numbers n and k @u[>] 2, we construct a
quadratic function f, with n x k variables and exhibit 2@+[n] vertices
of the unit hypercube of dimension n x k over which f takes distinct
values and where each vertex is a strong local maximum of f in the
continuous sense as well as in the discrete sense.
\*
LCSR-TR-74
\8/85
\"A Good Heuristic for the Chinese Postman Problem"
\M.D. Grigoriadis
B. Kalantari
\
\
\8/85
\We present a two-phase heuristic for the Chinese postman problem over
undirected connected edge-weighted graphs of arbitrary density. The
first phase is a generalization of Papadimitriou's minimum spanning
tree heuristic for the minimum perfect matching problem on complete
graphs satisfying the triangle inequality. This phase obtains an
approximate solution for which the weight of the "duplicate" edge
traversals does not exceed (n - @!@+[@u{k}]@/@-[2]) times that in
the optimal solution, where n is the total number of vertices in the
given graph and k the number of odd vertices. We show that this bound
is tight in the worst-case. The second phase improves upon this
approximation by solving a minimum cost transshipment problem. Our
experimental results indicate that, for graphs of various sizes and
densities, the two-phase heuristic, which is much faster than the best
implementation of Edmonds and Johnson's exact algorithm, consistently
produces approximate solutions with very small relative errors.
\*
LCSR-TM-1
\7/80
\"Using BRIGHT for Maintaining Class Rosters and Grades"
\R. Goldberg
\
\
\1/82
\This document describes an application of BRIGHT version 3, an
interactive data management system designed and implemented by the
author. The development of BRIGHT version 3 was supported by the
Biotechnology Resources Program, Division of Research Resources,
National Institutes of Health, Department of Health, Education, and
Welfare, under Grant 5 P41 RR00643 to the Special Research Resource:
Computers in Biomedicine at Rutgers University, New Brunswick, New
Jersey.
\*
LCSR-TM-2
\5/82
\"Acquisition of Appropriate Bias for Inductive Concept Learning"
Dissertation Proposal
\P.E. Utgoff
\
\
\10/82
\The inductive concept learning task is to observe examples and
counterexamples of the concept and, based on these observations, to
inductively infer the correct classifications for the unobserved
instances in the domain. This inductive inference process must be
guided by some form of information which we call bias. The proposed
thesis is that, based on information available to the concept learner,
bias which is needed to guide the inductive inference process in
concept learning can be acquired during concept learning. The overall
approach is to represent bias as a structure which can be manipulated,
specifically as an incomplete concept description language. By
forcing such an equivalence between bias and the concept description
language, bias can be manipulated by revising the concept description
language. For the concept attainment task, Mitchell's Candidate
Elimination Algorithm will be employed because it requires that bias
be represented as an incomplete concept description language. For the
concept formation task, we propose new methods which can be used to
revise the vocabulary of concepts to be considered during concept attainment.
\*
LCSR-TM-3
\10/82
\"Gaussian Elimination Runs in Polynomial Time"
\M. Dowd
\
\
\11/82
\We show that the ordinary Gaussian elimination algorithm runs in
polynomial time on a Turing machine. We do this by obtaining an
explicit expression for the matrix entries at any stage of the
procedure.
\*
LCSR-TM-4
\2/83
\"VEDIT Users Manual"
\John A. Roach
Jeffrey S. Shulman
\
\
\4/83
\VEDIT is a graphics based editor for VLSI circuits. It is based on
CIF which defines symbols that contain objects (currently only
rectangles) on a given mask layer and/or possible calls to other
symbols (the actual internal representation is CIF-like but not CIF,
see section 2.1 on how to convert a CIF file to internal
representation).
\*
LRP-TR-4
\5/80
\"The Representation of Conceptual Structures of TAXMAN II.
Part One: Logical Templates"
\L.T. McCarty
N.S. Sridharan
\
\
\1/82
\This report presents some basic information about the organization of
the TAXMAN II system, as of January, l980. We assume that the reader
is familiar with the general outline of the TAXMAN project, as
described in McCarty (l980) and McCarty, Sridharan and Sangster
(l979). In particular, we assume a familiarity with the basic
distinction between Logical Template structures and
Prototype-plus-Deformation structures, of which only the former will
be discussed in these pages. An abbreviated version of this report
will be presented at the Third National Conference of the Canadian
Society for Computational Studies of Intelligence, May 14-16, l980,
under the title: "The Representation of an Evolving System of Legal
Concepts: I. Logical Templates."
The report is divided into four sections. Section I describes AIMDS,
the basic language for the TAXMAN II implementation, and compares this
language to several other languages in the current AI literature.
Section II describes an extension of AIMDS which is unique to TAXMAN
II a set of descriptions (called DDNs and PDNs) which can be arranged
in an abstraction/expansion hierarchy to represent a complex system of
concepts. Section III then describes the pattern-matcher for this
abstraction/expansion hierarchy, with emphasis on our current
techniques for incorporating several diverse pattern-matching
strategies into a single system. Finally, Section IV outlines our
current work on the semantics of the TAXMAN II domain, and explains
the relationship between our present representation of Logical
Template structures and our projected representation of
Prototype-plus-Deformation structures. Part Two of this report
(which has not yet been written) will discuss these latter structures
in greater detail.
\*
LRP-TR-5
\3/80
\"The Post-Macomber Cases in a TAXMAN II Framework:
A Preliminary Analysis"
\D. Brody
\
\
\1/82
\In his revised proposal for Taxman II, @i(The Implementation of
Taxman II: An Experiment in Artificial Intelligence and Legal
Reasoning) (hereinafter cited as "McCarty"), L. Thorne McCarty
examined the arguments of Justices Pitney and Brandeis concerning the
nature of taxable income under the 16th amendment to the United States
Constitution. These arguments were seen to exhibit respectively what
McCarty called template and prototype-plus-deformation form. It was
hoped that analysis of the non-statutory reorganization cases and the
later stock dividend cases would show repetition of these styles of
argument and provide evidence of the process of conceptual change.
"Most significantly, we hope to be able to see in greater detail why
some conceptual structures work well, and others work poorly; why some
arguments are persuasive, and others are not."
\*
LRP-TR-6
\5/80
\"Some Notes on the MAP Formalism of TAXMAN II, with Applications to
Eisner v. Macomber"
\L.T. McCarty
\
\
\1/82
\We have talked for some time within the TAXMAN project about a magical
entity called a MAP, but our specification of the structure and
function of this entity has so far been exceedingly vague. These
notes are an attempt to fix some ideas about the MAP formalism as they
occur to me at the present time (early November, l979). I will try to
be fairly precise about the syntax and semantics of MAPs, and I will
try to analyze the case of @u(Eisner v. Macomber) within this
framework. I think we are now close to having a computational theory
of the Macomber case worked out in full, and I will try to set this
down as completely as possible.
\*
LRP-TR-7
\3/80
\"The Representation of an Evolving System of Legal Concepts: I.
Logical Templates"
\L.T. McCarty
N.S. Sridharan
\
\
\1/82
\Although our earlier work on the TAXMAN Project (McCarty, l977) has
demonstrated the basic feasibility of applying artificial intelligence
techniques to the field of corporate tax law, the original TAXMAN
system was seriously deficient as a model of "legal reasoning". More
recently (McCarty, Sridharan and Sangster, l979), we have proposed an
alternative model of conceptual structure, and an approach to the
process of conceptual change, in an attempt to remedy these
deficiencies. In the TAXMAN II system, which is currently under
development, we distinguish between two different kinds of legal
concepts. Precise statutory rules are represented as @u(logical
templates), a term intended to suggest the way in which a "logical"
pattern is "matched" to a lower-level factual network during the
analysis of a corporate tax case. But the more amorphous concepts of
corporate tax law, the concepts typically constructed and
reconstructed in the process of a judicial decision, are represented
by a @u(prototype) and a sequence of @u(deformations) of the
prototype. The prototype is a relatively concrete description
selected from the lower-level factual network itself, and the
deformations are selected from among the possible @u(mappings) of one
concrete description into another. We have suggested that these
prototype-plus-deformation structures play a crucial role in the
process of legal argument, and that they contribute a degree of
stability and flexibility to a system of legal concepts that would not
exist with the template structures alone (see McCarty, l980).
\*
LRP-TR-8
\7/80
\"Some Requirements for a Computer-based Legal Consultant"
\L.T. McCarty
\
\
\1/82
\Although the literature on computer-based consultation systems has
often suggested the possibility of building an expert system in the
field of law (see, e.g., Buchanan and Headrick, l970), it is only
recently that several AI researchers have begun to explore this
possibility seriously. Recent projects include: the development of a
computational theory of legal reasoning, using corporate tax law as an
experimental problem domain (McCarty, l977; McCarty, l980; McCarty and
Sridharan, l980); the development of a language for expressing legal
rules within a data-base management environment (Jones, Mason and
Stamper, l979; Stamper, l980); the design of an information retrieval
system based on a computer model of legal knowledge (Hafner, l978);
and the design of an artificial intelligence system to analyze simple
tort cases (Meldman, l975; Meldman, l977).
This paper attempts to identify the principal obstacles to the
development of a legal consultation system, given the current state of
artificial intelligence research, and argues that there are only
certain areas of the law which are amenable to such treatment at the
present time. The paper then suggests several criteria for selecting
the most promising areas of application, and indicates the kinds of
results that might be expected, using our current work on the TAXMAN
project (McCarty, Sridharan and Sangster, l979) as an example.
\*
LRP-TR-9
\10/80
\"A Computational Theory of Eisner v. Macomber"
\L.T. McCarty
\
\
\1/82
\This article pulls together some of the technical ideas from our
earlier papers on the TAXMAN project, and fashions them into a
coordinated analysis of Eisner v. Macomber, 252 U.S. 189 (l920), the
early stock dividend case. I discussed this case in detail in McCarty
[l980a], but the analysis there was quite loose: the paper spoke
vaguely of "templates" and "prototypes", of invariants and
"transformations", without attempting to give these concepts a
rigorous specification as computer data structures. Another earlier
paper, McCarty and Sridharan [1980b], described somewhat more
rigorously our current representation of the logical template
structures of TAXMAN II, but made no attempt to define what we meant
by prototypes and deformations. In this paper I will attempt to
remedy these deficiencies in a modest way. I will start with the
representational machinery of McCarty and Sridharan [1980b], and add
just enough of the "prototype-plus-deformation" machinery to represent
the basic patterns of legal argument observed in McCarty [1980a]. The
result, I claim, is a computational theory of Eisner v. Macomber: a
specification of the initial cognitive structures adopted by the
participants in the case, a specification of the strategic choices
made at each step in the construction of the arguments, and a
specification of the final positions set forth by Justice Pitney and
Justice Brandeis for the majority and the dissent.
Several caveats are in order. First, given the space limitations for
these conference proceedings, it is not possible to write an entirely
self-contained paper. I will thus assume that the reader has access
to McCarty and Sridharan [1980b] for the details of the TAXMAN II
representation, and I will include here only a brief outline of the
essential points. I will also assume that the reader is generally
familiar with the discussion of Eisner v. Macomber in McCarty [1980a],
so that I may proceed directly to the computational version. Second,
although the theory outlined in this paper is intended to be
implemented in a computer program, our implementation is not, at the
time of writing, complete. The present theory is therefore only a
"hand simulation": it poses computational problems at critical points
(e.g., "generate a data structure with the following
characteristics...") and then, without actually performing the
computation, it exhibits the data structures which Justice Pitney and
Justice Brandeis seem to have constructed in the analogous situations.
Given the lead time required for the preparation of this paper,
however, we hope to have an initial implementation available at the
time of the conference, and it should be interesting at that time to
compare the present hand simulation with the real thing.
\*
LRP-TR-10
\8/81
\"The Applications of Artificial Intelligence to Law:
A Survey of Six Current Projects"
\L.T. McCarty
\
\
\1/82
\This paper is a survey of six current projects on the applications of
artificial intelligence to legal problem domains, as presented in a
panel discussion at the 1981 National Computer Conference.
Two of the projects are concerned primarily with practical
applications: Hafner, represented in Section I, has explored the use
of a conceptual knowledge-base in an enhanced legal retrieval system,
and Sprowl, in Section II, has developed and tested a system which
assists an attorney in the drafting of routine legal documents.
Several of the projects have considered the general problem of
designing a language in which legal rules and legal concepts might be
easily expressed: the LEGOL project (Section IV) and the TAXMAN
project (Section V) fit within this category, as does the work of
Meldman (Section III) on the design of a system for computer-aided
legal analysis. Finally, two of the projects are exploring some
general theoretical issues about the legal process: McCarty and
Sridharan (Section V) are attempting to understand the patterns of
argument that appear in a contested corporate tax case, and Waterman
and Peterson (Section VI) are attempting to understand the
decisionmaking procedures of attorneys and claims adjusters in product
liability cases.
\*
LRP-TR-11
\8/81
\"The Representation of an Evolving System of Legal Concepts II.
Prototypes and Deformations"
\L.T. McCarty
N.S. Sridharan
\
\
\1/82
\One of the principal goals of the TAXMAN project is to develop a
theory about the structure and dynamics of legal concepts, using
corporate tax law as an experimental problem domain. In this paper we
describe the "prototype-plus-deformation" model of legal conceptual
structure: a concept is represented here by a prototypical
description plus a sequence of deformations of the prototype, where
the deformations are selected from among the possible "mappings" of
one concrete description into another. The paper focuses on the set
of mappings, which is the most important component of the model
because it makes manifest the basic coherence of the conceptual space.
The syntax and semantics of the mappings are described, and their role
in the process of legal argument is suggested. The formal model is
then illustrated by examples drawn from Eisner v. Macomber, an early
stock dividend case.
\*
-------
Technical Details
Message-ID:
<8601240815.AA15145@ucbvax.berkeley.edu>Path:
arc1-ca.pugleaf.net!utzoo!decvax!ittatc!dcdwest!sdcsvax!ucbvax.berkeley.edu!uucpShow 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!uucp From: uucp@ucbvax.berkeley.edu.BERKELEY.EDU (UNIX Copy) Newsgroups: mod.techreports Subject: (none) Message-ID: <8601240815.AA15145@ucbvax.berkeley.edu> Date: Fri, 24-Jan-86 03:15:33 EST Article-I.D.: ucbvax.8601240815.AA15145 Posted: Fri Jan 24 03:15:33 1986 Date-Received: Sat, 25-Jan-86 04:40:10 EST Organization: The ARPA Internet Lines: 2510 Approved: techreports@smu.CSNET