Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 13 Issue 3, July 1966

Time-Shared Computer Operations With Both Interarrival and Service Times Exponential
B. Krishnamoorthi, Roger C. Wood
Pages: 317-338
DOI: 10.1145/321341.321342
The concept of time-shared computer operations is briefly described and a model of a time-sharing system is proposed, based on the assumption that both interarrival and service times possess an exponential distribution. Although the process...

Conversion of Limited-Entry Decision Tables to Optimal Computer Programs I: Minimum Average Processing Time
Lewis T. Reinwald, Richard M. Soland
Pages: 339-358
DOI: 10.1145/321341.321343
This paper begins with a brief description of desicion tables, and then presents a discussion of alternative expressions for them as sequential testing procedures for computer implementation and as Boolean functions. An algorithm is developed...

Monogenic Post Normal Systems of Arbitrary Degree
Philip K. Hooper
Pages: 359-363
DOI: 10.1145/321341.321344
From an arbitrary Turing machine, Z, a monogenic Post normal system, v(Z), is constructed. It is then shown not only that the halting problem for Z is reducible to that of...

Preservation of unambiguity and inherent ambiguity in context-free languages
Seymour Ginsburg, Joseph Ullian
Pages: 364-368
DOI: 10.1145/321341.321345
Various elementary operations are studied to find whether they preserve on ambiguity and inherent ambiguity of language (“language” means “context-free language”) The following results are established: ...

Use of Multiwrite for General Programmability of Search Memories
Sigmund N. Porter
Pages: 369-373
DOI: 10.1145/321341.321346
Multiwrite (selective writing in words which satisfied a previous search) is shown to permit parallel evaluation of any Boolean function (including arithmetic) in a search memory. A general method is given which expresses the Boolean function as...

Predictor-Corrector Methods of High Order With Improved Stability Characteristics
Fred T. Krogh
Pages: 374-385
DOI: 10.1145/321341.321347
Some new predictors are presented for use with the Adams-Moulton correctors of orders 4 through 8. The resulting algorithms have better stability characteristics than the usual ones which employ the Adams Bashforth predictors and at the same...

Automatic Controlled Precision Calculations
Bruce A. Chartres
Pages: 386-403
DOI: 10.1145/321341.321348
Recent developments in computer design and error analysis have made feasible the use of variable precision arithmetic and the preparation of programs that automatically determine their own precision requirements. Such programs enable the user to...

Internal Sorting by Radix Plus Sifting
M. Donald MacLaren
Pages: 404-411
DOI: 10.1145/321341.321349
A method is proposed for internal sorting which has the property that the expected time required per record, to sort n records with random keys, is a bounded function of n. Moreover the storage required in...

Generalized Single-Ended Counters
John S. Bailey
Pages: 412-418
DOI: 10.1145/321341.321350
Conventional shift counters are shown to be a special case of the general class of counters that use single-ended information on all but one bit position of JK flip-flops. The resultant class of counters preserves the...

Numerical Inversion of Laplace Transforms Using Laguerre Functions
William T. Weeks
Pages: 419-429
DOI: 10.1145/321341.321351
A method is described for the numerical inversion of Laplace transforms, in which the inverse is obtained as an expansion in terms of orthonormal Laguerre functions. In order for this to be accomplished, the given Laplace transform is expanded...

A Class of Integration Formulas
R. W. Hamming, R. S. Pinkham
Pages: 430-438
DOI: 10.1145/321341.321352
Gregory's formula for numerically integrating a function is one of the most promising formulas for use in a computer library. This paper shows how Gregory's formula can be generalized, and examines special cases which have a number of very...

On the ``Reverse Order Law'' Related to the Generalized Inverse of Matrix Products
Ivan Erdelyi
Pages: 439-443
DOI: 10.1145/321341.321353
The “reverse order law” related to ordinary inverses of matrix products, i.e., (AB)-1 = B-1A-1, is generally not...

An Abstract Machine for Symbolic Computation
D. L. Overheu
Pages: 444-468
DOI: 10.1145/321341.321354
The design of an abstract machine with a recursive function programming language which avoids the predicate type of conditional is described. It is shown that trough the adoption of list processing techniques it has been possible to construct a...

Corrigenda: "Statistical Complexity of Algorithms for Boolean Function Minimization"
Franco Mileto, Gianfranco Putzolu
Page: 469
DOI: 10.1145/321341.321355