Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 13 Issue 4, Oct. 1966

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