Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 39 Issue 1, Jan. 1992

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