Journal of the ACM, Volume 41, 1994

Volume 41, Number 1, January 1994

• Michael J. Fischer, Mike Paterson:
  Fishspear: A Priority Queue Algorithm. 3-30
  
• Daniel N. Rockmore:
  Efficient Computation of Fourier Inversion for Finite Groups. 31-66
  
• Michael J. Kearns, Leslie G. Valiant:
  Cryptographic Limitations on Learning Boolean Formulae and Finite Automata. 67-95
  
• Pekka Orponen, Ker-I Ko, Uwe Schöning, Osamu Watanabe:
  Instance Complexity. 96-121
  
• Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer:
  Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty. 122-152
  
• Brenda S. Baker:
  Approximation Algorithms for NP-Complete Problems on Planar Graphs. 153-180
  
• Rajeev Alur, Thomas A. Henzinger:
  A Really Temporal Logic. 181-204
  

Volume 41, Number 2, March 1994

• Moshe Dubiner, Zvi Galil, Edith Magen:
  Faster Tree Pattern Matching. 205-213
  
• Samir Khuller, Uzi Vishkin:
  Biconnectivity Approximations and Graph Carvings. 214-235
  
• Leo Bachmair, Nachum Dershowitz:
  Equational Inference, Canonical Proofs, and Proof Orderings. 236-276
  
• Karl R. Abrahamson, Andrew Adler, Lisa Higham, David G. Kirkpatrick:
  Tight Lower Bounds for Probabilistic Solitude Verification on Anonymous Rings. 277-310
  
• Ambuj K. Singh, James H. Anderson, Mohamed G. Gouda:
  The Elusive Atomic Register. 311-339
  
• Ronald Fagin, Joseph Y. Halpern:
  Reasoning About Knowledge and Probability. 340-367
  , Corrigendum: JACM 45(1): 214 (1998)
• A. J. Kfoury, Jerzy Tiuryn, Pawel Urzyczyn:
  An Analysis of ML Typability. 368-398
  
• Michel Cosnard, El Mostafa Daoudi:
  Optimal Algorithms for Parallel Givens Factorization on a Coarse-Grained PRAM. 399-421
  
• Noga Alon, Nimrod Megiddo:
  Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time. 422-434
  

Volume 41, Number 3, May 1994

• Peter B. Ladkin, Roger D. Maddux:
  On Binary Constraint Problems. 435-469
  
• Avrim Blum:
  New Approximation Algorithms for Graph Coloring. 470-516
  
• Doron Drusinsky, David Harel:
  On the Power of Bounded Concurrency I: Finite Automata. 517-539
  
• Tirza Hirst, David Harel:
  On the Power of Bounded Concurrency II: Pushdown Automata. 540-554
  
• Ronald L. Rivest, Robert E. Schapire:
  Diversity-Based Inference of Finite Automata. 555-589
  

Volume 41, Number 4, July 1994

• Wray L. Buntine, Hans-Jürgen Bürckert:
  On Solving Equations and Disequations. 591-629
  
• Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis:
  Linear Approximation of Shortest Superstrings. 630-647
  
• Adrian E. Conway, Eugene Pinsky, Srinivasan Tridandapani:
  Efficient Decomposition Methods for the Analysis of Multi-Facility Blocking Models. 648-675
  
• John C. S. Lui, Richard R. Muntz:
  Computing Bounds on Steady State Availability of Repairable Computer Systems. 676-707
  
• Timothy C. Bell, Ian H. Witten:
  The Relationship between Greedy Parsing and Symbolwise Text Compression. 708-724
  
• Hagit Attiya, Nancy A. Lynch, Nir Shavit:
  Are Wait-Free Algorithms Fast? 725-763
  
• John H. Reif, Micha Sharir:
  Motion Planning in the Presence of Moving Obstacles. 764-790
  
• Shaodi Gao, Michael Kaufmann:
  Channel Routing of Multiterminal Nets. 791-818
  

Volume 41, Number 5, September 1994

• Peter K. Rathmann, Marianne Winslett, Mark S. Manasse:
  Circumscription with Homomorphisms: Solving the Equality and Counterexample Problems. 819-873
  
• Christopher J. Glass, Lionel M. Ni:
  The Turn Model for Adaptive Routing. 874-902
  
• Yves Dallery, Zhen Liu, Donald F. Towsley:
  Equivalence, Reversibility, Symmetry and Concavity Properties in Fork-Join Queueing Networks with Blocking. 903-942
  
• James R. Driscoll, Daniel Dominic Sleator, Robert Endre Tarjan:
  Fully Persistent Lists with Catenation. 943-959
  
• Carsten Lund, Mihalis Yannakakis:
  On the Hardness of Approximating Minimization Problems. 960-981
  
• James A. Storer, John H. Reif:
  Shortest Paths in the Plane with Polygonal Obstacles. 982-1012
  
• John H. Reif, James A. Storer:
  A Single-Exponential Upper Bound for Finding Shortest Paths in Three Dimensions. 1013-1019
  
• James Aspnes, Maurice Herlihy, Nir Shavit:
  Counting Networks. 1020-1048
  

Volume 41, Number 6, November 1994

• Mikhail J. Atallah, Michael T. Goodrich, S. Rao Kosaraju:
  Parallel Algorithms for Evaluating Sequences of Set-Manipulation Operations. 1049-1088
  
• Tal Rabin:
  Robust Sharing of Secrets When the Dealer is Honest or Cheating. 1089-1109
  
• Keith W. Ross, Danny H. K. Tsang, Jie Wang:
  Monte Carlo Summation and Integration Applied to Multiclass Queuing Networks. 1110-1135
  
• Richard M. Karp:
  Probabilistic Recurrence Relations. 1136-1150
  
• Jeffrey F. Naughton, Raghu Ramakrishnan:
  How to Forget the Past Without Repeating It. 1151-1177
  
• Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian:
  Mixed Integer Programming Methods for Computing Nonmonotonic Deductive Databases. 1178-1215
  
• Kenneth A. Ross:
  Modular Stratification and Magic Sets for Datalog Programs with Negation. 1216-1266
  
• Yehuda Afek, Hagit Attiya, Alan Fekete, Michael J. Fischer, Nancy A. Lynch, Yishay Mansour, Da-Wei Wang, Lenore D. Zuck:
  Reliable Communication Over Unreliable Channels. 1267-1297
  
• Michael J. Kearns, Ming Li, Leslie G. Valiant:
  Learning Boolean Formulas. 1298-1328
  
• Rajeev Motwani:
  Average-Case Analysis of Algorithms for Matchings and Related Problems. 1329-1356