Journal of the ACM, Volume 37, 1990
Volume 37, Number 1, January 1990
- Stavros S. Cosmadakis, Paris C. Kanellakis, Moshe Y. Vardi:
Polynomial-Time Implication Problems for Unary Inclusion Dependencies. 15-46 - Joseph Y. Halpern, John H. Williams, Edward L. Wimmers:
Completeness of Rewrite Rules and Rewrite Strategies for FP. 86-143
Volume 37, Number 2, April 1990
- Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, Robert Endre Tarjan:
Faster Algorithms for the Shortest Path Problem. 213-223 - Béla Bollobás, Andrei Z. Broder, István Simon:
The Cost Distribution of Clustering in Random Probing. 224-237 - Baruch Awerbuch, Oded Goldreich, David Peleg, Ronen Vainish:
A Trade-Off between Information and Communication in Broadcast Protocols. 238-256 - François Baccelli, Zhen Liu:
On the Execution of Parallel Programs on Multiprocessor Systems-A Queuing Theory Approach. 373-414 - Ker-I Ko:
Separating and Collapsing Results on the Relativized Probabilistic Polynomial-Time Hierarchy. 415-438
Volume 37, Number 3, July 1990
- Lawrence L. Larmore, Daniel S. Hirschberg:
A Fast Algorithm for Optimal Length-Limited Huffman Codes. 464-473 - Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, Rüdiger Reischuk:
Renaming in an Asynchronous Environment. 524-548 - Joseph Y. Halpern, Yoram Moses:
Knowledge and Common Knowledge in a Distributed Environment. 549-587 - Ariel Orda, Raphael Rom:
Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length. 607-625 - Krishna R. Pattipati, Michael M. Kostreva, John L. Teele:
Approximate Mean Value Analysis Algorithms for Queuing Networks: Existence, Uniqueness, and Convergence Results. 643-673 - Yuri Gurevich, Saharon Shelah:
Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space. 674-687
Volume 37, Number 4, October 1990
- David A. Briggs:
A Correction of the Termination Conditions of the Henschen-Naqvi Technique. 712-719 - Dorit S. Hochbaum, J. George Shanthikumar:
Convex Separable Optimization Is Not Much Harder than Linear Optimization. 843-862 - Peter G. Harrison, Naresh M. Patel:
The Representation of Multistage Interconnection Networks in Queuing Models of Parallel Systems. 863-898