Journal of the ACM -- 1993

Volume 40, Number 1, January 1993

• Jean Gallier, Paliath Narendran, David Plaisted, Stan Raatz, and Wayne Snyder. An algorithm for finding canonical sets of ground rewrite rules in polynomial time. Journal of the ACM, 40(1):1-16, January 1993. References and Citations. [BibTeX entry]

• Danny Dolev, Cynthia Dwork, Orli Waarts, and Moti Yung. Perfectly secure message transmission. Journal of the ACM, 40(1):17-47, January 1993. References and Citations. [BibTeX entry]

• John D. Hobby. Generating automatically tuned bitmaps from outlines. Journal of the ACM, 40(1):48-94, January 1993. References. [BibTeX entry]

• Leonard Pitt and Manfred K. Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. Journal of the ACM, 40(1):95-142, January 1993. References and Citations. [BibTeX entry]

• Robert Harper, Furio Honsell, and Gordon Plotkin. A framework for defining logics. Journal of the ACM, 40(1):143-184, January 1993. References and Citations. [BibTeX entry]

• Dana Angluin, Lisa Hellerstein, and Marek Karpinski. Learning read-once formulas with queries. Journal of the ACM, 40(1):185-210, January 1993. References and Citations. [BibTeX entry]

Volume 40, Number 2, April 1993

• Nader H. Bshouty. On the complexity of functions for random access machines. Journal of the ACM, 40(2):211-223, April 1993. References and Citations. [BibTeX entry]

• Andrea S. LaPaugh. Recontamination does not help to search a graph. Journal of the ACM, 40(2):224-245, April 1993. References and Citations. [BibTeX entry]

• David McAllester and Robert Givan. Taxonomic syntax for first order inference. Journal of the ACM, 40(2):246-283, April 1993. References and Citations. [BibTeX entry]

• David A. McAllester. Automatic recognition of tractability in inference relations. Journal of the ACM, 40(2):284-303, April 1993. References and Citations. [BibTeX entry]

• David M. Nicol. The cost of conservative synchronization in parallel discrete event simulations. Journal of the ACM, 40(2):304-333, April 1993. [BibTeX entry]

• Gil Neiger and Sam Toueg. Simulating synchronized clocks and common knowledge in distributed systems. Journal of the ACM, 40(2):334-367, April 1993. References and Citations. [BibTeX entry]

• Thomas Lengauer and Egon Wanke. Efficient decision procedures for graph properties on context-free graph languages. Journal of the ACM, 40(2):368-393, April 1993. References and Citations. [BibTeX entry]

• Kin K. Leung. An execution/sleep scheduling policy for serving an additional job in priority queueing systems. Journal of the ACM, 40(2):394-417, April 1993. [BibTeX entry]

Volume 40, Number 3, July 1993

• Don Coppersmith, Peter Doyle, Prabhakar Raghavan, and Marc Snir. Random walks on weighted graphs and applications to on-line algorithms. Journal of the ACM, 40(3):421-453, July 1993. References and Citations. [BibTeX entry]

• Howard J. Karloff and Prabhakar Raghavan. Randomized algorithms and pseudorandom numbers. Journal of the ACM, 40(3):454-476, July 1993. References and Citations. [BibTeX entry]

• Franz Baader. Unification in commutative theories, Hilbert's basis theorem and Gröbner bases. Journal of the ACM, 40(3):477-503, July 1993. Citations. [BibTeX entry]

• Neil V. Murray and Erik Rosenthal. Dissolution: Making paths vanish. Journal of the ACM, 40(3):504-535, July 1993. Abstract, References, Citations, etc. [BibTeX entry]

• C. A. Johnson. Factorization and circuit in the connection method. Journal of the ACM, 40(3):536-557, July 1993. References. [BibTeX entry]

• Tie-Cheng Wang. Z-module reasoning: An equality-oriented proving method with built-in ring axioms. Journal of the ACM, 40(3):558-606, July 1993. References. [BibTeX entry]

• Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform and learnability. Journal of the ACM, 40(3):607-620, July 1993. References and Citations. [BibTeX entry]

• Kurt Mehlhorn and Athanasios Tsakalidis. Dynamic interpolation search. Journal of the ACM, 40(3):621-634, July 1993. References and Citations. [BibTeX entry]

• Marc J. van Kreveld and Mark H. Overmars. Union-copy structures and dynamic segment trees. Journal of the ACM, 40(3):635-652, July 1993. References and Citations. [BibTeX entry]

