Journal of the ACM

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

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 0(h^2m+2) provided the integrand has 2m+2 bounded partial derivatives in each ...

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

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 key-to-address ...

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

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

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

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

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

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 polygenic systems, this ...

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.

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 a one-third octave ...

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 interconnected (logic) ...