**Sequential Operations in Digital Picture Processing**

Azriel Rosenfeld, John L. Pfaltz

Pages: 471-494

DOI: 10.1145/321356.321357

**A Formal System for Differentiation**

E. K. Blum

Pages: 495-504

DOI: 10.1145/321356.321358

A formal system is presented for the differentiation of mathematical formulas which can be implemented on a digital computer. The system departs in concept from others in that the programming language is nonprocedural, permitting the statement...

**An Extension of Romberg Integration Procedures to N-Variables**

Edward B. Anders

Pages: 505-510

DOI: 10.1145/321356.321359

The Romberg method of numerical integration is extended to multidimensional integration. The elements of the mth column of the Romberg array are shown to approximate up to...

**Statistical Determination of Certain Mathematical Constants and Functions Using Computers**

Satya D. Dubey

Pages: 511-525

DOI: 10.1145/321356.321360

With the availability of high speed electronic computers it is now quite convenient to devise statistical experiments for the purpose of estimating certain mathematical constants and functions. The paper contains statistical formulas for...

**Analysis of the Address Assignment Problem for Clustered Keys**

Junichi Toyoda, Yoshikazu Tezuka, Yoshiro Kasahara

Pages: 526-532

DOI: 10.1145/321356.321361

The occurrence pattern of clusterings of keys is analyzed by use of the generating function. Probabilities of occurrences of several clustered patterns are given as the coefficients of generating functions. Moreover, the result when a...

**Two-Tape Simulation of Multitape Turing Machines**

F. C. Hennie, R. E. Stearns

Pages: 533-546

DOI: 10.1145/321356.321362

It has long been known that increasing the number of tapes used by a Turing machine does not provide the ability to compute any new functions. On the other hand, the use of extra tapes does make it possible to speed up the computation of certain...

**On the Length of Programs for Computing Finite Binary Sequences**

Gregory J. Chaitin

Pages: 547-569

DOI: 10.1145/321356.321363

The use of Turing machines for calculating finite binary sequences is studied from the point of view of information theory and the theory of recursive functions. Various results are obtained concerning the number of instructions in programs. A...

**On Context-Free Languages**

Rohit J. Parikh

Pages: 570-581

DOI: 10.1145/321356.321364

In this report, certain properties of context-free (CF or type 2) grammars are investigated, like that of Chomsky. In particular, questions regarding structure, possible ambiguity and relationship to finite automata are considered. The following...

**The Unsolvability of the Recognition of Linear Context-Free Languages**

Sheila A. Greibach

Pages: 582-587

DOI: 10.1145/321356.321365

The problem of whether a given context-free language is linear is shown to be recursively undecidable.

**The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages**

Thomas N. Hibbard, Joseph Ullian

Pages: 588-593

DOI: 10.1145/321356.321366

Call a (context-free) language unambiguous if it is not inherently ambiguous. In the absence of evidence to the contrary, the suspicion has arisen that the unambiguous languages might be precisely those languages with context-free complements....

**The Immortality Problem for Post Normal Systems**

Philip K. Hooper

Pages: 594-599

DOI: 10.1145/321356.321367

A natural problem, related to the (known unsolvable) halting problem for Post normal systems, arises when one considers, for a given Post normal system, whether the system halts (eventually) on every word over its alphabet. For...

**Discrete Analogs for Continuous Filters**

H. Shaw

Pages: 600-604

DOI: 10.1145/321356.321368

A substitution rule for obtaining discrete analogs for continuous filters is given. Transient responses of filters related by the rule are in exact agreement. Steady-state responses are in close agreement.

**Digital One-Third Octave Spectral Analysis**

C. D. Negron

Pages: 605-614

DOI: 10.1145/321356.321369

An economical approach is described for estimating power spectra from sampled data through the application of Z-transform theory. The method consists of computing a weighting sequence whose frequency characteristics approximate...

**The Placement of Computer Logic Modules**

J. S. Mamelak

Pages: 615-629

DOI: 10.1145/321356.321370

The object of the work described was to develop a procedure for the allocation of logic to cards, boards, platters and so on which utilize modular circuit design and etched wiring techniques.
A chain of logic elements is a set of...