• J. C. M. Baeten, J. A. Bergstra, and J. W. Klop. Decidability of bisimulation equivalence for processes generating context-free languages. Journal of the ACM, 40(3):653-682, July 1993. References and Citations. [BibTeX entry]

• Haim Gaifman, Harry Mairson, Yehoshua Sagiv, and Moshe Y. Vardi. Undecidable optimization problems for database logic programs. Journal of the ACM, 40(3):683-713, July 1993. References and Citations. [BibTeX entry]

• Randolph Nelson and Donald Towsley. A performance evaluation of several priority policies for parallel processing systems. Journal of the ACM, 40(3):714-740, July 1993. References. [BibTeX entry]

• Sandeep Bhatt and Jin-Yi Cai. Taking random walks to grow trees in hypercubes. Journal of the ACM, 40(3):741-764, July 1993. References and Citations. [BibTeX entry]

• Richard M. Karp and Yanjun Zhang. Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM, 40(3):765-789, July 1993. References and Citations. [BibTeX entry]

Volume 40, Number 4, September 1993

• Edith Cohen and Nimrod Megiddo. Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs. Journal of the ACM, 40(4):791-830, September 1993. References and Citations. [BibTeX entry]

• Philip S. Yu, Daniel M. Dias, and Stephen S. Lavenberg. On the analytical modeling of database concurrency control. Journal of the ACM, 40(4):831-872, September 1993. References. [BibTeX entry]

• Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM, 40(4):873-890, September 1993. References and Citations. [BibTeX entry]

• Foto Afrati and Christos H. Papadimitriou. The parallel complexity of simple logic programs. Journal of the ACM, 40(4):891-916, September 1993. References and Citations. [BibTeX entry]

• Joseph Y. Halpern and Mark R. Tuttle. Knowledge, probability, and adversaries. Journal of the ACM, 40(4):917-962, September 1993. References and Citations. [BibTeX entry]

• V. Wiktor Marek, Grigori F. Schwarz, and Miros{\l}aw Truszczy\'nski. Modal nonmonotonic logics: Ranges, characterization, computation. Journal of the ACM, 40(4):963-990, September 1993. References and Citations. [BibTeX entry]

Volume 40, Number 5, November 1993

• E. G. Coffman, Jr. and M. R. Garey. Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling. Journal of the ACM, 40(5):991-1018, November 1993. References and Citations. [BibTeX entry]

• Zhi-Quan Luo and John N. Tsitsiklis. On the communication complexity of distributed algebraic computation. Journal of the ACM, 40(5):1019-1047, November 1993. References and Citations. [BibTeX entry]

• Bruce Donald, Patrick Xavier, John Canny, and John Reif. Kinodynamic motion planning. Journal of the ACM, 40(5):1048-1066, November 1993. References and Citations. [BibTeX entry]

• Y. C. Tay. On the optimality of strategies for multiple joins. Journal of the ACM, 40(5):1067-1086, November 1993. References and Citations. [BibTeX entry]

• Alan Fekete, Nancy Lynch, Yishay Mansour, and John Spinelli. The impossibility of implementing reliable communication in the face of crashes. Journal of the ACM, 40(5):1087-1107, November 1993. References and Citations. [BibTeX entry]

• Martin Charles Golumbic and Ron Shamir. Complexity and algorithms for reasoning about time: A graph-theoretic approach. Journal of the ACM, 40(5):1108-1133, November 1993. References and Citations. [BibTeX entry]

• Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, and Detlef Seese. An algebraic theory of graph reduction. Journal of the ACM, 40(5):1134-1164, November 1993. References and Citations. [BibTeX entry]

• Jean Fonlupt and Armand Nachef. Dynamic programming and the graphical traveling salesman problem. Journal of the ACM, 40(5):1165-1187, November 1993. [BibTeX entry]

• Alain Jean-Marie and Levent Gün. Parallel queues with resequencing. Journal of the ACM, 40(5):1188-1208, November 1993. References. [BibTeX entry]

• François Baccelli, Zhen Liu, and Don Towsley. Extremal scheduling of parallel processing with and without real-time constraints. Journal of the ACM, 40(5):1209-1237, November 1993. References. [BibTeX entry]

• Charles Knessl. On the sojourn time distribution in a finite capacity processor shared queue. Journal of the ACM, 40(5):1238-1301, November 1993. References. [BibTeX entry]

Shortcuts: