September 1973 - Vol. 16 No. 9
Features
Computational algorithms for closed queueing networks with exponential servers
Methods are presented for computing the equilibrium distribution of customers in closed queueing networks with exponential servers. Expressions for various marginal distributions are also derived. The computational algorithms are based on two-dimensional iterative techniques which are highly efficient and quite simple to implement. Implementation considerations such as storage allocation strategies and order of evaluation are examined in some detail.
Information theory applied to the conversion of decision tables to computer programs
Using ideas from information theory, this paper develops a heuristic algorithm that converts a limited entry decision table to a tree structured computer program with near minimum average processing time. The method is applicable to any limited entry decision table and does not require that actions have single rules or that the cost of testing conditions be equal. It is thus more general than the previously published heuristic algorithms. Compared to the optimal algorithm of Reinwald and Soland, this algorithm is easy to code and takes a much smaller translation time; it is thus felt that it is more useful in practice. The algorithm is well suited for manual conversion of decision tables to flowcharts.
Evaluation and selection of file organization—a model and system
This work first discusses the factors that affect file (data base) organization performance, an elusive subject, and then presents a methodology, a model and a programmed system to estimate primarily total storage costs and average access time of several file organizations, given a specific data base, query characterization and device-related specifications. Based on these estimates, an appropriate file structure may be selected for the specific situation. The system is a convenient tool to study file structures and to facilitate as much as possible the process of data base structure design and evaluation.
Design of tree structures for efficient querying
A standard information retrieval operation is to determine which records in a data collection satisfy a given query expressed in terms of data values. The process of locating the desired responses can be represented by a tree search model. This paper poses an optimization problem in the design of such trees to serve a well-specified application. The problem is academic in the sense that ordinarily the optimal tree cannot be implemented by means of practical techniques. On the other hand, it is potentially useful for the comparison it affords between observed performance and that of an intuitively attractive ideal search procedure.
As a practical application of such a model this paper considers the design of a novel tree search scheme based on a bit vector representation of data and shows that essentially the same algorithm can be used to design either an ideal search tree or a bit-vector tree. An experimental study of a small formatted file illustrates the concepts.
Empirical working set behavior
The working set model for program behavior has been proposed in recent years as a basis for the design of scheduling and paging algorithms. Although the words “working set” are now commonly encountered in the literature dealing with resource allocation, there is a dearth of published data on program working set behavior. It is the purpose of this paper to present empirical data from actual program measurements, in the hope that workers in the field might find experimental evidence upon which to substantiate and base theoretical work.
A simple technique for structured variable lookup
A simple technique for the symbol-table lookup of structured variables based on simple automata theory is presented. The technique offers a deterministic solution to a problem which is currently handled in a nondeterministic manner in PL/I and COBOL compilers.
The ability to backtrack, or retrace, the execution of a computer program has gained wider acceptance recently as a desired feature within a programming language. This is particularly useful in two different applications: (1) In debugging systems where the trace output is saved and can be interrogated under programmer control [1, 3]; (2) In artificial intelligence applications where one is trying to prove a certain result. It is frequently necessary to backup the proof and try some alternative path [2].
Sard kernels for certain bivariate cubatures
An error analysis for some bivariate cubatures is given. The remainders are obtained by the use of Sard kernels. Numerical results and computer graphs are given for some of the kernel functions.