**An optimal algorithm for intersecting line segments in the plane**

Bernard Chazelle, Herbert Edelsbrunner

Pages: 1-54

DOI: 10.1145/147508.147511

The main contribution of this work is an O(n log n + k)-time algorithm for computing all k intersections among n line segments in the plane....

**An O(log N) deterministic packet-routing scheme**

Eli Upfal

Pages: 55-70

DOI: 10.1145/147508.147517

A deterministic O(log N)-time algorithm for the problem of routing an aribitrary permutation on an N-processor bounded-degree network with bounded buffers is presented.
Unlike all...

**Syntactical characterization of a subset of domain-independent formulas**

Robert Demolombe

Pages: 71-94

DOI: 10.1145/147508.147520

A domain-independent formula of first-order predicate calculus is a formula whose evaluation in a given interpretation does not change when we add a new constant to the interpretation domain. The formulas used to express queries, integrity...

**Institutions: abstract model theory for specification and programming**

Joseph A. Goguen, Rod M. Burstall

Pages: 95-146

DOI: 10.1145/147508.147524

There is a population explosion among the logical systems used in computing science. Examples include first-order logic, equational logic, Horn-clause logic, higher-order logic, infinitary logic, dynamic logic, intuitionistic logic, order-sorted...

**Termination, deadlock, and divergence**

L. Aceto, M. Hennessy

Pages: 147-187

DOI: 10.1145/147508.147527

In this paper, a process algebra that incorporates explicit representations of successful termination, deadlock, and divergence is introduced and its semantic theory is analyzed. Both an operational and a denotational semantics for the language...

**Single-class bounds of multi-class queuing networks**

Lawrence W. Dowdy, Brian M. Carlson, Alan T. Krantz, Satish K. Tripathi

Pages: 188-213

DOI: 10.1145/147508.147530

In a closed, separable, queuing network model of a computer system, the number of customer classes is an input parameter. The number of classes and the class compositions are assumptions regarding the characteristics of the system's workload....

**How to sign given any trapdoor permutation**

Mihir Bellare, Silvio Micali

Pages: 214-233

DOI: 10.1145/147508.147537

A digital signature scheme is presented, which is based on the existence of any trapdoor permutation. The scheme is secure in the strongest possible natural sense: namely, it is secure against existential forgery under adaptive chosen message...

**Lower bounds for the low hierarchy**

Eric Allender, Lane A. Hemachandra

Pages: 234-251

DOI: 10.1145/147508.147546