Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 14 Issue 2, April 1967

A Survey of Microcellular Research
Robert C. Minnick
Pages: 203-241
DOI: 10.1145/321386.321387
This paper is a survey of research on microcellular techniques. Of particular interest are those techniques that are appropriate for realization by modern batch-fabrication processes, since the rapid emergence of reliable and economical...

Time-shared Systems: a theoretical treatment
Leonard Kleinrock
Pages: 242-261
DOI: 10.1145/321386.321388
Time-shared computer (or processing) facilities are treated as stochastic queueing systems under priority service disciplines, and the performance measure of these systems is taken to be the average time spent in the system. Models are analyzed...

Some Mathematical Considerations of Time-Sharing Scheduling Algorithms
Jack E. Shemer
Pages: 262-272
DOI: 10.1145/321386.321389
A mathematical derivation of expected response time is presented for selected cyclic and priority scheduling disciplines, thereby demonstrating analytic techniques which may be utilized to evaluate such servicing doctrines. To illustrate the...

Error Probability in Decision Functions for Character Recognition
J. T. Chu, J. C. Chueh
Pages: 273-280
DOI: 10.1145/321386.321390
Upper bounds for the error probability of a Bayes decision function are derived in terms of the differences among the probability distributions of the features used in character recognition. Applications to feature selection and error reduction...

Models of Computations and Systems—Evaluation of Vertex Probabilities in Graph Models of Computations
David Martin, Gerald Estrin
Pages: 281-299
DOI: 10.1145/321386.321391
This paper concerns itself with the modeling of computations and systems and the generation of a priori estimates of expected computation time for given problems on given processing systems. In particular, methods are discussed for determining...

Path Detection in Multidimensional Iterative Arrays
William M. Waite
Pages: 300-310
DOI: 10.1145/321386.321392
An iterative array is defined as an infinite set of identical blocks, interconnected in a regular manner. Each block has inputs and outputs, with internal connections from certain inputs to certain outputs. This paper is concerned with the...

A Convergent Algorithm for Solving Polynomial Algorithms
J. B. Moore
Pages: 311-315
DOI: 10.1145/321386.321393
The method of steepest descent is applied in a convergent procedure to determine the zeros of polynomials having either real or complex coefficients. By expressing the polynomials in terms of the Siljak functions, the methods are readily...

Iterative Refinement in Floating Point
Cleve B. Moler
Pages: 316-321
DOI: 10.1145/321386.321394
Iterative refinement reduces the roundoff errors in the computed solution to a system of linear equations. Only one step requires higher precision arithmetic. If sufficiently high precision is used, the final result is shown to be very...

A Machine-Independent Theory of the Complexity of Recursive Functions
Manuel Blum
Pages: 322-336
DOI: 10.1145/321386.321395
The number of steps required to compute a function depends, in general, on the type of computer that is used, on the choice of computer program, and on the input-output code. Nevertheless, the results obtained in this paper are so general as to...

A Uniform Random Number Generator Based on the Combination of Two Congruential Generators
W. J. Westlake
Pages: 337-340
DOI: 10.1145/321386.321396
A method of generating pseudo-random uniform numbers based on the combination of two congruential generators is described. It retains two of the desirable features of congruential generators, namely, the long cycle and the case of implementation...

Resolution by Iteration of Some Nonlinear Systems
O. G. Mancino
Pages: 341-350
DOI: 10.1145/321386.321397
For a system of nonlinear equations satisfying certain conditions it is shown that a solution exists and is unique. An iterative method that starts with an initial arbitrary approximation is presented....

A Test for Instability in the Numerical Solution of Ordinary Differential Equations
Fred T. Krogh
Pages: 351-354
DOI: 10.1145/321386.321398
A procedure is described to test the individual components of the numerical solution to a system of differential equations for relative instability. Although the test is based on the theory for linear differential equations, it has also worked...

A Procedure for Checking Equality of Regular Expressions
A. Ginzburg
Pages: 355-362
DOI: 10.1145/321386.321399
A simple “mechanical” procedure is described for checking equality of regular expressions. The procedure, based on the work of A. Salomaa, uses derivatives of regular expressions and transition graphs. Given a regular...

On the Numerical Solution of a Quasi-Linear Elliptic Equation
C. W. Cryer
Pages: 363-375
DOI: 10.1145/321386.321400
A boundary value problem for the quasi-linear elliptic equation (xx/q2s)x +...

Irreducible Topological Components of an Arbitrary Boolean Truth Function and Generation of Their Minimal Coverings
Alan Natapoff
Pages: 376-381
DOI: 10.1145/321386.321401
An extension of the work initiated by Quine in reducing an arbitrary Boolean truth function to its minimal form is presented. Apart from the unique parts of the form, the entire class of nonunique forms is discussed. The portion of the truth...

Note Concerning the Algebraic Theory of Automata
H. E. Pickett
Pages: 382-388
DOI: 10.1145/321386.321402
If an automaton is strongly connected, all of its automorphisms are regular permutations. It is proved that given any two groups G and H of regular permutations on finite sets A and...

One-way stack automata
Seymour Ginsburg, Sheila A. Greibach, Michael A. Harrison
Pages: 389-418
DOI: 10.1145/321386.321403
A number of operations which either preserve sets accepted by one-way stack automata or preserve sets accepted by deterministic one-way stack automata are presented. For example, sequential transduction preserves the former; set complementation,...

Corrigendum: “On the Boolean Matrix Equation M=∨i=1Mi
J. M. S. Simoes Pereira
Pages: 419-420
DOI: 10.1145/321386.321404

Corrigendum: `` The Automorphism Group of the Direct Product of Strongly Related Automata''
G. P. Weeg
Page: 421
DOI: 10.1145/321386.321405