Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 20 Issue 2, April 1973

Set Covering by an All Integer Algorithm: Computational Experience
Ronald D. Koncal, Harvey M. Salkin
Pages: 189-193
DOI: 10.1145/321752.321753
Computational experience with a modified linear programming method for the inequality or equality set covering problem (i.e. minimize cx subject to Exe or Ex =...

Benefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm
V. Srinivasan, G. L. Thompson
Pages: 194-213
DOI: 10.1145/321752.321754
A computer code for the transportation problem that is even more efficient than the primal-dual method is developed. The code uses the well-known (primal) MODI method and is developed by a benefit-cost investigation of the possible strategies...

Canonical Precedence Schemes
James N. Gray, Michael A. Harrison
Pages: 214-234
DOI: 10.1145/321752.321755
A general theory of canonical precedence analysis is defined and studied. The familiar types of precedence analysis such as operator precedence or simple precedence occur as special cases of this theory. Among the theoretical results obtained...

A Formalization of Transition Diagram Systems
David Bruce Lomet
Pages: 235-257
DOI: 10.1145/321752.321756
The transition diagram systems first introduced by Conway are formalized in terms of a restricted deterministic pushdown acceptor (DPDA) called a nested DPDA. It is then established that the class of nested DPDA's is capable of accepting all...

Recent Studies in Automatic Text Analysis and Document Retrieval
G. Salton
Pages: 258-278
DOI: 10.1145/321752.321757
Many experts in mechanized text processing now agree that useful automatic language analysis procedures are largely unavailable and that the existing linguistic methodologies generally produce disappointing results. An attempt is made in the...

Best Least Squares Solutions to Finite Difference Equations Using the Generalized Inverse and Tensor Product Methods
John F. Dalphin, Victor Lovass-Nagy
Pages: 279-289
DOI: 10.1145/321752.321758
A direct (noniterative) method for solving some singular systems of equations arising from finite difference approximations to partial differential equations is developed. The Moore-Penrose generalized inverse of some large tensor product...

Optimal Covering Algorithms in Methods of Search for Solving Polynomial Equations
Armin Friedli
Pages: 290-300
DOI: 10.1145/321752.321759
Covering algorithms utilized in methods of search for finding zeros of complex polynomials are investigated from both a deterministic and a probabilistic point of view. q-coverings are found to be optimal, and numerical examples...

A Midpoint Phenomenon
A. J. Goldstein, P. L. Richman
Pages: 301-304
DOI: 10.1145/321752.321760
Finite-precision interval arithmetic evaluation of a function ƒ of n variables at an n-dimensional rectangle T which is the Cartesian product of intervals yields an interval which is...

Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
Jacques Morgenstern
Pages: 305-306
DOI: 10.1145/321752.321761
A lower bound for the number of additions necessary to compute a family of linear functions by a linear algorithm is given when an upper bound c can be assigned to the modulus of the complex numbers involved in the computation....

Optimization of Static Loading and Sizing of Multilevel Memory Systems
S. R. Arora, A. Gallo
Pages: 307-319
DOI: 10.1145/321752.321762
The following two important aspects of multilevel static memory management are treated: (1) memory loading, and (2) memory sizing. An algorithm is developed for the optimal loading of program and data files in various memory levels of given...

Efficient Exercising of Switching Elements in Combinatorial Nets
Donald L. Richards
Pages: 320-332
DOI: 10.1145/321752.321763
The work described in a previous paper, “Efficient Exercising of Switching Elements in Nets of Identical Gates,” is continued. Sections 1, 3, and 4 of the previous paper are prerequisites to the current work. Exercising,...

A Complete Mechanization of Second-Order Type Theory
Tomasz Pietrzykowski
Pages: 333-364
DOI: 10.1145/321752.321764
A generalization of the resolution method for higher order logic is presented. The languages acceptable for the method are phrased in a theory of types of order w (all finite types)—including the &lgr;-operator,...