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