Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 32 Issue 2, April 1985

Soundness and completeness of a synthesis algorithm based on example computations
M. A. Bauer
Pages: 249-279
DOI: 10.1145/3149.3150
The problem of synthesizing a procedure from example computations is examined. An algorithm for this task is presented, and its success is considered. To do this, a model of procedures and example computations is introduced, and the class of...

On the efficiency of subsumption algorithms
G. Gottlob, A. Leitsch
Pages: 280-295
DOI: 10.1145/3149.214118
The costs of subsumption algorithms are analyzed by an estimation of the maximal number of unification attempts (worst-case unification complexity) made for deciding whether a clause C subsumes a clause D. For...

Feedback vertex sets and cyclically reducible graphs
Ching-Chy Wang, Errol L. Lloyd, Mary Lou Soffa
Pages: 296-313
DOI: 10.1145/3149.3159
The problem of finding a minimum cardinality feedback vertex set of a directed graph is considered. Of the classic NP-complete problems, this is one of the least understood. Although Karp showed the general problem to be NP-complete, a linear...

Beyond two-phase locking
G. N. Buckley, A. Silberschatz
Pages: 314-343
DOI: 10.1145/3149.3151
Many database systems maintain the consistency of the data by using a locking protocol to restrict access to data items. It has been previously shown that if no information is known about the method of accessing items in the database, then the...

Algorithms for resolving conflicts in dynamic storage allocation
Brenda S. Baker, Dan E. Willard
Pages: 327-343
DOI: 10.1145/3149.335126

Parallel algorithms for data compression
M. E. Gonzalez Smith, J. A. Storer
Pages: 344-373
DOI: 10.1145/3149.3152
Parallel algorithms for data compression by textual substitution that are suitable for VLSI implementation are studied. Both “static” and “dynamic” dictionary schemes are considered. ...

Impossibility of distributed consensus with one faulty process
Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson
Pages: 374-382
DOI: 10.1145/3149.214121
The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the...

The traveling salesman problem in graphs with 3-edge cutsets
G. Cornuéjols, D. Naddef, W. Pulleyblank
Pages: 383-410
DOI: 10.1145/3149.3154
This paper analyzes decomposition properties of a graph that, when they occur, permit a polynomial solution of the traveling salesman problem and a description of the traveling salesman polytope by a system of linear equalities and inequalities....

A fixpoint semantics for nondeterministic data flow
John Staples, V. L. Nguyen
Pages: 411-444
DOI: 10.1145/3149.3155
Criteria for adequacy of a data flow semantics are discussed and Kahn's successful semantics for functional (deterministic) data flow is reviewed. Problems arising from nondeterminism are introduced and the paper's approach to overcoming them is...

Optimal static load balancing in distributed computer systems
Asser N. Tantawi, Don Towsley
Pages: 445-465
DOI: 10.1145/3149.3156
A distributed computer system that consists of a set of heterogeneous host computers connected in an arbitrary fashion by a communications network is considered. A general model is developed for such a distributed computer system, in which the...

Decidable problems for powerful programs
Eitan M. Gurari
Pages: 466-483
DOI: 10.1145/3149.3157
Two of the most powerful classes of programs for which interesting decision problems are known to be solvable are the class of finite-memory programs and the class of programs that characterize the Presburger, or semilinear, sets. In this paper,...

A complexity theory based on Boolean algebra
S. Skyum, L. G. Valiant
Pages: 484-502
DOI: 10.1145/3149.3158
A projection of a Boolean function is a function obtained by substituting for each of its variables a variable, the negation of a variable, or a constant. Reducibilities among computational problems under this relation of projection are...