**New Algorithms for Bin Packing**

Andrew Chi-Chih Yao

Pages: 207-227

DOI: 10.1145/322186.322187

In the bin-packing problem a list L of n numbers are to be packed into unit-capacity bins. For any algorithm S, let r(S) be the maximum ratio...

**Reaching Agreement in the Presence of Faults**

M. Pease, R. Shostak, L. Lamport

Pages: 228-234

DOI: 10.1145/322186.322188

The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be...

**Equality and Domain Closure in First-Order Databases**

Raymond Reiter

Pages: 235-249

DOI: 10.1145/322186.322189

A class of first-order databases with no function signs is considered. A closed database DB is one for which the only existing individuals are those explicitly referred to in the formulas of DB. Formally, this is expressed by including in DB a...

**An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic**

Yehoshua Sagiv

Pages: 250-262

DOI: 10.1145/322186.322190

An algorithm is given for deciding whether a functional or a multivalued dependency &sgr; (with a right-hand side Y) is implied by a set of functional and multivalued dependencies &Sgr;. The running time of the...

**Can Any Stationary Iteration Using Linear Information Be Globally Convergent?**

G. W. Wasilkowski

Pages: 263-269

DOI: 10.1145/322186.322191

All known globally convergent iterations for the solution of a nonlinear operator equation ƒ(x) = 0 are either nonstationary or use nonlinear information. It is asked whether there exists a globally convergent stationary...

**Testing Deadlock-Freedom of Computer Systems**

Tiko Kameda

Pages: 270-280

DOI: 10.1145/322186.322192

The problem of determining whether it is possible for a set of “free-running” processes to become deadlocked is considered. It is assumed that any request by a process is immediately granted as long as there are enough free resource...

**The Cycle Time Distribution of Exponential Cyclic Queues**

We-Min Chow

Pages: 281-286

DOI: 10.1145/322186.322193

The cycle time distribution of a cyclic queue with two exponential servers is derived. Results show that when the population size N is large enough, the cycle time distribution is not sensitive to the ratio of service rates and...

**A New Algorithm for Preemptive Scheduling of Trees**

Teofilo F. Gonzalez, Donald B. Johnson

Pages: 287-312

DOI: 10.1145/322186.322194

An algorithm which schedules forests of n tasks on m identical processors in O(n log m) time, offline, is given. The schedules are optimal with respect to...

**Mean-Value Analysis of Closed Multichain Queuing Networks**

M. Reiser, S. S. Lavenberg

Pages: 313-322

DOI: 10.1145/322186.322195

It is shown that mean queue sizes, mean waiting times, and throughputs in closed multiple-chain queuing networks which have product-form solution can be computed recursively without computing product terms and normalization constants. The...

**Queuing Network Models with State-Dependent Routing**

Don Towsley

Pages: 323-337

DOI: 10.1145/322186.322196

A model of a closed queuing network within which customer routing between queues may depend on the state of the network is presented. The routing functions allowed may be rational functions of the queue lengths of various downstream queues which...

**On the Correctness of Semantic-Syntax-Directed Translations**

Ramachandran Krishnaswamy, Arthur B. Pyster

Pages: 338-355

DOI: 10.1145/322186.322197

The correctness of semantic-syntax-directed translators (SSDTs) is examined. SSDTs are a generalization of syntax-directed translators in which semantic information is employed to partially direct the translator. Sufficient conditions for an...

**Fast Decision Procedures Based on Congruence Closure**

Greg Nelson, Derek C. Oppen

Pages: 356-364

DOI: 10.1145/322186.322198

The notion of the congruence closure of a relation on a graph is defined and several algorithms for computing it are surveyed. A simple proof is given that the congruence closure algorithm provides a decision procedure for the...

**A Syntactic Theory of Message Passing**

Stephen A. Ward, Robert H. Halstead, Jr.

Pages: 365-383

DOI: 10.1145/322186.322199

Recent developments by Hewitt and others have stimulated interest in message-passing constructs as an alternative to the more conventional applicative semantics on which most current languages are based. The present work illuminates the...

**Lower Bounds on Information Transfer in Distributed Computations**

Harold Abelson

Pages: 384-392

DOI: 10.1145/322186.322200

Lower bounds on the interprocessor communication required for computing a differentiable real-valued function in a distributed network are derived. These bounds are independent of the network interconnection configuration, and they impose no...

**GO Is Polynomial-Space Hard**

David Lichtenstein, Michael Sipser

Pages: 393-401

DOI: 10.1145/322186.322201

It is shown that, given an arbitrary GO position on an n × n board, the problem of determining the winner is Pspace hard. New techniques are exploited to overcome the difficulties arising from the planar...

**Corrigendum: `` Control System Model for Critically Timed Success''**

Rainer Parchmann

Page: 402

DOI: 10.1145/322186.322202