**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...