Journal of the ACM, Volume 37, 1990

Volume 37, Number 1, January 1990

Phokion G. Kolaitis, Christos H. Papadimitriou:
Some Computational Aspects of Circumscription. 1-14
Stavros S. Cosmadakis, Paris C. Kanellakis, Moshe Y. Vardi:
Polynomial-Time Implication Problems for Unary Inclusion Dependencies. 15-46
Joxan Jaffar:
Minimal and Complete Word Unification. 47-85
Joseph Y. Halpern, John H. Williams, Edward L. Wimmers:
Completeness of Rewrite Rules and Rewrite Strategies for FP. 86-143
Charles Knessl, Charles Tier:
Asymptotic Expansions for Large Closed Queuing Networks. 144-174
Attila Máté:
Nondeterministic Polynomial-Time Computations and Models of Arithmetic. 175-193

Henry W. Davis:
Cost-Error Relationships in A* Tree-Searching. 195-199
Bernard Chazelle:
Lower Bounds for Orthogonal Range Searching: I. The Reporting Case. 200-212
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
Maurice Herlihy:
Concurrency and Availability as Dual Properties of Replicated Atomic Data. 257-278
Martín Abadi, Zohar Manna:
Nonclausal Deduction in First-Order Temporal Logic. 279-317
Farhad Shahrokhi, David W. Matula:
The Maximum Concurrent Flow Problem. 318-334
Jan A. Bergstra, Jan Heering, Paul Klint:
Module Algebra. 335-372
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

Bernard Chazelle:
Lower Bounds for Orthogonal Range Searching II. The Arithmetic Model. 439-463
Lawrence L. Larmore, Daniel S. Hirschberg:
A Fast Algorithm for Optimal Length-Limited Huffman Codes. 464-473
Marc H. Graham, Ke Wang:
On the Equivalence of an Egd to a Set of Fd's. 474-490
In Kyung Ryu, Alexander Thomasian:
Analysis of Database Performance with Dynamic Locking. 491-523
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
Aydin Üresin, Michel Dubois:
Parallel Asynchronous Algorithms for Discrete Data. 588-606
Ariel Orda, Raphael Rom:
Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length. 607-625
Yijie Han, Robert A. Wagner:
An Efficient and Fast Parallel-Connected Component Algorithm. 626-642
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

Wojciech Szpankowski:
Patricia Tries Again Revisited. 691-711
David A. Briggs:
A Correction of the Termination Conditions of the Henschen-Naqvi Technique. 712-719
Danny Dolev, Rüdiger Reischuk, H. Raymond Strong:
Early Stopping in Byzantine Agreement. 720-741
Tobias Nipkow:
Unification in Primal Algebras, Their Powers and Their Varieties. 742-776
Gopalan Nadathur, Dale Miller:
Higher-Order Horn Clauses. 777-814
J. Robin B. Cockett, J. A. Hierrera:
Decision Tree Reduction. 815-842
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