April 1969 - Vol. 12 No. 4
Features
Editorial: on the ACM publications
It is proper that a professional organization periodically review its publication policy to ensure that it is fully meeting its responsibilities to its members To this purpose the President of ACM has asked the Editorial Board to formulate a five-year policy for recommendation to the Council and an ad hoc commitee of the Editorial Board is examining the question.
Professor Gotlieb, through his distinguished editorial service over the past years as Editor-as-Chief of the Journal and also of Communications, has helped shape the development of ACM publications, and we are pleased to present his views in this invited editorial —M. Stuart Lynn, Editor-in-Chief
Analysis of boolean program models for time-shared, paged environments
Directed graphs or their associated matrices are frequently used to represent the logical structure of sequences of computer instructions. Such techniques are used and, in addition, data references are represented in a nondirected model. The complete structural specification of a program is represented by a combined model. A transformation of the combined model yields a new model in which additional timing information is also contained. Analysis of these models prior to execution yields information valuable in determining segmentation of instructions and data for a time-shared environment, as well as for initial page loading; during execution, the analysis may be used for “look ahead” control of page turning.
An algorithm for hidden line elimination
The algorithm presented causes the elimination of hidden lines in the representation of a perspective view of concave and convex plane-faced objects on the picture plane. All the edges of the objects are considered sequentially, and all planes which hide every point of an edge are found.
The computing time increases roughly as the square of the number of edges. The algorithm takes advantage of a reduced number of concave points and automatically recognizes if only one object with no concave points is considered. In this last case, the result is obtained in a much simpler way.
Simulation of outpatient appointment systems
An experimental computer program is described which simulates appointment systems employed by outpatient departments of hospitals. Both major kinds of appointment systems—individual and block—can be simulated. The purpose of the Simulator is to enable the user to evaluate the effectiveness of alternative appointment systems in a given clinical environment.
On coordination reduction and sentence analysis
A class of coordination phenomena in natural languages is considered within the framework of transformational theory. To account for these phenomena it is proposed that certain machinery be added to the syntactic component of a transformational grammar. This machinery includes certain rule schemata, the conditions under which they are to be applied, and conditions determining the sequence of subtrees on which they are to be performed. A solution to the syntactic analysis problem for this class of grammars is outlined. Precise specification of both the generative procedure of this paper and its inverse is given in the form of LISP function definitions.
An algorithm for solving a special class of tridiagonal systems of linear equations
An algorithm is presented for solving a system of linear equations Bu = k where B is tridiagonal and of a special form. This form arises when discretizing the equation - d/dx (p(x) du/dx) = k(x) (with appropriate boundary conditions) using central differences. It is shown that this algorithm is almost twice as fast as the Gaussian elimination method usually suggested for solving such systems. In addition, explicit formulas for the inverse and determinant of the matrix B are given.
Computation of Jn(x) by numerical integration
It is shown to be practical to compute Jn(x) by numerical integration of its integral representation using the trapezoidal rule. The error in this approximation was studied empirically.
