Stanford Computer Science Department Technical Reports from the 1970
The
authors have given permission to make their technical reports available
on this server. If a report was published in print and is not here it
may be that the author published it elsewhere.
Report Number: CS-TR-70-146
Institution: Stanford University, Department of Computer Science
Title: Roundoff error analysis of the fast Fourier transform
Author: Ramos, George U.
Date: February 1970
Abstract:
This paper presents an analysis of roundoff errors occurring in the
floating-point computation of the fast Fourier transform. Upper bounds
are derived for the ratios of the root-mean-square (RMS) and maximum
roundoff errors in the output data to the RMS value of the input data
for both single and multidimensional transformations. These bounds are
compared experimentally with actual roundoff errors.
CS-TR-70-146
Report Number: CS-TR-70-147
Institution: Stanford University, Department of Computer Science
Title: Pitfalls in computation, or why a math book isn't enough
Author: Forsythe, George E.
Date: January 1970
Abstract:
The floating-point number system is contrasted with the real numbers.
The author then illustrates the variety of computational pitfalls a
person can fall into who merely translates information gained from pure
mathematics courses into computer programs. Examples include summing a
Taylor series, solving a quadratic equation, solving linear algebraic
systems, solving ordinary and partial differential equations, and
finding polynomial zeros. It is concluded that mathematics courses
should be taught with a greater awareness of automatic computation.
CS-TR-70-147
Report Number: CS-TR-70-150
Institution: Stanford University, Department of Computer Science
Title: Elementary proof of the Wielandt-Hoffman Theorem and of its generalization
Author: Wilkinson, James H.
Date: January 1970
Abstract:
An elementary proof is given of the Wielandt-Hoffman Theorem for normal
matrices and of a generalization of this theorem. The proof makes no
direct appeal to results from linear-programming theory.
CS-TR-70-150
Report Number: CS-TR-70-151
Institution: Stanford University, Department of Computer Science
Title:
"On the Properties of the Derivatives of the Solutions of Laplace's
Equation and the Errors of the Method of Finite Differences for
Boundary Values in $C_2$ and $C_{1,1}$" by E. A. Volkov
Author: Volkov, E. A.
Author: Forsythe, George E.
Date: January 1970
Abstract:
If a function u is harmonic in a circular disk and its boundary values
are twice continuously differentiable, u need not have bounded second
derivatives in the open disk. For the Dirichlet problem for Laplace's
equation in a more general two-dimensional region the discretization
error of the ordinary method of finite differences is studied, when
Collatz's method of linear interpolation is used at the boundary. If
the boundary of the region has a tangent line whose angle satisfies a
Lipschitz condition, and if the boundary values have a first derivative
satisfying a Lipschitz condition, then the discretization error is
shown to be of order $h^2 ln h^{-1}$. This bound is shown to be sharp.
By a different method of interpolation at the boundary one can improve
the bound to o($h^2$). There are other similar results. Translated by
G. E. Forsythe.
CS-TR-70-151
Report Number: CS-TR-70-155
Institution: Stanford University, Department of Computer Science
Title: The method of odd/even reduction and factorization with application to Poisson's equation, part II
Author: Buzbee, B. L.
Author: Golub, Gene H.
Author: Nielson, C. W.
Date: March 1970
Abstract:
In this paper, we derive and generalize the methods of Buneman for
solving elliptic partial difference equations in a rectangular region.
We show why the Buneman methods lead to numerically accurate solutions
whereas the CORF algorithm may be numerically unstable. Several
numerical examples are given and discussed.
CS-TR-70-155
Report Number: CS-TR-70-156
Institution: Stanford University, Department of Computer Science
Title: On a model for computing round-off error of a sum
Author: Dantzig, George B.
Date: March 1970
Abstract: No abstract available.
CS-TR-70-156
Report Number: CS-TR-70-157
Institution: Stanford University, Department of Computer Science
Title: Algorithms for matrix multiplication
Author: Brent, Richard P.
Date: March 1970
Abstract:
Strassen's and Winograd's algorithms for matrix multiplication are
investigated and compared with the normal algorithm. Floating-point
error bounds are obtained, and it is shown that scaling is essential
for numerical accuracy using Winograd's method. In practical cases
Winograd's method appears to be slightly faster than the other two
methods, but the gain is, at most, about 20%. Finally, an attempt to
generalize Strassen's method is described.
CS-TR-70-157
Report Number: CS-TR-70-159
Institution: Stanford University, Department of Computer Science
Title: The use of direct methods for the solution of the discrete Poisson equation on non-rectangular regions
Author: George, John Alan
Date: June 1970
Abstract:
Some direct and iterative schemes are presented for solving a standard
finite-difference scheme for Poisson's equation on a two-dimensional
bounded region R with Dirichlet conditions specified on the boundary
$\delta$R. These procedures make use of special-purpose direct methods
for solving rectangular Poisson problems. The region is imbedded in a
rectangle and a uniform mesh is superimposed on it. The usual
five-point Poisson difference operator is applied over the whole
rectangle, yielding a block-tridiagonal system of equations. The
original problem, however, determines only the elements of the
right-hand side which correspond to grid points lying within $\delta$R;
the remaining elements can be treated as parameters. The iterative
algorithms construct a sequence of right-hand sides in such a way that
the corresponding sequence of solutions on the rectangle converges to
the solution of the imbedded problem.
CS-TR-70-159
Report Number: CS-TR-70-160
Institution: Stanford University, Department of Computer Science
Title: A model for parallel computer systems
Author: Bredt, Thomas H.
Author: McCluskey, Edward J.
Date: April 1970
Abstract:
A flow table model is defined for parallel computer systems. In this
model, fundamental-mode flow tables are used to describe the operation
of system componenets, which may be programs or circuits. Components
communicate by changing the values on interconnecting lines which carry
binary level signals. It is assumed that there is no bound on the time
for value changes to propagate over the interconnecting lines. Given
this delay assumption, it is necessary to specify a mode of operation
for system components such that input changes which arrive while a
component is unstable do not affect the operation of the component.
Such a mode of operation is specified. Using the flow table model, a
new control algorithm for the two-process mutual exclusion problem is
designed. This algorithm does not depend on the exclusive execution of
any primitive operations used in its implementation. A circuit
implementation of the control algorithm is described.
CS-TR-70-160
Report Number: CS-TR-70-162
Institution: Stanford University, Department of Computer Science
Title: Numerical techniques in mathematical programming
Author: Bartels, Richard H.
Author: Golub, Gene H.
Author: Saunders, Michael A.
Date: May 1970
Abstract:
The application of numerically stable matrix decompositions to
minimization problems involving linear constraints is discussed and
shown to be feasible without undue loss of efficiency. Part A describes
computation and updating of the product-form of the LU decomposition of
a matrix and shows it can be applied to solving linear systems at least
as efficiently as standard techniques using the product-form of the
inverse. Part B discusses orthogonalization via Householder
transformations, with applications to least squares and quadratic
programming algorithms based on the principal pivoting method of Cottle
and Dantzig. Part C applies the singular value decomposition to the
nonlinear least squares problem and discusses related eigenvalue
problems.
CS-TR-70-162
Report Number: CS-TR-70-163
Institution: Stanford University, Department of Computer Science
Title: An algorithm for floating-point accumulation of sums with small relative error
Author: Malcolm, Michael A.
Date: June 1970
Abstract:
A practical algorithm for floating-point accumulation is presented.
Through the use of multiple accumulators, errors due to cancellation
are avoided. An example in Fortran is included. An error analysis
providing a sharp bound on the relative error is also given.
CS-TR-70-163
Report Number: CS-TR-70-164
Institution: Stanford University, Department of Computer Science
Title: "Estimates of the Roundoff Error in the Solution of a System of Conditional Equations" by V. I. Gordonova
Author: Gordonova, V. I.
Author: Kaufman, Linda C.
Date: June 1970
Abstract:
Using backward error analysis, this paper compares the roundoff error
in the least-squares solution of a system of conditional equations Ax=f
by two different methods. The first one entails solving the normal
equations $A^T$Ax=$A^T$f and the second is one proposed by Faddeev,
Faddeeva, and Kublanovskaya in 1966. This latter method involves
multiplying the system by orthogonal matrices to transform the matrix A
into upper triangular form. Translated by Linda Kaufman.
CS-TR-70-164
Report Number: CS-TR-70-165
Institution: Stanford University, Department of Computer Science
Title: The scheduling of n tasks with m operations on two processors
Author: Bauer, Henry R.
Author: Stone, Harold S.
Date: July 1970
Abstract:
The job shop problem is one scheduling problem for which no efficient
algorithm exists. That is, no algorithm is known in which the number of
computational steps grow algebraically as the problem enlarges. This
paper presents a discussion of the problem of scheduling N tasks on two
processors when each task consists of three operations. The operations
of each task must be performed in order and among the processors. We
analyze this problem through four sub-problems. Johnson's scheduling
algorithm is generalized to solve two of these sub-problems, and
functional equation algorithms are used to solve the remaining two
problems. Except for one case, the algorithms are efficient. The
exceptional case has been labelled the "core" problem and the
difficulties are described.
CS-TR-70-165
Report Number: CS-TR-70-170
Institution: Stanford University, Department of Computer Science
Title: Analysis and synthesis of concurrent sequential programs
Author: Bredt, Thomas H.
Date: May 1970
Abstract:
This paper presents analysis and synthesis procedures for a class of
sequential programs. These procedures aid in the design of programs for
parallel computer systems. In particular, the interactions of a given
program with other programs or circuits in a system can be described
precisely. The basis for this work is a model for parallel computer
systems in which the operation of each component is described by a flow
table and the components interact by changing values on interconnecting
lines. The details of this model are discussed in another paper
[Stanford University Department of Computer Science report
STAN-CS-70-160]. The analysis procedure produces a flow table
description of a program. In program synthesis, a flow table
description is converted to a sequential program. Using flow table
design procedures, a control program for the two-program mutual
exclusion problem is produced.
CS-TR-70-170
Report Number: CS-TR-70-171
Institution: Stanford University, Department of Computer Science
Title: A survey of models for parallel computing
Author: Bredt, Thomas H.
Date: August 1970
Abstract:
The work of Adams, Karp and Miller, Luconi, and Rodriguez on formal
models for parallel computations and computer systems is reviewed. A
general definition of a parallel schema is given so that the
similarities and differences of the models can be discussed. Primary
emphasis is on the control structures used to achieve parallel
operation and on properties of the models such as determinacy and
equivalence. Decidable and undecidable properties are summarized.
CS-TR-70-171
Report Number: CS-TR-70-172
Institution: Stanford University, Department of Computer Science
Title: Analysis of parallel systems
Author: Bredt, Thomas H.
Date: August 1970
Abstract:
A formal analysis procedure for parallel computer systems is presented.
The flow table model presented in an earlier paper [Stanford University
Department of Computer Science report STAN-CS-70-160] is used to
describe a system. Each component to the system is described by a
completely specified fundamental-mode flow table. All delays in a
parallel system are assumed to be finite. Component delays are assumed
to be bounded and line delays unbounded. The concept of an output
hazard is introduced to account for the effects of line delay and the
lack of synchronization among components. Necessary and sufficient
conditions for the absence of output hazards are given. The state of a
parallel system is defined by the present internal state and input
state of each component. The operation of the system is described by a
system state graph which specifies all possible state transitions for a
specified initial system state. A procedure for constructing the system
state graph is given. The analysis procedure may be summarized as
follows. A problem is stated in terms of restrictions on system
operation. A parallel system is said to operate correctly with respect
to the given problem if the associated restrictions are always
satisfied. The restrictions specify either forbidden system states,
which are never to be entered during the operation of the system, or
forbidden system state sequences, which must never appear during system
operation. The restrictions are tested by examining the system state
graph. A parallel system for the two-process mutual exclusion problem
is analyzed and the system is shown to operate correctly with respect
to this problem. Finally, the conditions of determinacy and output
functionality, which have been used in other models of parallel
computing, are discussed as they relate to correct solutions to the
mutual exclusion problem.
CS-TR-70-172
Report Number: CS-TR-70-173
Institution: Stanford University, Department of Computer Science
Title: The mutual exclusion problem
Author: Bredt, Thomas H.
Date: August 1970
Abstract:
This paper discusses how n components, which may be programs or
circuits, in a computer system can be controlled so that (1) at most
one component may perform a designated "critical" operation at any
instant and (2) if one component wants to perform its critical
operation, it is eventually allowed to do so. This control problem is
known as the mutual exclusion or interlock problem. A summary of the
flow table model [Stanford University Department of Computer Science
report STAN-CS-70-160] for computer systems is given. In this model, a
control algorithm is represented by a flow table. The number of
internal states in the control flow table is used as a measure of the
complexity of control algorithms. A lower bound of n + 1 internal
states is shown to be necessary if the mutual exclusion problem is to
be solved. Procedures to generate control flow tables for the mutual
exclusion problem which require the minimum number of internal states
are described and it is proved that these procedures given correct
control solutions. Other so-called "unbiased" algorithms are described
which require 2.n! internal states but break ties in the case of
multiple requests in favor of the component that least recently
executed its critical operation. The paper concludes with a discussion
of the tradeoffs between central and distributed control algorithms.
CS-TR-70-173
Report Number: CS-TR-70-174
Institution: Stanford University, Department of Computer Science
Title: Towards automatic program synthesis
Author: Manna, Z ohar
Author: Waldinger, Richard J.
Date: July 1970
Abstract:
An elementary outline of the theorem-proving approach to automatic
program synthesis is given, without dwelling on technical details. The
method is illustrated by the automatic construction of both recursive
and iterative programs operating on natural numbers, lists, and trees.
In order to construct a program satisfying certain specifications, a
theorem induced by those specifications is proved, and the desired
program is extracted from the proof. The same technique is applied to
transform recursively defined functions into iterative programs,
frequently with a major gain in efficiency. It is emphasized that in
order to construct a program with loops or with recursion, the
principle of mathematical induction must be applied. The relation
between the version of the induction rule used and the form of the
program constructed is explored in some detail.
CS-TR-70-174
Report Number: CS-TR-70-175
Institution: Stanford University, Department of Computer Science
Title: A description and comparison of subroutines for computing Euclidean inner products on the IBM 360
Author: Malcolm, Michael A.
Date: October 1970
Abstract:
Several existing subroutines and an Algol W procedure for computing
inner products on the IBM 360, using more precision than long, are
described and evaluated. Error bounds (when they exist) and execution
timing tests are included.
CS-TR-70-175
Report Number: CS-TR-70-176
Institution: Stanford University, Department of Computer Science
Title: On generality and problem solving: a case study using the DENDRAL program
Author: Feigenbaum, Edward A.
Author: Buchanan, Bruce G.
Author: Lederberg, Joshua
Date: August 1970
Abstract:
Heuristic DENDRAL is a computer program written to solve problems of
inductive inference in organic chemistry. This paper will use the
design of Heuristic DENDRAL and its performance on different problems
for a discussion of the following topics: 1. the design for generality;
2. the performance problems attendant upon too much generality; 3. the
coupling of expertise to the general problem solving processes; 4. the
symbiotic relationship between generality and expertness, and the
implications of this symbiosis for the study and design of problem
solving systems. We conclude the paper with a view of the design for a
general problem solver that is a variant of the "big switch" theory of
generality.
CS-TR-70-176
Report Number: CS-TR-70-178
Institution: Stanford University, Department of Computer Science
Title: Research in the Computer Science Department and selected other research in computing at Stanford University
Author: Forsythe, George E.
Author: Miller, William F.
Date: October 1970
Abstract:
The research program of the Computer Science Department can perhaps be
best summarized in terms of its research projects. The chart on page ii
lists the projects and the participation by faculty and students. The
sections following the chart provide descriptions of the individual
projects. There are a number of projects in other schools or
departments which are making significant contributions to computer
science; and these add to the total computer environment. Descriptions
of a few of these projects are also included with this report. This
list of projects outside of Computer Science does not purport to be
complete or even representative.
CS-TR-70-178
Report Number: CS-TR-70-179
Institution: Stanford University, Department of Computer Science
Title: MLISP
Author: Smith, David Canfield
Date: October 1970
Abstract:
MLISP is a high level list-processing and symbol-manipulation language
based on the programming language LISP. MLISP programs are translated
into LISP programs and then executed or compiled. MLISP exists for two
purposes: (1) to facilitate the writing and understanding of LISP
programs; (2) to remedy certain important deficiencies in the
list-processing ability of LISP.
CS-TR-70-179
Report Number: CS-TR-70-183
Institution: Stanford University, Department of Computer Science
Title: Machine learning through signature trees: applications to human speech
Author: White, George M.
Date: October 1970
Abstract:
Signature tree "machine learning", pattern recognition heuristics are
investigated for the specific problem of computer recognition of human
speech. When the data base of given utterances is insufficient to
establish trends with confidence, a large number of feature extractors
must be employed and "recognition" of an unknown pattern made by
comparing its feature values with those of known patterns. When the
data base is replete, a "signature" tree can be constructed and
recognition can be achieved by the evaluation of a select few features.
Learning results from selecting an optimal minimal set of features to
achieve recognition. Properties of signature trees and the heuristics
for this type of learning are of primary interest in this exposition.
CS-TR-70-183
Report Number: CS-TR-70-184
Institution: Stanford University, Department of Computer Science
Title: A note on a conjecture of L. J. Mordell
Author: Malcolm, Michael A.
Date: November 1970
Abstract:
A computer proof is described for a previously unsolved problem
concerning the inequality $\sum{i=1}{n} x_i/(x_{i+1}\ + x_{i+2}) \geq\
frac{n}{2}$.
CS-TR-70-184
Report Number: CS-TR-70-185
Institution: Stanford University, Department of Computer Science
Title: Graph program simulation
Author: Nelson, Edward C.
Date: October 1970
Abstract:
This reports the simulation of a parallel processing system based on a
directed graph representation of parallel computations. The graph
representation is based on the model developed by Duane Adams in which
programs are written as directed graphs whose nodes represent
operations and whose edges represent data flow. The first part of the
report describes a simulator which interprets these graph programs. The
second part describes the use of the simulator in a hypothetical
environment which has an unlimited number of processors and an
unlimited amount of memory. Three programs, a trapezoidal quadrature, a
sort and a matrix multiplication, were used to study the effect of
varying the relative speed of primitive operations on computation time
with problem size. The system was able to achieve a high degree of
parallelism. For example, the simulator multiplied two n by n matrices
in a simulated time proportional to n.
CS-TR-70-185
Report Number: CS-TR-70-187
Institution: Stanford University, Department of Computer Science
Title: MPL, Mathematical Programming Language: specification manual for Committee review
Author: Eisenstat, Stanley C.
Author: Magnanti, Thomas L.
Author: Maier, Steven F.
Author: McGrath, Michael B.
Author: Nicholson, Vincent J.
Author: Riedl, Christiane
Author: Dantzig, George B.
Date: November 1970
Abstract:
Mathematical Programming Language (MPL) is intended as a highly
readable, user oriented, programming tool for use in the writing and
testing of mathematical algorithms, in particular experimental
algorithms for solving large-scale linear programs. It combines the
simplicity of standard mathematical notation with the power of complex
data structures. Variables may be implicitly introduced into a program
by their use in the statement in which they first appear. No formal
defining statement is necessary. Statements of the "let" and "where"
type are part of the language. Included within the allowable data
structures of MPL are matrices, partitioned matrices, and
multidimensional arrays. Ordered sets are included as vectors with
their constructs closely paralleling those found in set theory.
Allocation of storage is dynamic, thereby eliminating the need for a
data manipulating subset of the language, as is characteristic of most
high level scientific programming languages. This report summarizes the
progress that has been made to date in developing MPL. It contains a
specification manual, examples of the application of the language, and
the future directions and goals of the project. A version of MPL,
called MPL/70, has been implemented using PL/I as a translator. This
will be reported separately. Until fully implemented, MPL is expected
to serve primarily as a highly readable communication language for
mathematical algorithms.
CS-TR-70-187
Report Number: CS-TR-71-188
Institution: Stanford University, Department of Computer Science
Title: The translation of 'go to' programs to 'while' programs
Author: Ashcroft, Edward A.
Author: Manna, Z ohar
Date: January 1971
Abstract:
In this paper we show that every flowchart program can be written
without $underline{go to}$ statements by using $underline{while}$
statements. The main idea is to introduce new variables to preserve the
values of certain variables at particular points in the program; or
alternatively, to introduce special boolean variables to keep
information about the course of the computation. The 'while' programs
produced yield the same final results as the original flowchart program
but need not perform computations in exactly the same way. However, the
new programs do preserve the 'topology' of the original flowchart
program, and are of the same order of efficiency. We also show that
this cannot be done in general without adding variables.
CS-TR-71-188
Report Number: CS-TR-71-189
Institution: Stanford University, Department of Computer Science
Title: Mathematical theory of partial correctness
Author: Manna, Z ohar
Date: January 1971
Abstract:
In this work we show that it is possible to express most properties
regularly observed in algorithms in terms of 'partial correctness'
(i.e., the property that the final results of the algorithm, if any,
satisfy some given input-output relation). This result is of special
interest since 'partial correctness' has already been formulated in
predicate calculus and in partial function logic for many classes of
algorithms.
CS-TR-71-189
Report Number: CS-TR-71-190
Institution: Stanford University, Department of Computer Science
Title: An n log n algorithm for minimizing states in a finite automaton
Author: Hopcroft, John E.
Date: January 1971
Abstract:
An algorithm is given for minimizing the number of states in a finite
automaton or for determining if two finite automata are equivalent. The
asymptotic running time of the algorithm is bounded by k n log n where
k is some constant and n is the number of states. The constant k
depends linearly on the size of the input alphabet.
CS-TR-71-190
Report Number: CS-TR-71-191
Institution: Stanford University, Department of Computer Science
Title: An introduction to the direct emulation of control structures by a parallel micro-computer
Author: Lesser, Victor R.
Date: January 1971
Abstract:
This paper is an investigation of the organization of a parallel
micro-computer designed to emulate a wide variety of sequential and
parallel computers. This micro-computer allows tailoring of its control
structure so that it is appropriate for the particular computer to be
emulated. The control structure of this micro-computer is dynamically
modified by changing the organization of its data structure for
control. The micro-computer contains six primitive operators which
dynamically manipulate and generate a tree type data structure for
control. This data structure for control is used as a syntactic
framework within which particular implementations of control concepts,
such as iteration, recursion, co-routines, parallelism, interrupts,
etc., can be easily expressed. The major features of the control data
structure and the primitive operators are: (1) once the fixed control
and data linkages among processes have been defined, they need not be
rebuilt on subsequent executions of the control structure; (2)
micro-programs may be written so that they execute independently of the
number of physical processors present and still take advantage of
available processors; (3) control structures for I/O processes,
data-accessing processes, and computational processes are expressed in
a single uniform framework. An emulator programmed on this
micro-computer works as an iterative two-step process similar to the
process of dynamic compilation or run time macro-expansion. This
dynamic compilation approach to emulation differs considerably from the
conventional approach to emulation, and provides a unifying approach to
the emulation of a wide variety of sequential and parallel computers.
CS-TR-71-191
Report Number: CS-TR-71-192
Institution: Stanford University, Department of Computer Science
Title: An n log n algorithm for isomorphism of planar triply connected graphs
Author: Hopcroft, John E.
Date: January 1971
Abstract:
It is shown that the isomorphism problem for triply connected planar
graphs can be reduced to the problem of minimizing states in a finite
automaton. By making use of an n log n algorithm for minimizing the
number of states in a finite automaton, an algorithm for determining
whether two planar triply connected graphs are isomorphic is developed.
The asymptotic growth rate of the algorithm grows as n log n where n is
the number of vertices in the graph.
CS-TR-71-192
Report Number: CS-TR-71-193
Institution: Stanford University, Department of Computer Science
Title: Intention, memory, and computer understanding
Author: Schank, Roger C.
Date: January 1971
Abstract:
Procedures are described for discovering the intention of a speaker by
relating the Conceptual Dependency representation of the speaker's
utterance to the computer's world model such that simple implications
can be made. These procedures function at levels higher than that of
the sentence by allowing for predictions based on context and the
structure of the memory. Computer understanding of natural language is
shown to consist of the following parts: assigning a conceptual
representation to an input; relating that representation to the memory
such as to extract the intention of the speaker; and selecting the
correct response type triggered by such an utterance according to the
situation.
CS-TR-71-193
Report Number: CS-TR-71-195
Institution: Stanford University, Department of Computer Science
Title: The direct solution of the discrete Poisson equation on irregular regions
Author: Buzbee, B. L.
Author: Dorr, Fred W.
Author: George, John Alan
Author: Golub, Gene H.
Date: December 1970
Abstract:
There are several very fast direct methods which can be used to solve
the discrete Poisson equation on rectangular domains. We show that
these methods can also be used to treat problems on irregular regions.
CS-TR-71-195
Report Number: CS-TR-71-197
Institution: Stanford University, Department of Computer Science
Title: MIX/360 user's guide
Author: Knuth, Donald E.
Author: Sites, Richard L.
Date: March 1971
Abstract:
MIX/360 is an assembler and simulator for the hypothetical MIX machine,
which is described for example in Knuth's $\underline{The Art of
Computer Programming}$, Section 1.3.1. The system contains several
debugging aids to help program construction and verification.
CS-TR-71-197
Report Number: CS-TR-71-201
Institution: Stanford University, Department of Computer Science
Title: Planarity testing in V log V steps: extended abstract
Author: Hopcroft, John E.
Author: Tarjan, Robert Endre
Date: February 1971
Abstract:
An efficient algorithm is presented for determining whether or not a
given graph is planar. If V is the number of vertices in the graph, the
algorithm requires time proportional to V log V and space proportional
to V when run on a random-access computer. The algorithm constructs the
facial boundaries of a planar representation without backup, using
extensive list-processing features to speed computation. The
theoretical time bound improves on that of previously published
algorithms. Experimental evidence indicates that graphs with a few
thousand edges can be tested within seconds.
CS-TR-71-201
Report Number: CS-TR-71-202
Institution: Stanford University, Department of Computer Science
Title: Communicating semaphores
Author: Saal, Harry J.
Author: Riddle, William E.
Date: February 1971
Abstract:
This paper describes two extensions to the semaphore operators
originally introduced by Dijkstra. These extensions can be used to
reduce: 1) the number of semaphore references; 2) the time spent in
critical sections; and 3) the number of distinct semaphores required
for proper synchronization without greatly increasing the time required
for semaphore operations. Communicating semaphores may be utilized not
only for synchronization but also for message switching, resource
allocation from pools and as general queueing mechanisms.
CS-TR-71-202
Report Number: CS-TR-71-203
Institution: Stanford University, Department of Computer Science
Title: The Heuristic DENDRAL program for explaining empirical data
Author: Buchanan, Bruce G.
Author: Lederberg, Joshua
Date: February 1971
Abstract:
The Heuristic DENDRAL program uses an information processing model of
scientific reasoning to explain experimental data in organic chemistry.
This report summarizes the organization and results of the program for
computer scientists. The program is divided into three main parts:
planning, structure generation, and evaluation. The planning phase
infers constraints on the search space from the empirical data input to
the system. The structure generation phase searches a tree whose
termini are models of chemical molecules using pruning heuristics of
various kinds. The evaluation phase tests the candidate structures
against the original data. Results of the program's analyses of some
test data are discussed.
CS-TR-71-203
Report Number: CS-TR-71-204
Institution: Stanford University, Department of Computer Science
Title: FETE: a Fortran execution time estimator
Author: Ingalls, Daniel H. H.
Date: February 1971
Abstract:
If you want to live cheaply, you must make a list of how much money is
spent on each thing every day. This enumeration will quickly reveal the
principal areas of waste. The same method works for saving computer
time. Originally, one had to put his own timers and counters into a
program to determine the distribution of time spent in each part.
Recently several automated systems have appeared which either insert
counters automatically or interrupt the program during its execution to
produce the tallies. FETE is a system of the former type which has two
outstanding characteristics: it is very easy to implement and it is
very easy to use. By demonstrating such convenience, it should
establish execution timing as a standard tool in program development.
CS-TR-71-204
Report Number: CS-TR-71-205
Institution: Stanford University, Department of Computer Science
Title: An algebraic definition of simulation between programs
Author: Milner, Robin
Date: February 1971
Abstract:
A simulation relation between programs is defined which is
quasi-ordering. Mutual simulation is then an equivalence relation, and
by dividing out by it we abstract from a program such details as how
the sequencing is controlled and how data is represented. The
equivalence classes are approxiamtions to the algorithms which are
realized, or expressed, by their member programs. A technique is given
and illustrated for proving simulation and equivalence of programs;
there is an analogy with Floyd's technique for proving correctness of
programs. Finally, necessary and sufficient conditions for simulation
are given.
CS-TR-71-205
Report Number: CS-TR-71-207
Institution: Stanford University, Department of Computer Science
Title: Efficient algorithms for graph manipulation
Author: Hopcroft, John E.
Author: Tarjan, Robert Endre
Date: March 1971
Abstract:
Efficient algorithms are presented for partitioning a graph into
connected components, biconnected components and simple paths. The
algorithm for partitioning of a graph into simple paths is iterative
and each iteration produces a new path between two vertices already on
paths. (The start vertex can be specified dynamically.) If V is the
number of vertices and E is the number of edges each algorithm requires
time and space proportional to max(V,E) when executed on a random
access computer.
CS-TR-71-207
Report Number: CS-TR-71-209
Institution: Stanford University, Department of Computer Science
Title: Project technical report
Author: McCarthy, John
Author: Samuel, Arthur L.
Author: Feigenbaum, Edward A.
Author: Lederberg, Joshua
Date: March 1971
Abstract:
An overview is presented of current research at Stanford in artificial
intelligence and heuristic programming. This report is largely the text
of a proposal to the Advanced Research Projects Agency for fiscal years
1972-73.
CS-TR-71-209
Report Number: CS-TR-71-210
Institution: Stanford University, Department of Computer Science
Title: ACCESS: a program for the catalog and access of information
Author: Purdy, J. Gerry
Date: March 1971
Abstract:
ACCESS is a program for the catalog and access of information. The
program is primarily designed for and intended to handle a personal
library, although larger applications are possible. ACCESS produces a
listing of all entries by locator code (so one knows where to find the
entry in his library), a listing of entry titles by user-specified
category codes, and a keyword-in-context KWIC listing (each keyword
specified by the user). ACCESS is presently programmed in FORTRAN and
operates on any IBM System/360 under OS (it uses the IBM SORT/MERGE
package). It is anticipated a machine language version (soon to be
implemented) will greatly decrease the running time of the program.
CS-TR-71-210
Report Number: CS-TR-71-211
Institution: Stanford University, Department of Computer Science
Title: Algorithms to reveal properties of floating-point arithmetic
Author: Malcolm, Michael A.
Date: March 1971
Abstract:
Two algorithms are presented in the form of Fortran subroutines. Each
subroutine computes the radix and number of digits of the
floating-point numbers and whether rounding or chopping is done by the
machine on which it is run. The methods are shown to work on any
"reasonable" floating-point computer.
CS-TR-71-211
Report Number: CS-TR-71-212
Institution: Stanford University, Department of Computer Science
Title: Time and memory requirements for solving linear systems
Author: Morgana, Maria Aurora
Date: March 1971
Abstract:
The Computer Science Department program library contains a number of
ALGOL W procedures and FORTRAN subroutines which can be used to solve
systems of linear equations. This report describes the results of tests
to determine the amount of time and memory required to solve systems of
various orders.
CS-TR-71-212
Report Number: CS-TR-71-213
Institution: Stanford University, Department of Computer Science
Title: The switchyard problem: sorting using networks of queues and stacks
Author: Tarjan, Robert Endre
Date: April 1971
Abstract:
The problem of sorting a sequence of numbers using a network of queues
and stacks is presented. A characterization of sequences sortable using
parallel queues is given, and partial characterizations of sequences
sortable using parallel stacks and networks of queues are given.
CS-TR-71-213
Report Number: CS-TR-71-215
Institution: Stanford University, Department of Computer Science
Title: PL360 (revised): a programming language for the IBM 360
Author: Malcolm, Michael A.
Date: May 1972
Abstract:
In 1968, N. Wirth (Jan. JACM) published a formal description of PL360,
a programming language designed specifically for the IBM 360. PL360 has
an appearance similar to that of Algol, but it provides the facilities
of a symbolic machine language. Since 1968, numerous extensions and
modifications have been made to the PL360 compiler which was originally
designed and implemented by N. Wirth and J. Wells. Interface and
input-output subroutines have been written which allow the use of PL360
under OS, DOS, MTS and Orvyl. A formal description of PL360 as it is
presently implemented is given. The description of the language is
followed by sections on the use of PL360 under various operating
systems, namely OS, DOS and MTS. Instructions on how to use the PL360
compiler and PL360 programs in an interactive mode under the Orvyl
time-sharing monitor are also included.
CS-TR-71-215
Report Number: CS-TR-71-217
Institution: Stanford University, Department of Computer Science
Title: Decidable properties of monadic functional schemas
Author: Ashcroft, Edward A.
Author: Manna, Z ohar
Author: Pneuli, Amir
Date: July 1971
Abstract:
We define a class of (monadic) functional schemas which properly
includes 'Ianov' flowchart schemas. We show that the termination,
divergence and freedom problems for functional schemas are decidable.
Although it is possible to translate a large class of non-free
functional schemas into equivalent free functional schemas, we show
that this cannot be done in general. We show also that the equivalence
problem for free functional schemas is decidable. Most of the results
are obtained from well-known results in Formal Languages and Automata
Theory.
CS-TR-71-217
Report Number: CS-TR-71-221
Institution: Stanford University, Department of Computer Science
Title: A heuristic programming study of theory formation in science
Author: Buchanan, Bruce G.
Author: Feigenbaum, Edward A.
Author: Lederberg, Joshua
Date: July 1971
Abstract:
The Meta-DENDRAL program is a vehicle for studying problems of theory
formation in science. The general strategy of Meta-DENDRAL is to reason
from data to plausible generalizations and then to organize the
generalizations into a unified theory. Three main subproblems are
discussed: (1) explain the experimental data for each individual
chemical structure, (2) generalize the results from each structure to
all structures, and (3) organize the generalizations into a unified
theory. The program is built upon the concepts and programmed routines
already available in the Heuristic DENDRAL performance program, but
goes beyond the performance program in attempting to formulate the
theory which the performance program will use.
CS-TR-71-221
Report Number: CS-TR-71-224
Institution: Stanford University, Department of Computer Science
Title: Parallel programming
Author: Ershov, Andrei P.
Date: July 1971
Abstract: This report is based on lectures given at Stanford University by Dr. Ershov in November, 1970.
CS-TR-71-224
Report Number: CS-TR-71-225
Institution: Stanford University, Department of Computer Science
Title: Numerical methods for computing angles between linear subspaces
Author: Bjoerck, Ake
Author: Golub, Gene H.
Date: July 1971
Abstract:
Assume that two subspaces F and G of unitary space are defined as the
ranges (or nullspaces) of given rectangular matrices A and B. Accurate
numerical methods are developed for computing the principal angles
$\theta_k (F,G)$ and orthogonal sets of principal vectors $u_k\
\epsilon\ F$ and $v_k\ \epsilon\ G$, k = 1,2,..., q = dim(G) $\leq$
dim(F). An important application in statistics is computing the
canonical correlations $\sigma_k\ = cos \theta_k$ between two sets of
variates. A perturbation analysis shows that the condition number for
$\theta_k$ essentially is max($\kappa (A),\kappa (B)$), where $\kappa$
denotes the condition number of a matrix. The algorithms are based on a
preliminary QR-factorization of A and B (or $A^H$ and $B^H$), for which
either the method of Householder transformations (HT) or the modified
Gram-Schmidt method (MGS) is used. Then cos $\theta_k$ and sin
$\theta_k$ are computed as the singular values of certain related
matrices. Experimental results are given, which indicates that MGS
gives $\theta_k$ with equal precision and fewer arithmetic operations
than HT. However, HT gives principal vectors, which are orthogonal to
working accuracy, which is not in general true for MGS. Finally the
case when A and/or B are rank deficient is discussed.
CS-TR-71-225
Report Number: CS-TR-71-226
Institution: Stanford University, Department of Computer Science
Title: SIMPLE: a simple precedence translator writing system
Author: George, James E.
Date: July 1971
Abstract:
SIMPLE is a translator writing system composed of a simple precedence
syntax analyzer and a semantic constructor and is implemented in PL/I.
It provides an error diagnostic and recovery mechanism for any system
implemented using SIMPLE. The removal of precedence conflicts is
discussed in detail with several examples. The utilization of SIMPLE is
illustrated by defining a command language meta system for the
construction of scanners for a wide variety of command oriented
languages. This meta system is illustrated by defining commands from
several text editors.
CS-TR-71-226
Report Number: CS-TR-71-228
Institution: Stanford University, Department of Computer Science
Title: Function minimization and automatic therapeutic control
Author: Kaufman, Linda C.
Date: July 1971
Abstract: No abstract available.
CS-TR-71-228
Report Number: CS-TR-71-229
Institution: Stanford University, Department of Computer Science
Title: Variational study of nonlinear spline curves
Author: Lee, Erastus H.
Author: Forsythe, George E.
Date: August 1971
Abstract:
This is an exposition of the variational and differential properties of
nonlinear spline curves, based on the Euler-Bernoulli theory for the
bending of thin beams or elastica. For both open and closed splines
through prescribed nodal points in the euclidean plane, various types
of nodal constraints are considered, and the corresponding algebraic
and differential equations relating curvature, angle, arc length, and
tangential force are derived in a simple manner. The results for closed
splines are apparently new, and they cannot be derived by the
consideration of a constrained conservative system. There is a survey
of the scanty recent literature.
CS-TR-71-229
Report Number: CS-TR-71-230
Institution: Stanford University, Department of Computer Science
Title: ALGOL W reference manual
Author: Sites, Richard L.
Date: February 1972
Abstract:
"A Contribution to the Development of ALGOL" by Niklaus Wirth and C. A.
R. Hoare was the basis for a compiler developed for the IBM 360 at
Stanford University. This report is a description of the implemented
language, ALGOL W. Historical background and the goals of the language
may be found in the Wirth and Hoare paper. This manual refers to the
version of the Algol W compiler dated 16 January 1972.
CS-TR-71-230
Report Number: CS-TR-71-234
Institution: Stanford University, Department of Computer Science
Title: Some modified eigenvalue problems
Author: Golub, Gene H.
Date: August 1971
Abstract:
We consider the numerical calculation of several eigenvalue problems
which require some manipulation before the standard algorithms may be
used. This includes finding the stationary values of a quadratic form
subject to linear constraints and determining the eigenvalues of a
matrix which is modified by a matrix of rank one. We also consider
several inverse eigenvalue problems. This includes the problem of
computing the Gauss-Radau and Gauss-Lobatto quadrature rules. In
addition, we study several eigenvalue problems which arise in least
squares.
CS-TR-71-234
Report Number: CS-TR-71-236
Institution: Stanford University, Department of Computer Science
Title: Numerical computations for univariate linear models
Author: Golub, Gene H.
Author: Styan, George P. H.
Date: September 1971
Abstract:
We consider the usual univariate linear model E($\underset ~\to y$) =
$\underset ~\to X \underset ~\to \gamma$ , V ($\underset ~\to y$) =
$\sigma^2 \underset ~\to I$. In Part One of this paper $\underset ~\to
X$ has full column rank. Numerically stable and efficient computational
procedures are developed for the least squares estimation of $\underset
~\to \gamma$ and the error sum of squares. We employ an orthogonal
triangular decomposition of $\underset ~\to X$ using Householder
transformations. A lower bound for the condition number of $\underset
~\to X$ is immediately obtained from this decomposition. Similar
computational procedures are presented for the usual F-test of the
general linear hypothesis $\underset ~\to L\ ' \underset ~\to \gamma$ =
$\underset ~\to 0$ ; $\underset ~\to L\ ' \underset ~\to \gamma$ =
$\underset ~\to m$ is also considered for $\underset ~\to m\ \neq\ 0$.
Updating techniques are given for adding to or removing from
($\underset ~\to X ,\underset ~\to y$) a row, a set of rows or a column
. In Part Two, $\underset ~\to X$ has less than full rank. Least
squares estimates are obtained using generalized inverses. The function
$\underset ~\to L '\underset ~\to \gamma$ is estimable whenever it
admits an unbiased estimator linear in $\underset ~\to y$. We show how
to computationally verify estimability of $\underset ~\to L '\underset
~\to \gamma$ and the equivalent testability of $\underset ~\to L
'\underset ~\to \gamma\ = \underset ~\to 0$.
CS-TR-71-236
Report Number: CS-TR-71-237
Institution: Stanford University, Department of Computer Science
Title: A generalization of the divide-sort-merge strategy for sorting networks
Author: Van Voorhis, David C.
Date: August 1971
Abstract:
With a few notable exceptions the best sorting networks known have
employed a "divide-sort-merge" strategy. That is, the N inputs are
divided into 2 groups - - normally of size $\lceil \frac{1}{2} N\rceil$
and $\lfloor \frac{1}{2} N\rfloor$ [Here $\lceil x\rceil$ denotes the
smallest integer greater than or equal to x, whereas $\lfloor x\rfloor$
denotes the largest integer less than or equal to x] - - that are
sorted independently and then "merged" together to form a single sorted
sequence. An N-sorter network that uses this strategy consists of 2
smaller sorting networks followed by a merge network. The best merge
networks known are also constructed recursively, using 2 smaller merge
networks followed by a simple arrangement of $\lceil \frac{1}{2}
N\rceil$ - 1 comparators. We consider a generalization of the
divide-sort-merge strategy in which the N inputs are divided into g
$\geq$ 2 disjoint groups that are sorted independently and then merged
together. The merge network that combines these g sorted groups uses d
$\geq$ 2 smaller merge networks as an initial subnetwork. The two
parameters g and d together define what we call a "[g,d]" strategy. A
[g,d] N-sorter network consists of g smaller sorting networks followed
by a [g,d] merge network. The initial portion of the [g,d] merge
network consists of d smaller merge networks; the final portion, which
we call the "f-network," includes whatever additional comparators are
required to complete the merge. When g = d = 2, the f-network is a
simple arrangement of $\lceil \frac{1}{2} N\rceil$ - 1 comparators;
however, for larger g,d the structure of the [g,d] f-network becomes
increasingly complicated. In this paper we describe how to construct
[g,d] f-networks for arbitrary g,d. For N > 8 the resulting [g,d]
N-sorter networks are more economical than any previous networks that
use the divide-sort-merge strategy; for N > 34 the resulting
networks are more economical than previous networks of any
construction. The [4,4] N-sorter network described in this paper
requires $\frac{1}{4} N{(log_2 N)}^2\ - \frac{1}{3} N(log_2 N) + O(N)$
comparators, which represents an asymptotic improvement of
$\frac{1}{12} N(log_2 N)$ comparators over the best previous N-sorter.
We indicate that special constructions (not described in this paper)
have been found for [$2^r , 2^r$] f-networks, which lead to an N-sorter
network that requires only .25 $N{(log_2 N)}^2\ - .372 N(log_2 N) +
O(N)$ comparators.
CS-TR-71-237
Report Number: CS-TR-71-238
Institution: Stanford University, Department of Computer Science
Title: A lower bound for sorting networks that use the divide-sort-merge strategy
Author: Van Voorhis, David C.
Date: August 1971
Abstract:
Let $M_g (g^{k+1})$ represent the minimum number of comparators
required by a network that merges g sorted multisets containing $g^k$
members each. In this paper we prove that $M_g (g^{k+1}) \geq\ g
M_g(g^k) + g^{k-1} \sum_{\ell =2}^{g} \lfloor (\ell -1)g/\ell\rfloor$.
From this relation we are able to show that an N-sorter network which
uses the g-way divide-sort-merge strategy must contain at least order
$N{(log_2 N)}^2$ comparators.
CS-TR-71-238
Report Number: CS-TR-71-239
Institution: Stanford University, Department of Computer Science
Title: Large [g,d] sorting networks
Author: Van Voorhis, David C.
Date: August 1971
Abstract:
With only a few exceptions the minimum-comparator N-sorter networks
employ the generalized "divide-sort-merge" strategy. That is, the N
inputs are divided among g $\geq$ 2 smaller sorting networks -- of size
$N_1,N_2,...,N_g$, where $N = \sum_{k=1}^{g} N_k$ -- that comprise the
initial portion of the N-sorter network. The remainder of the N-sorter
is a comparator network that merges the outputs of the $N_1-, N_2-,
...,$ and $N_g$-sorter networks into a single sorted sequence. The most
economical merge networks yet designed, known as the "[g,d]" merge
networks, consist of d smaller merge networks -- where d is a common
divisor of $N_1,N_2,...,N_g$ -- followed by a special comparator
network labeled a "[g,d] f-network." In this paper we describe special
constructions for $[2^r,2^r]$ f-networks, r > 1, which enable us to
reduce the number of comparators required by a large N-sorter network
from $.25N {log_2 N)}^2 - .25N(log_2 N) + O(N) to .25N{(log_2 N)}^2 -
.37N(log_2 N) + O(N)$.
CS-TR-71-239
Report Number: CS-TR-71-240
Institution: Stanford University, Department of Computer Science
Title: Correctness of two compilers for a Lisp subset
Author: London, Ralph L.
Date: October 1971
Abstract:
Using mainly structural induction, proofs of correctness of each of two
running Lisp compilers for the PDP-10 computer are given. Included are
the rationale for presenting these proofs, a discussion of the proofs,
and the changes needed to the second compiler to complete its proof.
CS-TR-71-240
Report Number: CS-TR-71-242
Institution: Stanford University, Department of Computer Science
Title: The frame problem and related problems in artificial intelligence
Author: Hayes, Patrick J.
Date: November 1971
Abstract:
The frame problem arises in considering the logical structure of a
robot's beliefs. It has been known for some years, but only recently
has much progress been made. The problem is described and discussed.
Various suggested methods for its solution are outlined, and described
in a uniform notation. Finally, brief consideration is given to the
problem of adjusting a belief system in the face of evidence which
contradicts beliefs. It is shown that a variation on the situation
notation of (McCarthy and Hayes, 1969) permits an elegant approach, and
relates this problem to the frame problem.
CS-TR-71-242
Report Number: CS-TR-71-246
Institution: Stanford University, Department of Computer Science
Title: A resemblance test for the validation of a computer simulation of paranoid processes
Author: Colby, Kenneth Mark
Author: Hilf, Franklin Dennis
Author: Weber, Sylvia
Author: Kraemer, Helena C.
Date: November 1971
Abstract:
A computer simulation of paranoid processes in the form of a dialogue
algorithm was subjected to a validation study using an experimental
resemblance test in which judges rated degrees of paranoia present in
initial psychiatric interviews of both paranoid patients and of
versions of the paranoid model. The statistical results indicate a
satisfactory degree of resemblance between the two groups of
interviews. It is concluded that the model provides a successful
simulation of naturally occuring paranoid processes.
CS-TR-71-246
Report Number: CS-TR-71-247
Institution: Stanford University, Department of Computer Science
Title: One small head -- some remarks on the use of 'model' in linguistics
Author: Wilks, Yorick A.
Date: December 1971
Abstract:
I argue that the present situation in formal linguistics, where much
new work is presented as being a "model of the brain", or of "human
language behavior", is an undesirable one. My reason for this judgement
is not the conservative (Braithwaitian) one that the entities in
question are not really models but theories. It is rather that they are
called models because they cannot be theories of the brain at the
present stage of brain research, and hence that the use of "model" in
this context is not so much aspirational as resigned about our total
ignorance of how the brain stores and processes linguistic information.
The reason such explanatory entities cannot be theories is that this
ignorance precludes any "semantic ascent" up the theory; i.e.,
interpreting the items of the theory in terms of observables. And the
brain items, whatever they may be, are not, as Chomsky has sometimes
claimed, in the same position as the "occult entities" of Physics like
Gravitation; for the brain items are not theoretically unreachable,
merely unreached. I then examine two possible alternate views of what
linguistic theories should be proffered as theories of: theories of
sets of sentences, and theories of a particular class of algorithms. I
argue for a form of the latter view, and that its acceptance would also
have the effect of making Computational Linguistics a central part of
Linguistics, rather than the poor relation it is now. I examine a
distinction among "linguistic models" proposed recently by Mey, who was
also arguing for the self-sufficiency of Computational Linguistics,
though as a "theory of performance". I argue that his distinction is a
bad one, partly for the reasons developed above and partly because he
attempts to tie it to Chomsky's inscrutable competence-performance
distinction. I conclude that the independence and self-sufficiency of
Computational Linguistics are better supported by the arguments of this
paper.
CS-TR-71-247
Report Number: CS-TR-71-249
Institution: Stanford University, Department of Computer Science
Title: An annotated bibliography on the construction of compilers
Author: Pollack, Bary W.
Date: December 1971
Abstract:
This bibliography is divided into 9 sections: 1. General Information on
Compiling Techniques 2. Syntax- and Base-Directed Parsing 3. Parsing in
General 4. Resource Allocation 5. Errors - Detection and Correction 6.
Compiler Implementation in General 7. Details of Compiler Construction
8. Additional Topics 9. Miscellaneous Related References Within each
section the entries are alphabetical by author. Keywords describing the
entry will be found for each entry set off by pound signs (#). Some
amount of cross-referencing has been done; e.g., entries which fall
into Section 3 as well as Section 7 will generally be found in both
sections. However, entries will be found listed only under the
principle or first author's name. "Computing Reviews" citations are
given following the annotation when available.
CS-TR-71-249
Report Number: CS-TR-71-250
Institution: Stanford University, Department of Computer Science
Title: Program schemas with equality
Author: Chandra, Ashok K.
Author: Manna, Z ohar
Date: December 1971
Abstract:
We discuss the class of program schemas augmented with equality tests,
that is, tests of equality between terms. In the first part of the
paper we discuss and illustrate the "power" of equality tests. It turns
out that the class of program schemas with equality is more powerful
than the "maximal" classes of schemas suggested by other investigators.
In the second part of the paper we discuss the decision problems of
program schemas with equality. It is shown for example that while the
decision problems normally considered for schemas (such as halting,
divergence, equivalence, isomorphism and freedom) are solvable for
Ianov schemas, they all become unsolvable if general equality tests are
added. We suggest, however, limited equality tests which can be added
to certain subclasses of program schemas while preserving their
solvable properties.
CS-TR-71-250
Report Number: CS-TR-72-252
Institution: Stanford University, Department of Computer Science
Title: Large-scale linear programming using the Cholesky factorization.
Author: Saunders, Michael A.
Date: January 1972
Abstract:
A variation of the revised simplex method is proposed for solving the
standard linear programming problem. The method is derived from an
algorithm recently proposed by Gill and Murray, and is based upon the
orthogonal factorization B = LQ or, equivalently, upon the Cholesky
factorization ${BB}^T = {LL}^T$ where B is the usual square basis, L is
lower triangular and Q is orthogonal. We wish to retain the favorable
numerical properties of the orthogonal factorization, while extending
the work of Gill and Murray to the case of linear programs which are
both large and sparse. The principal property exploited is that the
Cholesky factor L depends only on $underline{which}$ variables are in
the basis, and not upon the $underline{order}$ in which they happen to
enter. A preliminary ordering of the rows of the full data matrix
therefore promises to ensure that L will remain sparse throughout the
iterations of the simplex method. An initial (in-core) version of the
algorithm has been implemented in Algol W on the IBM 360/91 and tested
on several medium-scale problems from industry (up to 930 constraints).
While performance has not been especially good on problems of high
density, the method does appear to be efficient on problems which are
very sparse, and on structured problems which have either generalized
upper bounding, block-angular, or staircase form.
CS-TR-72-252
Report Number: CS-TR-72-253
Institution: Stanford University, Department of Computer Science
Title: Total complexity and the inference of best programs.
Author: Feldman, Jerome A.
Author: Shields, Paul C.
Date: April 1972
Abstract:
Axioms for a total complexity measure for abstract programs are
presented. Essentially, they require that total complexity be an
unbounded increasing function of the Blum time and size measures.
Algorithms for finding the best program on a finite domain are
presented, and their limiting behaviour for infinite domains described.
For total complexity, there are important senses in which a machine
$underline{can}$ find the best program for a large class of functions.
CS-TR-72-253
Report Number: CS-TR-72-254
Institution: Stanford University, Department of Computer Science
Title: Von Neumann's comparison method for random sampling from the normal and other distributions.
Author: Forsythe, George E.
Date: January 1972
Abstract:
The author presents a generalization he worked out in 1950 of von
Neumann's method of generating random samples from the exponential
distribution by comparisons of uniform random numbers on (0,1). It is
shown how to generate samples from any distribution whose probability
density function is piecewise both absolutely continuous and monotonic
on ($-\infty$,$\infty$). A special case delivers normal deviates at an
average cost of only 4.036 uniform deviates each. This seems more
efficient than the Center-Tail method of Dieter and Ahrens, which uses
a related, but different, method of generalizing the von Neumann idea
to the normal distribution.
CS-TR-72-254
Report Number: CS-TR-72-255
Institution: Stanford University, Department of Computer Science
Title: Automatic programming.
Author: Feldman, Jerome A.
Date: February 1972
Abstract:
The revival of interest in Automatic Programming is considered. The
research is divided into direct efforts and theoretical developments
and the successes and prospects of each are described.
CS-TR-72-255
Report Number: CS-TR-72-256
Institution: Stanford University, Department of Computer Science
Title: Edmonds polyhedra and weakly hamiltonian graphs.
Author: Chvatal, Vaclav
Date: January 1972
Abstract:
Jack Edmonds developed a new way of looking at extremal combinatorial
problems and applied his technique with a great success to the problems
of the maximal-weight degree-constrained subgraphs. Professor C. St. J.
A. Nash-Williams suggested to use Edmonds' approach in the context of
hamiltonian graphs. In the present paper, we determine a new set of
inequalities (the "comb inequalities") which are satisfied by the
characteristic functions of hamiltonian circuits but are not explicit
in the straightforward integer programming formulation. A direct
application of the linear programming duality theorem then leads to a
new necessary condition for the existence of hamiltonian circuits; this
condition appears to be stronger than the previously known ones.
Relating linear programming to hamiltonian circuits, the present paper
can also be seen as a continuation of the work of Dantzig, Fulkerson
and Johnson on the travelling salesman problem.
CS-TR-72-256
Report Number: CS-TR-72-257
Institution: Stanford University, Department of Computer Science
Title: On "PASCAL," code generation, and the CDC 6000 computer.
Author: Wirth, Niklaus
Date: February 1972
Abstract:
"PASCAL" is a general purpose programming language with characteristics
similar to ALGOL 60, but with an enriched set of program- and data
structuring facilities. It has been implemented on the CDC 6000
computer. This paper discusses selected topics of code generation, in
particular the selection of instruction sequences to represent simple
operations on arithmetic, Boolean, and powerset operands. Methods to
implement recursive procedures are briefly described, and it is hinted
that the more sophisticated solutions are not necessarily also the
best. The CDC 6000 architecture appears as a frequent source of
pitfalls and nuisances, and its main trouble spots are scrutinized and
discussed.
CS-TR-72-257
Report Number: CS-TR-72-258
Institution: Stanford University, Department of Computer Science
Title: Some basic machine algorithms for integral order computations.
Author: Brown, Harold
Date: February 1972
Abstract:
Three machine implemented algorithms for computing with integral orders
are described. The algorithms are: 1. For an integral order R given in
terms of its left regular representation relative to any basis, compute
the nil radical J(R) and a left regular representation of R/J(R). 2.
For a semisimple order R given in terms of its left regular
representation relative to any basis, compute a new basis for R and the
associated left regular representation of R such that the first basis
element of the transformed basis is an integral multiple of the
identity element in Q $\bigotimes$ R. 3. Relative to any fixed Z -basis
for R, compute a unique canonical form for any given finitely generated
Z -submodule of Q $\bigotimes$ R described in terms of that basis.
CS-TR-72-258
Report Number: CS-TR-72-261
Institution: Stanford University, Department of Computer Science
Title: The differentiation of pseudoinverses and nonlinear least squares problems whose variables separate.
Author: Golub, Gene H.
Author: Pereyra, Victor
Date: February 1972
Abstract:
For given data ($t_i\ , y_i), i=1, \ldots ,m$ , we consider the least
squares fit of nonlinear models of the form F($\underset ~\to a\ ,
\underset ~\to \alpha\ ; t) = \sum_{j=1}^{n}\ g_j (\underset ~\to a )
\varphi_j (\underset ~\to \alpha\ ; t) , \underset ~\to a\ \epsilon
R^s\ , \underset ~\to \alpha\ \epsilon R^k\ $. For this purpose we
study the minimization of the nonlinear functional r($\underset ~\to a\
, \underset ~\to \alpha ) = \sum_{i=1}^{m} {(y_i - F(\underset ~\to a ,
\underset ~\to \alpha , t_i))}^2$. It is shown that by defining the
matrix ${ \{\Phi (\underset ~\to \alpha\} }_{i,j} = \varphi_j
(\underset ~\to \alpha ; t_i)$ , and the modified functional
$r_2(\underset ~\to \alpha ) = \l\ \underset ~\to y\ - \Phi (\underset
~\to \alpha )\Phi^+(\underset ~\to \alpha ) \underset ~\to y \l_2^2$,
it is possible to optimize first with respect to the parameters
$\underset ~\to \alpha$ , and then to obtain, a posteriori, the optimal
parameters $\overset ^\to {\underset ~\to a}$. The matrix
$\Phi^+(\underset ~\to \alpha$) is the Moore-Penrose generalized
inverse of $\Phi (\underset ~\to \alpha$), and we develop formulas for
its Frechet derivative under the hypothesis that $\Phi (\underset ~\to
\alpha$) is of constant (though not necessarily full) rank. From these
formulas we readily obtain the derivatives of the orthogonal projectors
associated with $\Phi (\underset ~\to \alpha$), and also that of the
functional $r_2(\underset ~\to \alpha$). Detailed algorithms are
presented which make extensive use of well-known reliable linear least
squares techniques, and numerical results and comparisons are given.
These results are generalizations of those of H. D. Scolnik [1971].
CS-TR-72-261
Report Number: CS-TR-72-263
Institution: Stanford University, Department of Computer Science
Title: A procedure for improving the upper bound for the number of n-ominoes.
Author: Klarner, David A.
Author: Rivest, Ronald L.
Date: February 1972
Abstract:
An n-omino is a plane figure composed of n unit squares joined together
along their edges. Every n-omino is generated by joining the edge of a
unit square to the edge of a unit square in some (n-1)-omino so that
the new square does not overlap any squares. Let t(n) denote the number
of n-ominoes, then it is known that the sequence ${((t(n))}^{1/n} : n =
1,2,\ldots )$ increases to a limit $\Theta$ , and 3.72 < $\Theta$
< 6.75 . A procedure exists for computing an increasing sequence of
numbers bounded above by $\Theta$. (Chandra recently showed that the
limit of this sequence is $\Theta$ .) In the present work we give a
procedure for computing a sequence of numbers bounded below by $\Theta$
. Whether or not the limit of this sequence is $\Theta$ remains an open
question. By computing the first ten terms of our sequence, we have
shown that $\Theta$ < 4.65 .
CS-TR-72-263
Report Number: CS-TR-72-264
Institution: Stanford University, Department of Computer Science
Title: An artificial intelligence approach to machine translation.
Author: Wilks, Yorick A.
Date: February 1972
Abstract:
The paper describes a system of semantic analysis and generation,
programmed in LISP 1.5 and designed to pass from paragraph length input
in English to French via an interlingual representation. A wide class
of English input forms will be covered, but the vocabulary will
initially be restricted to one of a few hundred words. With this subset
working, and during the current year (71-72), it is also hoped to map
the interlingual representation onto some predicate calculus notation
so as to make possible the answering of very simple questions about the
translated matter. The specification of the translation system itself
is complete, and its main points of interest that distinguish it from
other systems are: i) It translated phrase by phrase -- with facilities
for reordering phrases and establishing essential semantic
connectivities between them -- by mapping complex semantic structures
of "message" onto each phrase. These constitute the interlingual
representation to be translated. This matching is done without the
explicit use of a conventional syntax analysis, by taking as the
appropriate matched structure the "most dense" of the alternative
structures derived. This method has been found highly successful in
earlier versions of this analysis system. ii) The French output strings
are generated without the explicit use of a generative grammar. That is
done by means of STEREOTYPES: strings of French words, and functions
evaluating to French words, which are attached to English word senses
in the dictionary and built into the interlingual representation by the
analysis routines. The generation program thus receives an interlingual
representation that already contains both French output and implicit
procedures for assembling the output, since the stereotypes are in
effect recursive procedures specifying the content and production of
the ouput word strings. Thus the generation program at no time consults
a word dictionary or inventory of grammar rules. It is claimed that the
system of notation and translation described is a convenient one for
expressing and handling the items of semantic information that are
ESSENTIAL to any effective MT system, I discuss in some detail the
semantic information needed to ensure the correct choice of output
prepositions in French, a vital matter inadequately treated by
virtually all previous formalisms and projects.
CS-TR-72-264
Report Number: CS-TR-72-265
Institution: Stanford University, Department of Computer Science
Title: Primitive concepts underlying verbs of thought.
Author: Schank, Roger C.
Author: Goldman, Neil M.
Author: Rieger, Charles J.
Author: Riesbeck, Christopher K.
Date: February 1972
Abstract:
In order to create conceptual structures that will uniquely and
unambiguously represent the meaning of an utterance, it is necessary to
establish 'primitive' underlying actions and states into which verbs
can be mapped. This paper presents analyses of the most common mental
verbs in terms of such primitive actions and states. In order to
represent the way people speak about their mental processes, it was
necessary to add to the usual ideas of memory structure the notion of
Immediate Memory. It is then argued that there are only three primitive
mental ACTs.
CS-TR-72-265
Report Number: CS-TR-72-267
Institution: Stanford University, Department of Computer Science
Title: Mathematical Programming Language: an appraisal based on practical experiments.
Author: Bonzon, Pierre E.
Date: March 1972
Abstract:
The newly proposed Mathematical Programming Language is approached from
the user's point of view. To demonstrate its facility of use, three
programs are presented which solve large scale linear programming
problems with the generalized upper-bounding structure.
CS-TR-72-267
Report Number: CS-TR-72-268
Institution: Stanford University, Department of Computer Science
Title: Degrees and matchings.
Author: Chvatal, Vaclav
Date: March 1972
Abstract:
Let n, b, d be positive integers. D. Hanson proposed to evaluate
f(n,b,d), the largest possible number of edges in a graph with n
vertices having no vertex of degree greater than d and no set of more
than b independent edges. Using the alternating path method, he found
partial results in this direction. We complete Hanson's work; our proof
technique has a linear programming flavor and uses Berge's matching
formula.
CS-TR-72-268
Report Number: CS-TR-72-269
Institution: Stanford University, Department of Computer Science
Title: Arithmetic properties of certain recursively defined sets.
Author: Klarner, David A.
Author: Rado, Richard
Date: March 1972
Abstract:
Let R denote a set of linear operations defined on the set P of
positive integers; for example, a typical element of R has the form
$\rho (x_1, \ldots ,x_r) = m_0 + m_1 x_1 + \ldots + m_r x_r where m_0,
\ldots ,m_r$ denote certain integers. Given a set A of positive
integers, there is a smallest set of positive integers denoted which contains A as a subset and is closed under every operation in R. The set
can be constructed recursively as follows: Let $A_0$ = A, and define
$A_{k+1} = A_k \cup \{\rho (\bar{a}): \rho \in R,\bar{a}\in A_k \times
\ldots \times A_k\}$ (k = 0,1,\ldots ), then it can be shown that = $A_0 \cup A_1 \cup \ldots $. The sets
sometimes have an elegant form, for example, the set <2x + 3y: 1>
consists of all positive numbers congruent to 1 or 5 modulo 12. The
objective is to give an arithmetic characterization of elements of a
set , and this paper is a report on progress made on this problem
last year. Many of the questions left open here have since been
resolved by one of us (Klarner).
CS-TR-72-269
Report Number: CS-TR-72-270
Institution: Stanford University, Department of Computer Science
Title: The Lanczos algorithm for the symmetric Ax = $\lambda$Bx problem.
Author: Golub, Gene H.
Author: Underwood, Richard R.
Author: Wilkinson, James H.
Date: March 1972
Abstract:
The problem of computing the eigensystem of Ax = $\lambda$Bx when A and
B are symmetric and B is positive definite is considered. A
generalization of the Lanczos algorithm for reducing the problem to a
symmetric tridiagonal eigenproblem is given. A numerically stable
variant of the algorithm is described. The new algorithm depends
heavily upon the computation of elementary Hermitian matrices. An ALGOL
W procedure and a numerical example are also given.
CS-TR-72-270
Report Number: CS-TR-72-272
Institution: Stanford University, Department of Computer Science
Title: Fixpoint approach to the theory of computation.
Author: Manna, Z ohar
Author: Vuillemin, Jean
Date: March 1972
Abstract:
Following the fixpoint theory of Scott, we propose to define the
semantics of computer programs in terms of the least fixpoints of
recursive programs. This allows one not only to justify all existing
verification techniques, but also to extend them to handle various
properties of computer programs, including correctness, termination and
equivalence, in a uniform manner.
CS-TR-72-272
Report Number: CS-TR-72-273
Institution: Stanford University, Department of Computer Science
Title: Chromatic automorphisms of graphs.
Author: Chvatal, Vaclav
Author: Sichler, Jiri
Date: March 1972
Abstract:
The coloring group and the full automorphism group of an n-chromatic
graph are independent if and only if n is an integer $\geq$ 3.
CS-TR-72-273
Report Number: CS-TR-72-274
Institution: Stanford University, Department of Computer Science
Title: Linear combinations of sets of consecutive integers.
Author: Klarner, David A.
Author: Rado, Richard
Date: March 1972
Abstract:
Let k-1,$m_1, \ldots ,m_k$ denote non-negative integers, and suppose
the greatest common divisor of $m_1, \ldots ,m_k$ is 1. We show that if
$S_1, \ldots ,S_k$ are sufficiently long blocks of consecutive
integers, then the set $m_1 S_1 + \ldots\ m_k S_k$ contains a sizable
block of consecutive integers. For example, if m and n are relatively
prime natural numbers, and u, U, v, V are integers with U-u $\geq$ n-1,
V-v $geq$ m-1, then the set m{u,u+1, $\ldots$,U} + n{v,v+1, $\ldots$,V}
contains the set {mu + nv - $\sigma$(m,n), $\ldots$,mU + nV -
$\sigma$(m,n)} where $\sigma${m,n) = (m-1)(n-1) is the largest number
such that $\sigma$(m,n)-1 cannot be expressed in the form mx + ny with
x and y non-negative integers.
CS-TR-72-274
Report Number: CS-TR-72-275
Institution: Stanford University, Department of Computer Science
Title: Sets generated by iteration of a linear operation.
Author: Klarner, David A.
Date: March 1972
Abstract:
This note is a continuation of the paper "Arithmetic properties of
certain recursively defined sets," written in collaboration with
Richard Rado. Here the sets under consideration are those having the
form S = <$m_1 x_1 + \ldots\ + m_r x_r : 1$> where $m_1,\ldots
,m_r$ are given natural numbers with greatest common divisor 1. The set
S is the smallest set of natural numbers which contains 1 and is closed
under the operation $m_1 x_1 + \ldots\ + m_r x_r$. Also, S can be
constructed by iterating the operation $m_1 x_1 + \ldots\ + m_r X_r$
over the set {1}. For example, <2x + 3y: 1> = {1, 5, 13, 17, 25,
$\ldots\ } = (1 + 12N) $\cup$ (5 + 12N) where N = {0,1,2,$\ldots$}. It
is shown in this note that S contains an infinite arithmetic
progression for all natural numbers r-1,$m_1,\ldots ,m_r$. Furthermore,
if ($m_1,\ldots ,m_r$) = ($m_1\ldots m_r,m_1 + \ldots\ + m_r$) = 1,
then S is a per-set; that is, S is a finite union of infinite
arithmetic progressions. In particular, this implies
is a per-set for all pairs {m,n} of relatively prime natural numbers.
It is an open question whether S is a per-set when ($m_1,\ldots ,m_r$)
= 1, but ($m_1\ldots m_r,m_1 + \ldots\ + m_r$) > 1.
CS-TR-72-275
Report Number: CS-TR-72-278
Institution: Stanford University, Department of Computer Science
Title: Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations.
Author: Concus, Paul
Author: Golub, Gene H.
Date: April 1972
Abstract:
We study an iterative technique for the numerical solution of strongly
elliptic equations of divergence form in two dimensions with Dirichlet
boundary conditions on a rectangle. The technique is based on the
repeated solution by a fast direct method of a discrete Helmholtz
equation on a uniform rectangular mesh. The problem is suitably scaled
before iteration, and Chebyshev acceleration is applied to improve
convergence. We show that convergence can be exceedingly rapid and
independent of mesh size for smooth coefficients. Extensions to other
boundary conditions, other equations, and irregular mesh spacings are
discussed, and the performance of the technique is illustrated with
numerical examples.
CS-TR-72-278
Report Number: CS-TR-72-279
Institution: Stanford University, Department of Computer Science
Title: Topics in optimization.
Author: Osborne, Michael R.
Date: April 1972
Abstract:
These notes are based on a course of lectures given at Stanford, and
cover three major topics relevant to optimization theory. First an
introduction is given to those results in mathematical programming
which appear to be most important for the development and analysis of
practical algorithms. Next unconstrained optimization problems are
considered. The main emphasis is on that subclass of descent methods
which (a) requires the evaluation of first derivatives of the objective
function, and (b) has a family connection with the conjugate direction
methods. Numerical results obtained using a program based on this
material are discussed in an Appendix. In the third section, penalty
and barrier function methods for mathematical programming problems are
studied in some detail, and possible methods for accelerating their
convergence indicated.
CS-TR-72-279
Report Number: CS-TR-72-281
Institution: Stanford University, Department of Computer Science
Title: Computer interactive picture processing.
Author: Quam, Lynn H.
Author: Liebes, Sidney, Jr.
Author: Tucker, Robert B.
Author: Hannah, Marsha Jo
Author: Eross, Botond G.
Date: April 1972
Abstract:
This report describes work done in image processing using an
interactive computer system. Techniques for image differencing are
described and examples using images returned from Mars by the Mariner
Nine spacecraft are shown. Also described are techniques for stereo
image processing. Stereo processing for both conventional camera
systems and the Viking 1975 Lander camera system is reviewed.
CS-TR-72-281
Report Number: CS-TR-72-282
Institution: Stanford University, Department of Computer Science
Title: Efficient compilation of linear recursive programs.
Author: Chandra, Ashok K.
Date: April 1972
Abstract:
We consider the class of linear recursive programs. A linear recursive
program is a set of procedures where each procedure can make at most
one recursive call. The conventional stack implementation of recursion
requires time and space both proportional to n, the depth of recursion.
It is shown that in order to implement linear recursion so as to
execute in time n one doesn't need space proportional to n:
$n^\epsilon$ for arbitrarily small $\epsilon$ will do. It is also known
that with constant space one can implement linear recursion in time
$n^2$. We show that one can do much better: $n^{1+\epsilon}$ for
arbitrarily small $\epsilon$. We also describe an algorithm that lies
between these two: it takes time n.log(n) and space log(n). It is shown
that several problems are closely related to the linear recursion
problem, for example, the problem of reversing an input tape given a
finite automaton with several one-way heads. By casting all these
problems into a canonical form, efficient solutions are obtained
simultaneously for all.
CS-TR-72-282
Report Number: CS-TR-72-284
Institution: Stanford University, Department of Computer Science
Title: Edmonds polyhedra and a hierarchy of combinatorial problems.
Author: Chvatal, Vaclav
Date: May 1972
Abstract:
Let S be a set of linear inequalities that determine a bounded
polyhedron P. The closure of S is the smallest set of inequalities that
contains S and is closed under two operations: (i) taking linear
combinations of inequalities, (ii) replacing an inequality $\sum\ a_j
x_j \leq\ a_0$, where $a_1, a_2, ... , a_n$ are integers, by the
inequality $\sum\ a_j x_j \leq\ a$ with $a \geq\ [a_0]$. Obviously, if
integers $x_1, x_2, ... , x_n$ satisfy all the inequalities in S then
they satisfy also all the inequalities in the closure of S. Conversely,
let $\sum\ c_j x_j \leq\ c_0$ hold for all choices of integers $x_1,
x_2, ... , x_n$, that satisfy all the inequalities in S. Then we prove
that $\sum\ c_j x_j \leq\ c_0$ belongs to the closure of S. To each
integer linear programming problem, we assign a nonnegative integer,
called its rank. (The rank is the minimum number of iterations of the
operation (ii) that are required in order to eliminate the integrality
constraint.) We prove that there is no upper bound on the rank of
problems arising from the search for largest independent sets in graphs.
CS-TR-72-284
Report Number: CS-TR-72-286
Institution: Stanford University, Department of Computer Science
Title:
On the solution of Moser's problem in four dimensions, and related
issues. A collection of two papers: On the solution of Moser's problem
in four dimensions and Independent permutations as related to a problem
of Moser and a theorem of Polya.
Author: Chandra, Ashok K.
Date: May 1972
Abstract:
The problem of finding the largest set of nodes in a d-cube of side 3
such that no three nodes are collinear was proposed by Moser. Small
values of d (viz., $d \leq\ 3$) resulted in elegant symmetric
solutions. It is shown that this does not remain the case in 4
dimensions where at most 43 nodes can be chosen, and these must not
include the center node.
CS-TR-72-286
Report Number: CS-TR-72-288
Institution: Stanford University, Department of Computer Science
Title: Logic for Computable Functions: description of a machine implementation.
Author: Milner, Robin
Date: May 1972
Abstract:
This paper is primarily a user's manual for LCF, a proof-checking
program for a logic of computable functions proposed by Dana Scott in
1969 but unpublished by him. We use the name LCF also for the logic
itself, which is presented at the start of the paper. The
proof-checking program is designed to allow the user interactively to
generate formal proofs about computable functions and functionals over
a variety of domains, including those of interest to the computer
scientist - for example, integers, lists and computer programs and
their semantics. The user's task is alleviated by two features: a
subgoaling facility and a powerful simplification mechanism.
Applications include proofs of program correctness and in particular of
compiler correctness; these applications are not discussed herein, but
are illustrated in the papers referenced in this introduction.
CS-TR-72-288
Report Number: CS-TR-72-289
Institution: Stanford University, Department of Computer Science
Title: Lakoff on linguistics and natural logic.
Author: Wilks, Yorick A.
Date: June 1972
Abstract:
The paper examines and criticises Lakoff's notions of a natural logic
and of a generative semantics described in terms of logic. I argue that
the relationship of these notions to logic as normally understood is
unclear, but I suggest, in the course of the paper, a number of
possible interpretations of his thesis of generative semantics. I argue
further that on these interpretations the thesis (of Generative
Semantics) is false, unless it be taken as a mere notational variant of
Chomskyan theory. I argue, too, that Lakoff's work may provide a
service in that it constitutes a reductio ad absurdum of the
derivational paradigm of modern linguistics; and shows, inadvertently,
that only a system with the ability to reconsider its own inferences
can do the job that Lakoff sets up for linguistic enquiry -- that is to
say, only an "artificial intelligence" system.
CS-TR-72-289
Report Number: CS-TR-72-290
Institution: Stanford University, Department of Computer Science
Title: Adverbs and belief.
Author: Schank, Roger C.
Date: June 1972
Abstract:
The treatment of a certain class of adverbs in conceptual
representation is given. Certain adverbs are shown to be representative
of complex belief structures. These adverbs serve as pointers that
explain where the sentence that they modify belongs in a belief
structure.
CS-TR-72-290
Report Number: CS-TR-72-291
Institution: Stanford University, Department of Computer Science
Title: Some combinatorial lemmas.
Author: Knuth, Donald E.
Date: June 1972
Abstract:
This report consists of several short papers which are completely
independent of each other: 1. "Wheels Within Wheels." Every finite
strongly connected digraph is either a single point or a set of n
smaller strongly connected digraphs joined by an oriented cycle of
length n. This result is proved in somewhat stronger form, and two
applications are given. 2. "An Experiment in Optimal Sorting." An
unsuccessful attempt, to sort 13 or 14 elements in less comparisons
than the Ford-Johnson algorithm, is described. (Coauthor: E.B.
Kaehler.) 3. "Permutations With Nonnegative Partial Sums." A sequence
of s positive and t negative real numbers, whose sum is zero, can be
arranged in at least (s+t-1)! and at most (s+t)!/(max(s,t)+1) <
2(s+t-1)! ways such that the partial sums $x_1 + ... + x_j$ are
nonnegative for $1 \leq\ j \leq\ s+t$.
CS-TR-72-291
Report Number: CS-TR-72-292
Institution: Stanford University, Department of Computer Science
Title: Selected combinatorial research problems.
Author: Chvatal, Vaclav
Author: Klarner, David A.
Author: Knuth, Donald E.
Date: June 1972
Abstract:
Thirty-seven research problems are described, covering a wide range of
combinatorial topics. Unlike Hilbert's problems, most of these are not
especially famous and they might be "do-able" in the next few years.
(Problems 1-16 were contributed by Klarner, 17-26 by Chvatal, 27-37 by
Knuth. All cash awards are Chvatal's responsibility.)
CS-TR-72-292
Report Number: CS-TR-72-299
Institution: Stanford University, Department of Computer Science
Title: semantic categories of nominals for conceptual dependency analysis of natural language.
Author: Russell, Sylvia Weber
Date: July 1972
Abstract:
A system for the semantic categorization of conceptual objects
(nominals) is provided. The system is intended to aid computer
understanding of natural language. Specific implementations for
"noun-pairs" and prepositional phrases are offered.
CS-TR-72-299
Report Number: CS-TR-72-300
Institution: Stanford University, Department of Computer Science
Title: Counterexample to a conjecture of Fujii, Kasami and Ninomiya.
Author: Kaufman, Marc T.
Date: June 1972
Abstract:
In a recent paper [1], Fujii, Kasami and Ninomiya presented a procedure
for the optimal scheduling of a system of unit length tasks represented
as a directed acyclic graph on two identical processors. The authors
conjecture that the algorithm can be extended to the case where more
than two processors are employed. This note presents a counterexample
to that conjecture. [1] Fujii, M., T. Kasami and K. Ninomiya, "Optimal
Sequencing of Two Equivalent Processors, SIAM J. Appl. Math., Vol. 17,
No.4, July 1969, pp. 784-789.
CS-TR-72-300
Report Number: CS-TR-72-301
Institution: Stanford University, Department of Computer Science
Title: Product form of the Cholesky factorization for large-scale linear programming.
Author: Saunders, Michael A.
Date: August 1972
Abstract:
A variation of Gill and Murray's version of the revised simplex
algorithm is proposed, using the Cholesky factorization ${BB}^T =
{LDL}^T$ where B is the usual basis, D is diagonal and L is unit lower
triangular. It is shown that during change of basis L may be updated in
product form. As with standard methods using the product form of
inverse, this allows use of sequential storage devices for accumulating
updates to L. In addition the favorable numerical properties of Gill
and Murray's algorithm are retained. Cloase attention is given to
efficient out-of-core implementation. In the case of large-scale
block-angular problems, the updates to L will remain very sparse for
all iterations.
CS-TR-72-301
Report Number: CS-TR-72-304
Institution: Stanford University, Department of Computer Science
Title: Richardson's non-stationary matrix iterative procedure.
Author: Anderssen, Robert S.
Author: Golub, Gene H.
Date: August 1972
Abstract:
Because of its simplicity, Richardson's non-stationary iterative scheme
is a potentially powerful method for the solution of (linear) operator
equations. However, its general application has more or less been
blocked by (a) the problem of constructing polynomials, which deviate
least from zero on the spectrum of the given operator, and which are
required for the determination of the iteration parameters of the
non-stationary method, and (b) the instability of this scheme with
respect to rounding error effects. Recently, these difficulties were
examined in two Russian papers. In the first, Lebedev [1969]
constructed polynomials which deviate least from zero on a set of
subintervals of the real axis which contains the spectrum of the given
operator. In the second, Lebedev and Finogenov [1971] gave an ordering
for the iteration parameters of the non-stationary Richardson scheme
which makes it a stable numerical process. Translation of these two
papers appear as Appendices 1 and 2, respectively, in this report. The
body of the report represents an examination of the properties of
Richardson's non-stationary scheme and the pertinence of the two
mentioned papers along with the results of numerical experimentation
testing the actual implementation of the procedures given in them.
CS-TR-72-304
Report Number: CS-TR-72-306
Institution: Stanford University, Department of Computer Science
Title: A bibliography on computer graphics.
Author: Pollack, Bary W.
Date: August 1972
Abstract:
This bibliography includes the most important works describing the
softwre aspects of generative computer graphics. As such it will be of
most usefullness to researchers, system designers and programmers whose
interests and responsibilities include the development of software
systems for interactive graphical input/output. The bibliography does
include a short section on hardware systems. Image analysis, pattern
recognition and picture processing and related fields are rather poorly
represented here. The interested researcher is referred to journals in
this field and to the reports of Azriel Rosenfeld, University of
Maryland, which include excellent bibliographic references.
CS-TR-72-306
Report Number: CS-TR-72-307
Institution: Stanford University, Department of Computer Science
Title: Hadamard transform for speech wave analysis.
Author: Tanaka, Hozumi
Date: August 1972
Abstract:
Two methods of speech wave analysis using the Hadamard transform are
discussed. The first method is a direct application of the Hadamard
transform for speech waves. The reason this method yields poor results
is discussed. The second method is the application of the Hadamard
transform to a log-magnitude frequency spectrum. After the application
of the Fourier transform the Hadamard transform is applied to detect a
pitch period or to get a smoothed spectrum. This method shows some
positive aspects of the Hadamard transform for the analysis of a speech
wave with regard to the reduction of processing time required for
smoothing, but at the cost of precision. A formant tracking program for
voiced speech is implemented by using this method and an edge following
technique used in scene analysis.
CS-TR-72-307
Report Number: CS-TR-72-308
Institution: Stanford University, Department of Computer Science
Title: Recent developments in SAIL, an algol-based language for artificial intelligence.
Author: Feldman, Jerome A.
Author: Low, James R.
Author: Swinehart, Daniel C.
Author: Taylor, Russell H.
Date: November 1972
Abstract:
New features added to SAIL, an ALGOL based language for the PDP-10, are
discussed. The features include: procedure variables; multiple
processes; coroutines; a limited form of backtracking; an event
mechanism for inter-process communication; and matching procedures, a
new way of searching the LEAP associative data base.
CS-TR-72-308
Report Number: CS-TR-72-310
Institution: Stanford University, Department of Computer Science
Title: Anomalies in scheduling unit-time tasks.
Author: Kaufman, Marc T.
Date: June 1972
Abstract:
In this paper we examine the problem of scheduling a set of tasks on a
system with a number of identical processors. Several timing anomalies
are known to exist for the general case, in which the execution time
can increase when inter-task constraints are removed or processors are
added. It is shown that these anomalies also exist when tasks are
restricted to be of equal (unit) length. Several, increasingly
restrictive, heuristic scheduling algorithms are reviewed. The "added
processor" anomaly is shown to persist through all of them, though in
successively weaker form.
CS-TR-72-310
Report Number: CS-TR-72-317
Institution: Stanford University, Department of Computer Science
Title: An analysis of drum storage units.
Author: Fuller, Samuel H.
Author: Baskett, Forest
Date: August 1972
Abstract:
This article discusses the modeling and analysis of drum-like storage
units. Two common forms of drum organizations and two common scheduling
disciplines are considered: the file drum and the paging drum;
first-in-first-out (FIFO) scheduling and shortest-latency-time-first
(SLTF) scheduling. The modeling of the I/O requests to the drum is an
important aspect of this analysis. Measurements are presented to
indicate that it is realistic to model requests for records, or blocks
of information to a file drum, as requests that have starting addresses
uniformly distributed around the circumference of the drum and transfer
times that are exponentially distributed with a mean of 1/2 to 1/3 of a
drum revolution. The arrival of I/O requests is first assumed to be a
Poisson process and then generalized to the case of a computer system
with a finite degree of multiprogramming. An exact analysis of all the
models except the SLTF file drum is presented; in this case the
complexity of the drum organization has forced us to accept an
approximate analysis. In order to examine the error introduced into the
analysis of the SLTF file drum by our approximations, the results of
the analytic models are compared to a simulation model of the SLTF file
drum.
CS-TR-72-317
Report Number: CS-TR-72-318
Institution: Stanford University, Department of Computer Science
Title: Constructive graph labeling using double cosets.
Author: Brown, Harold
Author: Masinter, Larry M.
Author: Hjelmeland, Larry
Date: October 1972
Abstract:
Two efficient computer implemented algorithms are presented for
explicitly constructing all distinct labelings of a graph G with a set
of (not necessarily distinct) labels L, given the symmetry group B of
G. Two recursive reductions of the problem and a precomputation
involving certain orbits of stabilizer subgroups are the techniques
used by the algorithm. Moreover, for each labeling, the subgroup of B
which preserves that labeling is calculated.
CS-TR-72-318
Report Number: CS-TR-72-319
Institution: Stanford University, Department of Computer Science
Title: On a characterization of the best $\ell_2$ scaling of a matrix.
Author: Golub, Gene H.
Author: Varah, James M.
Date: October 1972
Abstract:
This paper is concerned with best two-sided scaling of a general square
matrix, and in particular with a certain characterization of that best
scaling: namely that the first and last singular vectors (on left and
right) of the scaled matrix have components of equal modulus.
Necessity, sufficiency, and its relation with other characterizations
are discussed. Then the problem of best scaling for rectangular
matrices is introducted and a conjecture made regarding a possible best
scaling. The conjecture is verified for some special cases.
CS-TR-72-319
Report Number: CS-TR-72-320
Institution: Stanford University, Department of Computer Science
Title: Winged edge polyhedron representation.
Author: Baumgart, Bruce G.
Date: October 1972
Abstract:
A winged edge polyhedron representation is stated and a set of
primitives that preserve Euler's F-E+V = 2 equation are explained.
Present use of this representation in artificial intelligence for
computer graphics and world modeling is illustrated and its intended
future application to computer vision is described.
CS-TR-72-320
Report Number: CS-TR-72-322
Institution: Stanford University, Department of Computer Science
Title: Methods for modifying matrix factorizations.
Author: Gill, Phillip E.
Author: Golub, Gene H.
Author: Murray, Walter A.
Author: Saunders, Michael A.
Date: November 1972
Abstract:
In recent years several algorithms have appeared for modifying the
factors of a matrix following a rank-one change. These methods have
always been given in the context of specific applications and this has
probably inhibited their use over a wider field. In this report several
methods are described for modifying Cholesky factors. Some of these
have been published previously while others appear for the first time.
In addition, a new algorithm is presented for modifying the complete
orthogonal factorization of a general matrix, from which the
conventional QR factors are obtained as a special case. A uniform
notation has been used and emphasis has been placed on illustrating the
similarity between different methods.
CS-TR-72-322
Report Number: CS-TR-72-323
Institution: Stanford University, Department of Computer Science
Title: A fast method for solving a class of tri-diagonal linear systems.
Author: Malcolm, Michael A.
Author: Palmer, John
Date: November 1972
Abstract:
The solution of linear systems having real, symmetric, diagonally
dominant, tridiagonal coefficient matrices with constant diagonals is
considered. It is proved that the diagonals of the LU decomposition of
the coefficient matrix rapidly converge to full floating-point
precision. It is also proved that the computed LU decomposition
converges when floating-point arithmetic is used and that the limits of
the LU diagonals using floating point are roughly within machine
precision of the limits using real arithmetic. This fact is exploited
to reduce the number of floating-point operations required to solve a
linear system from 8n-7 to 5n+2k-3, where k is much less than n, the
order of the matrix. If the elements of the sub- and superdiagonals are
1, then only 4n+2k-3 operations are needed. The entire LU decomposition
takes k words of storage, and considerable savings in array
subscripting are achieved. Upper and lower bounds on k are obtained in
terms of the ratio of the coefficient matrix diagonal constants and
parameters of the floating-point number system. Various generalizations
of these results are discussed.
CS-TR-72-323
Report Number: CS-TR-72-325
Institution: Stanford University, Department of Computer Science
Title:
Review of Hubert Dreyfus' What Computers Can't Do: a Critique of
Artificial Reason (Harper & Row, New York, 1972).
Author: Buchanan, Bruce G.
Date: November 1972
Abstract:
The recent book $\underline{What Computers Can't Do}$ by Hubert Dreyfus
is an attack on artificial intelligence research. This review takes the
position that the philosophical content of the book is interesting, but
that the attack on artificial intelligence is not well reasoned.
CS-TR-72-325
Report Number: CS-TR-72-326
Institution: Stanford University, Department of Computer Science
Title:
Can expert judges, using transcripts of teletyped psychiatric
interviews, distinguish human paranoid patients from a computer
simulation of paranoid processes?
Author: Colby, Kenneth Mark
Author: Hilf, Franklin Dennis
Date: December 1972
Abstract:
Expert judges (psychiatrists and computer scientists) could not
correctly distinguish a simulation model of paranoid processes from
actual paranoid patients.
CS-TR-72-326
Report Number: CS-TR-72-328
Institution: Stanford University, Department of Computer Science
Title: An efficient implementation of Edmonds' maximum matching algorithm.
Author: Gabow, Harold N.
Date: June 1972
Abstract:
A matching in a graph is a collection of edges, no two of which share a
vertex. A maximum matching contains the greatest number of edges
possible. This paper presents an efficient implementation of Edmonds'
algorithm for finding maximum matchings. The computation time is
proportional to $V^3$, where V is the number of vertices; previous
algorithms have computation time proportional to $V^4$. The
implementation avoids Edmonds' blossom reduction by using pointers to
encode the structure of alternating paths.
CS-TR-72-328
Report Number: CS-TR-73-330
Institution: Stanford University, Department of Computer Science
Title: Axioms and theorems for integers, lists and finite sets in LCF.
Author: Newey, Malcolm C.
Date: January 1973
Abstract:
LCF (Logic for Computable Functions) is being promoted as a formal
language suitable for the discussion of various problems in the
Mathematical Theory of Computation (MTC). To this end, several examples
of MTC problems have been formalised and proofs have been exhibited
using the LCF proof-checker. However, in these examples, there has been
a certain amount of ad-hoc-ery in the proofs; namely, many mathematical
theorems have been assumed without proof and no axiomatisation of the
mathematical domains involved was given. This paper describes a
suitable mathematical environment for future LCF experiments and its
axiomatic basis. The environment developed, deemed appropriate for such
experiments, consists of a large body of theorems from the areas of
integer arithmetic, list manipulation and finite set theory.
CS-TR-73-330
Report Number: CS-TR-73-331
Institution: Stanford University, Department of Computer Science
Title: The computing time of the Euclidean algorithm.
Author: Collins, George E.
Date: January 1973
Abstract:
The maximum, minimum and average computing times of the classical
Euclidean algorithm for the greatest common divisor of two integers are
derived, to within codominance, as functions of the lengths of the two
inputs and the output.
CS-TR-73-331
Report Number: CS-TR-73-332
Institution: Stanford University, Department of Computer Science
Title: Models of LCF.
Author: Milner, Robin
Date: January 1973
Abstract:
LCF is a deductive system for computable functions proposed by D. Scott
in 1969 in an unpublished memorandum. The purpose of the present paper
is to demonstrate the soundness of the system with respect to certain
models, which are partially ordered domains of continuous functions.
This demonstration was supplied by Scott in his memorandum; the present
paper is merely intended to make this work more accessible.
CS-TR-73-332
Report Number: CS-TR-73-333
Institution: Stanford University, Department of Computer Science
Title: On the power of programming features.
Author: Chandra, Ashok K.
Author: Manna, Z ohar
Date: January 1973
Abstract:
We consider the power of several programming features such as counters,
pushdown stacks, queues, arrays, recursion and equality. In this study
program schemas are used as the model for computation. The relations
between the powers of these features is completely described by a
comparison diagram.
CS-TR-73-333
Report Number: CS-TR-73-334
Institution: Stanford University, Department of Computer Science
Title: URAND: a universal random number generator.
Author: Malcolm, Michael A.
Author: Moler, Cleve B.
Date: January 1973
Abstract:
A subroutine for generating uniformly-distributed floating-point
numbers in the interval [O,1) is presented in ANSI standard Fortran.
The subroutine, URAND, is designed to be relatively machine
independent. URAND has undergone minimal testing on various machines
and is thought to work properly on any machine having binary integer
number representation, integer multiplication modulo m and integer
addition either modulo m or yielding at least ${log}_2$ (m) significant
bits, where m is some integral power of 2. Upon the first call of
URAND, the value of m is automatically determined and appropriate
constants for a linear congruential generator are computed following
the suggestions of D. E. Knuth, volume 2. URAND is guaranteed to have a
full-length cycle. Readers are invited to apply their favorite
statistical tests to URAND, using any binary machine, and report the
results to the authors.
CS-TR-73-334
Report Number: CS-TR-73-335
Institution: Stanford University, Department of Computer Science
Title: Computation of the stationary distribution of an infinite Markov matrix.
Author: Golub, Gene H.
Author: Seneta, Eugene
Date: January 1973
Abstract:
An algorithm is presented for computing the unique stationary
distribution of an infinite stochastic matrix possessing at least one
column whose elements are bounded away from zero. Elementwise
convergence rate is discussed by means of two examples.
CS-TR-73-335
Report Number: CS-TR-73-337
Institution: Stanford University, Department of Computer Science
Title: Aesthetics systems.
Author: Gips, James
Author: Stiny, George
Date: January 1973
Abstract:
The formal structure of aesthetics systems is defined. Aesthetics
systems provide for the essential tasks of interpretation and
evaluation in aesthetic analysis. Kolmogorov's formulation of
information theory is applicable. An aesthetics system for a class of
non-representational, geometric paintings and its application to three
actual paintings is described in the Appendix.
CS-TR-73-337
Report Number: CS-TR-73-338
Institution: Stanford University, Department of Computer Science
Title: A finite basis theorem revisited.
Author: Klarner, David A.
Date: February 1973
Abstract:
Let S denote a set of k-dimensional boxes each having integral sides.
Let $\Gamma$(S) denote the set of all boxes which can be filled
completely with translates of elements of S. It is shown here that S
contains a finite subset B such that $\Gamma$(B) = $\Gamma$(S). This
result was proved for k = 1,2 in an earlier paper, but the proof for k
> 2 contained an error.
CS-TR-73-338
Report Number: CS-TR-73-339
Institution: Stanford University, Department of Computer Science
Title: Computation of the limited information maximum likelihood estimator.
Author: Dent, Warren T.
Author: Golub, Gene H.
Date: February 1973
Abstract:
Computation of the Limited Information Maximum Likelihood Estimator
(LIMLE) of the set of coefficients in a single equation of a system of
interdependent relations is sufficiently complicated to detract from
other potentially interesting properties. Although for finite samples
the LIMLE has no moments, asymptotically it remains normally
distributed and retains other properties associated with maximum
likelihood. The most extensive application of the estimator has been
made in the Brookings studies. We believe that current methods of
estimation are clumsy, and present a numerically stable estimation
schema based on Householder transformations and the singular value
decomposition. The analysis permits a convenient demonstration of
equivalence with the Two Stage Least Squares Estimator (TSLSE) in the
instance of just identification.
CS-TR-73-339
Report Number: CS-TR-73-340
Institution: Stanford University, Department of Computer Science
Title: Notes on a problem involving permutations as subsequences.
Author: Newey, Malcolm C.
Date: March 1973
Abstract:
The problem (attributed to R. M. Karp by Knuth) is to describe the
sequences of minimum length which contain, as subsequences, all the
permutations of an alphabet of n symbols. This paper catalogs some of
the easy observations on the problem and proves that the minimum
lengths for n=5, n=6 & n=7 are 19, 28 and 39 respectively. Also
presented is a construction which yields (for n>2) many appropriate
sequences of length $n^2$-2n+4 so giving an upper bound on length of
minimum strings which matches exactly all known values.
CS-TR-73-340
Report Number: CS-TR-73-341
Institution: Stanford University, Department of Computer Science
Title: A heuristic approach to program verification.
Author: Katz, Shmuel M.
Author: Manna, Z ohar
Date: March 1973
Abstract:
We present various heuristic techniques for use in proving the
correctness of computer programs. The techniques are designed to obtain
automatically the "inductive assertions" attached to the loops of the
program which previously required human "understanding" of the
program's performance. We distinguish between two general approaches:
one in which we obtain the inductive assertion by analyzing predicates
which are known to be true at the entrances and exits of the loop
($underline{top-down}$ approach), and another in which we generate the
inductive assertion directly from the statements of the loop
($underline{bottom-up}$ approach).
CS-TR-73-341
Report Number: CS-TR-73-342
Institution: Stanford University, Department of Computer Science
Title: Matroid partitioning.
Author: Knuth, Donald E.
Date: March 1973
Abstract:
This report discusses a modified version of Edmonds's algorithm for
partitioning of a set into subsets independent in various given
matroids. If ${\cal M}_1$,...,${\cal M}_k$ are matroids defined on a
finite set E, the algorithm yields a simple necessary and sufficient
condition for whether or not the elements of E can be colored with k
colors such that (i) all elements of color j are independent in ${\cal
M}_j$, and (ii) the number of elements of color j lies between given
limits, $n_j \leq \| E_j \| \leq {n'}_j$. The algorithm either finds
such a coloring or it finds a proof that none exists, after making at
most $n^3$ + $n^2$k tests of independence in the given matroids, where
n is the number of elements in E.
CS-TR-73-342
Report Number: CS-TR-73-344
Institution: Stanford University, Department of Computer Science
Title: The fourteen primitive actions and their inferences.
Author: Schank, Roger C.
Date: March 1973
Abstract:
In order to represent the conceptual information underlying a natural
language sentence, a conceptual structure has been established that
uses the basic actor-action-object framework. It was the intent that
these structures have only one representation for one meaning,
regardless of the semantic form of the sentence being represented.
Actions were reduced to their basic parts so as to effect this. It was
found that only fourteen basic actions were needed as building blocks
by which all verbs can be represented. Each of these actions has a set
of actions or states which can be inferred when they are present.
CS-TR-73-344
Report Number: CS-TR-73-345
Institution: Stanford University, Department of Computer Science
Title: The minimum root separation of a polynomial.
Author: Collins, George E.
Author: Horowitz, Ellis
Date: April 1973
Abstract:
The minimum root separation of a complex polynomial A is defined as the
minimum of the distances between distinct roots of A. For polynomials
with Gaussian integer coefficients and no multiple roots, three lower
bounds are derived for the root separation. In each case the bound is a
function of the degree, n, of A and the sum, d, of the absolute values
of the coefficients of A. The notion of a semi-norm for a commutative
ring is defined, and it is shown how any semi-norm can be extended to
polynomial rings and matrix rings, obtaining a very general analogue of
Hadamard's determinant theorem.
CS-TR-73-345
Report Number: CS-TR-73-347
Institution: Stanford University, Department of Computer Science
Title: Multidimensional analysis in evaluating a simulation of paranoid thought.
Author: Colby, Kenneth Mark
Author: Hilf, Franklin Dennis
Date: May 1973
Abstract:
The limitations of Turing's Test as an evaluation procedure are
reviewed. More valuable are tests which ask expert judges to make
ratings along multiple dimensions essential to the model. In this way
the model's weaknesses become clarified and the model builder learns
where the model must be improved.
CS-TR-73-347
Report Number: CS-TR-73-346
Institution: Stanford University, Department of Computer Science
Title: The rationale for computer based treatment of language difficulties in nonspeaking autistic children.
Author: Colby, Kenneth Mark
Date: March 1973
Abstract:
The principles underlying a computer-based treatment method for
language acquisition in nonspeaking autistic children are described.
The main principle involves encouragement of exploratory learning with
minimum adult interference.
CS-TR-73-346
Report Number: CS-TR-73-348
Institution: Stanford University, Department of Computer Science
Title: High order finite difference solution of differential equations.
Author: Pereyra, Victor
Date: April 1973
Abstract:
These seminar notes give a detailed treatment of finite difference
approximations to smooth nonlinear two-point boundary value problems
for second order differential equations. Consistency, stability,
convergence, and asymptotic expansions are discussed. Most results are
stated in such a way as to indicate extensions to more general
problems. Successive extrapolations and deferred corrections are
described and their implementations are explored thoroughly. A very
general deferred correction generator is developed and it is employed
in the implementation of a variable order, variable (uniform) step
method. Complete FORTRAN programs and extensive numerical experiments
and comparisons are included together with a set of 48 references.
CS-TR-73-348
Report Number: CS-TR-73-349
Institution: Stanford University, Department of Computer Science
Title:
Two papers on the selection problem: Time Bounds for Selection [by
Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and
Robert E. Tarjan] and Expected Time Bounds for Selection [by Robert W.
Floyd and Ronald L. Rivest].
Author: Blum, Manual
Author: Floyd, Robert W.
Author: Pratt, Vaughan R.
Author: Rivest, Ronald L.
Author: Tarjan, Robert Endre
Date: April 1973
Abstract:
(1) The number of comparisons required to select the i-th smallest of n
numbers is shown to be at most a linear function of n by analysis of a
new selection algorithm -- PICK. Specifically, no more than 5.4305 n
comparisons are ever required. This bound is im