Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 17 Issue 3, July 1970

On the Approximate Solution of Free Boundary Problems Using Finite Differences
C. W. Cryer
Pages: 397-411
DOI: 10.1145/321592.321593
Two algorithms for solving free boundary problems in two dimensions are described. The algorithms use the method of finite differences and are automated versions of methods due to Southwell. The algorithms have been implemented as a general...

An Initial-Value Theory for Fredholm Integral Equations With Semidegenerate Kernels
H. H. Kagiwada, R. Kalaba
Pages: 412-419
DOI: 10.1145/321592.321594
The Fredholm integral equation where the kernel is semidegenerate has many applications. The solution of this integral equation may be studied as a function of the upper limit of integration x, while t remains...

Nonlinear Interpolation of Multivariable Functions by the Monte Carlo Method
Takao Tsuda, Kozo Ichida
Pages: 420-425
DOI: 10.1145/321592.321595
The nonlinear interpolation of functions of very many variables is discussed. Deterministic termwise assessment of a prohibitively large number of terms naturally leads to a choice of random sampling from these numerous terms. After introduction...

Optimization of Memory Hierarchies in Multiprogrammed Systems
C. V. Ramamoorthy, K. M. Chandy
Pages: 426-445
DOI: 10.1145/321592.321596
The optimization of memory hierarchy involves the selection of types and sizes of memory devices such that the average access time to an information block is a minimum for a particular cost constraint. It is assumed that the frequency of usage...

Nonlinear Regression With Linear Constraints: An Extension of the Magnified Diagonal Method
Richard I. Shrager
Pages: 446-452
DOI: 10.1145/321592.321597
A syntax-directed picture analysis system based on a formal picture description scheme is described. The system accepts a description of a set of pictures in terms of a grammar generating strings in a picture description language; the grammar is...

Parsing of Graph-Representable Pictures
Alan C. Shaw
Pages: 453-481
DOI: 10.1145/321592.321598
A syntax-directed picture analysis system based on a formal picture description scheme is described. The system accepts a description of a set of pictures in terms of a grammar generating strings in a picture description language; the grammar is...

The Use of Information in Sorting
H. Lynn Beus
Pages: 482-495
DOI: 10.1145/321592.321599
The information-gathering aspect of sorting is considered from a theoretical viewpoint. A large class, R, of sorting algorithms is defined, based on the idea of information use. Properties of this algorithm class are developed,...

Samplesort: A Sampling Approach to Minimal Storage Tree Sorting
W. D. Frazer, A. C. McKellar
Pages: 496-507
DOI: 10.1145/321592.321600
The methods currently in use and previously proposed for the choice of a root in minimal storage tree sorting are in reality methods for making inefficient statistical estimates of the median of the sequence to be sorted. By making efficient use...

Tree Structures for Optimal Searching
L. E. Stanfel
Pages: 508-517
DOI: 10.1145/321592.321601
It is shown that, owing to certain restrictions placed upon the set of admissible structures, some previous solutions have not characterized trees in which expected search time is minimized. The more general problem is shown to be a special case...

Controllability of Nonlinear Sequential Networks
Frederic J. Mowle
Pages: 518-524
DOI: 10.1145/321592.321602
A sequential network is said to be controllable if there exists at least one integer k such that it is possible to transition between any pair of arbitrary states (S&agr;,...

A Linear Format for Resolution With Merging and a New Technique for Establishing Completeness
Robert Anderson, W. W. Bledsoe
Pages: 525-534
DOI: 10.1145/321592.321603
A new technique is given for establishing the completeness of resolution-based deductive systems for first-order logic (with or without equality) and several new completeness results are proved using this technique. The technique leads to very...

Interpolation Theorems for Resolution in Lower Predicate Calculus
James R. Slagle
Pages: 535-542
DOI: 10.1145/321592.321604
The resolution principle is an inference rule for quantifier-free first-order predicate calculus. In the past, the completeness theorems for resolution and its refinements have been stated and proved for finite sets of clauses. It is easy (by...

Legality and Other Properties of Graph Models of Computations
J. L. Baer, D. P. Bovet, G. Estrin
Pages: 543-554
DOI: 10.1145/321592.321605
Directed graphs having logical control associated with each vertex have been introduced as models of computational tasks for automatic assignment and sequencing on parallel processor systems. A brief review of their properties is given. A...

Formalization of Properties of Functional Programs
Zohar Manna, Amir Pnueli
Pages: 555-569
DOI: 10.1145/321592.321606
The problems of convergence, correctness, and equivalence of computer programs can be formulated by means of the satisfiability or validity of certain first-order formulas. An algorithm is presented for constructing such formulas for functional...