Journal of the ACM -- 1990

Volume 37, Number 1, January 1990

• Phokion G. Kolaitis and Christos H. Papadimitriou. Some computational aspects of circumscription. Journal of the ACM, 37(1):1-14, January 1990. Citations. [BibTeX entry]

• Stavros S. Cosmadakis, Paris C. Kanellakis, and Moshe Y. Vardi. Polynomial-time implication problems for unary inclusion dependencies. Journal of the ACM, 37(1):15-46, January 1990. Citations. [BibTeX entry]

• Joxan Jaffar. Minimal and complete word unification. Journal of the ACM, 37(1):47-85, January 1990. Citations. [BibTeX entry]

• Joseph Y. Halpern, John H. Williams, and Edward L. Wimmers. Completeness of rewrite rules and rewrite strategies for FP. Journal of the ACM, 37(1):86-143, January 1990. Citations. [BibTeX entry]

• Charles Knessl and Charles Tier. Asymptotic expansions for large closed queuing networks. Journal of the ACM, 37(1):144-174, January 1990. [BibTeX entry]

• Attila Máté. Nondeterministic polynomial-time computations and models of arithmetic. Journal of the ACM, 37(1):175-193, January 1990. Citations. [BibTeX entry]

Volume 37, Number 2, April 1990

• Henry W. Davis. Cost-error relationships in A* tree-searching. Journal of the ACM, 37(2):195-199, April 1990. [BibTeX entry]

• Bernard Chazelle. Lower bounds for orthogonal range searching: I. the reporting case. Journal of the ACM, 37(2):200-212, April 1990. Citations. [BibTeX entry]

• Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, and Robert E. Tarjan. Faster algorithms for the shortest path problem. Journal of the ACM, 37(2):213-223, April 1990. Citations. [BibTeX entry]

• Béla Bollobás, Andrei Z. Broder, and Istvan Simon. The cost distribution of clustering in random probing. Journal of the ACM, 37(2):224-237, April 1990. [BibTeX entry]

• Baruch Awerbuch, Oded Goldreich, David Peleg, and Ronen Vainish. A trade-off between information and communication in broadcast protocols. Journal of the ACM, 37(2):238-256, April 1990. Citations. [BibTeX entry]

• Maurice Herlihy. Concurrency and availability as dual properties of replicated atomic data. Journal of the ACM, 37(2):257-278, April 1990. [BibTeX entry]

• Martín Abadi and Zohar Manna. Nonclausal deduction in first-order temporal logic. Journal of the ACM, 37(2):279-317, April 1990. Citations. [BibTeX entry]

• Farhad Shahrokhi and D. W. Matula. The maximum concurrent flow problem. Journal of the ACM, 37(2):318-334, April 1990. Citations. [BibTeX entry]

• J. A. Bergstra, J. Heering, and P. Klint. Module algebra. Journal of the ACM, 37(2):335-372, April 1990. Citations. [BibTeX entry]

• François Baccelli and Zhen Lu. On the execution of parallel programs on multiprocessor systems -- a queuing theory approach. Journal of the ACM, 37(2):373-414, April 1990. Citations. [BibTeX entry]

• Ker-I Ko. Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy. Journal of the ACM, 37(2):415-438, April 1990. Citations. [BibTeX entry]

Volume 37, Number 3, July 1990

• Bernard Chazelle. Lower bounds for orthogonal range searching II. the arithmetic model. Journal of the ACM, 37(3):439-463, July 1990. Citations. [BibTeX entry]

• Lawrence L. Larmore and Daniel S. Hirschberg. A fast algorithm for optimal length-limited Huffman codes. Journal of the ACM, 37(3):464-473, July 1990. Citations. [BibTeX entry]

• Marc H. Graham and Ke Wang. On the equivalence of an egd to a set of fd's. Journal of the ACM, 37(3):474-490, July 1990. [BibTeX entry]

• In Kyung Ryu and Alexander Thomasian. Analysis of database performance with dynamic locking. Journal of the ACM, 37(3):491-523, July 1990. Citations. [BibTeX entry]

• Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rüdiger Reischuk. Renaming in an asynchronous environment. Journal of the ACM, 37(3):524-548, July 1990. Citations. [BibTeX entry]

• Joseph Y. Halpern and Yoram Moses. Knowledge and common knowledge in a distributed environment. Journal of the ACM, 37(3):549-587, July 1990. Citations. [BibTeX entry]

• Aydin Üresin and Michel Dubois. Parallel asynchronous algorithms for discrete data. Journal of the ACM, 37(3):588-606, July 1990. Citations. [BibTeX entry]

• Ariel Orda and Raphael Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM, 37(3):607-625, July 1990. [BibTeX entry]

• Yijie Han and Robert A. Wagner. An efficient and fast parallel-connected component algorithm. Journal of the ACM, 37(3):626-642, July 1990. Citations. [BibTeX entry]

• K. R. Pattipati, M. M. Kostreva, and J. L. Teele. Approximate mean value analysis algorithms for queuing networks: Existence, uniqueness, and convergence results. Journal of the ACM, 37(3):643-673, July 1990. [BibTeX entry]

• Yuri Gurevich and Saharon Shelah. Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space. Journal of the ACM, 37(3):674-687, July 1990. [BibTeX entry]

Volume 37, Number 4, October 1990

• Wojciech Szpankowski. Patricia tries again revisited. Journal of the ACM, 37(4):691-711, October 1990. Citations, etc. [BibTeX entry]

• David A. Briggs. A correction of the termination conditions of the Henschen-Naqvi technique. Journal of the ACM, 37(4):712-719, October 1990. References, etc. [BibTeX entry]

• Danny Dolev, Ruediger Reischuk, and H. Raymond Strong. Early stopping in Byzantine agreement. Journal of the ACM, 37(4):720-741, October 1990. References, Citations, etc. [BibTeX entry]

• Tobias Nipkow. Unification in primal algebras, their powers and their varieties. Journal of the ACM, 37(4):742-776, October 1990. Abstract, Citations, etc. [BibTeX entry]

• Gopalan Nadathur and Dale Miller. Higher-order Horn clauses. Journal of the ACM, 37(4):777-814, October 1990. References, Citations, etc. [BibTeX entry]

• J. R. B. Cockett and J. A. Hierrera. Decision tree reduction. Journal of the ACM, 37(4):815-842, October 1990. Additional information. [BibTeX entry]

• Dorit S. Hochbaum and J. George Shanthikumar. Convex separable optimization is not much harder than linear optimization. Journal of the ACM, 37(4):843-862, October 1990. References, Citations, etc. [BibTeX entry]

• Peter G. Harrison and Naresh M. Patel. The representation of multistage interconnection networks in queuing models of parallel systems. Journal of the ACM, 37(4):863-898, October 1990. References, etc. [BibTeX entry]

Shortcuts: