Journal of the ACM, Volume 40, 1993

Volume 40, Number 1, January 1993

• Jean H. Gallier, Paliath Narendran, David A. Plaisted, Stan Raatz, Wayne Snyder:
  An Algorithm for Finding Canonical Sets of Ground Rewrite Rules in Polynomial Time. 1-16
  
• Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung:
  Perfectly Secure Message Transmission. 17-47
  
• John D. Hobby:
  Generating Automatically Tuned Bitmaps from Outlines. 48-94
  
• Leonard Pitt, Manfred K. Warmuth:
  The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial. 95-142
  
• Robert Harper, Furio Honsell, Gordon D. Plotkin:
  A Framework for Defining Logics. 143-184
  
• Dana Angluin, Lisa Hellerstein, Marek Karpinski:
  Learning Read-Once Formulas with Queries. 185-210
  

Volume 40, Number 2, April 1993

• Nader H. Bshouty:
  On the Complexity of Functions for Random Access Machines. 211-223
  
• Andrea S. LaPaugh:
  Recontamination Does Not Help to Search a Graph. 224-245
  
• David A. McAllester, Robert Givan:
  Taxonomic Syntax for First Order Inference. 246-283
  
• David A. McAllester:
  Automatic Recognition of Tractability in Inference Relations. 284-303
  
• David M. Nicol:
  The Cost of Conservative Synchronization in Parallel Discrete Event Simulations. 304-333
  
• Gil Neiger, Sam Toueg:
  Simulating Synchronized Clocks and Common Knowledge in Distributed Systems. 334-367
  
• Thomas Lengauer, Egon Wanke:
  Efficient Decision Procedures for Graph Properties on Centext-Free Graph Languages. 368-393
  
• Kin K. Leung:
  An Execution/Sleep Scheduling Policy for Serving an Additional Job in Priority Queueing Systems. 394-417
  

Volume 40, Number 3, July 1993

• Don Coppersmith, Peter Doyle, Prabhakar Raghavan, Marc Snir:
  Random Walks on Weighted Graphs and Applications to On-line Algorithms. 421-453
  
• Howard J. Karloff, Prabhakar Raghavan:
  Randomized Algorithms and Pseudorandom Numbers. 454-476
  
• Franz Baader:
  Unification in Commutative Theories, Hilbert's Basis Theorem, and Gröbner Bases. 477-503
  
• Neil V. Murray, Erik Rosenthal:
  Dissolution: Making Paths Vanish. 504-535
  
• C. A. Johnson:
  Factorization and Circuit in the Connection Method. 536-557
  
• Tie-Cheng Wang:
  Z-Module Reasoning: An Equality-Oriented Proving Method with Built-in Ring Axioms. 558-606
• Nathan Linial, Yishay Mansour, Noam Nisan:
  Constant Depth Circuits, Fourier Transform, and Learnability. 607-620
  
• Kurt Mehlhorn, Athanasios K. Tsakalidis:
  Dynamic Interpolation Search. 621-634
  
• Marc J. van Kreveld, Mark H. Overmars:
  Union-Copy Structures and Dynamic Segment Trees. 635-652
  
• Jos C. M. Baeten, Jan A. Bergstra, Jan Willem Klop:
  Decidability of Bisimulation Equivalence for Processes Generating Context-Free Languages. 653-682
  
• Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi:
  Undecidable Optimization Problems for Database Logic Programs. 683-713
  
• Randolph D. Nelson, Donald F. Towsley:
  A Performance Evaluation of Several Priority Policies for Parallel Processing Systems. 714-740
  
• Sandeep N. Bhatt, Jin-yi Cai:
  Taking Random Walks to Grow Trees in Hypercubes. 741-764
  
• Richard M. Karp, Yanjun Zhang:
  Randomized Parallel Algorithms for Backtrack Search and Branch-and-Bound Computation. 765-789
  

Volume 40, Number 4, September 1993

• Edith Cohen, Nimrod Megiddo:
  Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Periodic Graphs. 791-830
  
• Philip S. Yu, Daniel M. Dias, Stephen S. Lavenberg:
  On the Analytical Modeling of Database Concurrency Control. 831-872
  
• Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, Nir Shavit:
  Atomic Snapshots of Shared Memory. 873-890
  
• Foto N. Afrati, Christos H. Papadimitriou:
  The Parallel Complexity of Simple Logic Programs. 891-916
  
• Joseph Y. Halpern, Mark R. Tuttle:
  Knowledge, Probability, and Adversaries. 917-962
  
• V. Wiktor Marek, Grigori F. Shvarts, Miroslaw Truszczynski:
  Modal Nonmonotonic Logics: Ranges, Characterization, Computation. 963-990
  

Volume 40, Number 5, November 1993

• Edward G. Coffman Jr., M. R. Garey:
  Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling. 991-1018
  
• Zhi-Quan Luo, John N. Tsitsiklis:
  On the Communication Complexity of Distributed Algebraic Computation. 1019-1047
  
• Bruce Randall Donald, Patrick G. Xavier, John F. Canny, John H. Reif:
  Kinodynamic Motion Planning. 1048-1066
  
• Y. C. Tay:
  On the Optimality of Strategies for Multiple Joins. 1067-1086
  
• Alan Fekete, Nancy A. Lynch, Yishay Mansour, John Spinelli:
  The Impossibility of Implementing Reliable Communication in the Face of Crashes. 1087-1107
  
• Martin Charles Golumbic, Ron Shamir:
  Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach. 1108-1133
  
• Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, Detlef Seese:
  An Algebraic Theory of Graph Reduction. 1134-1164
  
• Jean Fonlupt, Armand Nachef:
  Dynamic Programming and the Graphical Traveling Salesman Problem. 1165-1187
  
• Alain Jean-Marie, Levent Gün:
  Parallel Queues with Resequencing. 1188-1208
  
• François Baccelli, Zhen Liu, Donald F. Towsley:
  Extremal Scheduling of Parallel Processing with and without Real-Time Constraints. 1209-1237
  
• Charles Knessl:
  On the Sojourn Time Distribution in a Finite Capacity Processor Shared Queue. 1238-1301