ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 16 Issue 1, Jan. 1969

A Policy for JACM
Gerard Salton
Page: 1
DOI: 10.1145/321495.321496
When the Journal of the Association for Computing Machinery was first issued in 1954, the intention was to make it into the definitive journal in the computer area. This in many ways it has become. Even in some of the applied...

One Man's View of Computer Science
R. W. Hamming
Pages: 3-12
DOI: 10.1145/321495.321497
A number of observations and comments are directed toward suggesting that more than the usual engineering flavor be given to computer science. The engineering aspect is important because most present difficulties in this field do not involve the...

MERCURY: H system for the computer-aided distribution of technical reports
W. S. Brown, J. F. Traub
Pages: 13-25
DOI: 10.1145/321495.321498
MERCURY is a computer-aided system for the selective distribution of Bell Telephone Laboratories technical reports to employees. MERCURY is based on the idea that the job of distribution should be divided between the author and the reader with...

Automatic Question-Answering of English-Like Questions About Simple Diagrams
Manfred Kochen
Pages: 26-48
DOI: 10.1145/321495.321499

Semi-Automated Mathematics
J. R. Guard, F. C. Oglesby, J. H. Bennett, L. G. Settle
Pages: 49-62
DOI: 10.1145/321495.321500
The fifth in a series of experiments in semi-automated mathematics is described. These experiments culminated in large complex computer programs which allow a mathematician to prove mathematical theorems on an man/machine basis. SAM V, the fifth...

Recursive Formulas for the Evaluation of the Convolutions Integral
H. H. Trauboth
Pages: 63-72
DOI: 10.1145/321495.321501
Recursive formulas for the numerical evaluation of the real convolution integral are derived for the case in which the impulse response is given analytically. These formulas require considerably less computation time and memory space than the...

Analysis of a Drum Input/Output Queue Under Scheduled Operation in a Paged Computer System
E. G. Coffman, Jr.
Pages: 73-90
DOI: 10.1145/321495.321502
Properly scheduling the usage of input output devices is an important aspect of the design of modern multiprogramming systems featuring a paged environment. In this paper magnetic drums in the role of auxiliary memories are studied in the...

An Infinite Hierarchy of Context-Free Languages
Sheila A. Greibach
Pages: 91-106
DOI: 10.1145/321495.321503

Programmed Grammars and Classes of Formal Languages
Daniel J. Rosenkrantz
Pages: 107-131
DOI: 10.1145/321495.321504

On Decompositions of Regular Events
J. A. Brzozowski, Rina Cohen
Pages: 132-144
DOI: 10.1145/321495.321505
Decompositions of regular events into star events, i.e. events of the form W = V*, are studied. Mathematically, the structure of a star event is that of a monoid. First it is shown that every regular event...

On the Length of Programs for Computing Finite Binary Sequences: statistical considerations
Gregory J. Chaitin
Pages: 145-159
DOI: 10.1145/321495.321506
An attempt is made to carry out a program (outlined in a previous paper) for defining the concept of a random or patternless, finite binary sequence, and for subsequently defining a random or patternless, infinite binary sequence to be a...

On the Complexity of Undecidable Problems in Automata Theory
J. Hartmanis
Pages: 160-167
DOI: 10.1145/321495.321507
Some general results about hierarchies of undecidable problems in automata theory are given, and studies are described which show how properties of sets accepted by automata (i.e. languages) change from decidable to undecidable problems as the...

Some Results on Tape-Bounded Turing Machines
J. E. Hopcroft, J. D. Ullman
Pages: 168-177
DOI: 10.1145/321495.321508
Classes of tape-bounded Turing machines similar to the on-line and off-line Turing machines, but without the restrictions that each machine halt and be deterministic, are studied. It is shown that the lower bounds on tape complexity of [1]...

A Model of Replication
Abraham Waksman
Pages: 178-188
DOI: 10.1145/321495.321509
A one-dimensional array of finite-state machines is being considered as a model for sequence replication. The authors consider the initial state of the first k machines in the array as representing the sequence of...