Journal of the ACM, Volume 39, 1992

Volume 39, Number 1, January 1992

• Bernard Chazelle, Herbert Edelsbrunner:
  An Optimal Algorithm for Intersecting Line Segments in the Plane. 1-54
  Electronic Edition (ACM DL) BibTeX
• Eli Upfal:
  An O(log(N)) Deterministic Packet-Routing Scheme. 55-70
  Electronic Edition (ACM DL) BibTeX
• Robert Demolombe:
  Syntactical Characterization of a Subset of Domain-Independent Formulas. 71-94
  Electronic Edition (ACM DL) BibTeX
• Joseph A. Goguen, Rod M. Burstall:
  Institutions: Abstract Model Theory for Specification and Programming. 95-146
  Electronic Edition (ACM DL) BibTeX
• Luca Aceto, Matthew Hennessy:
  Termination, Deadlock, and Divergence. 147-187
  Electronic Edition (ACM DL) BibTeX
• Lawrence W. Dowdy, Brian M. Carlson, Alan T. Krantz, Satish K. Tripathi:
  Single-Class Bounds of Multi-Class Queuing Networks. 188-213
  Electronic Edition (ACM DL) BibTeX
• Mihir Bellare, Silvio Micali:
  How to Sign Given Any Trapdoor Permutation. 214-233
  Electronic Edition (ACM DL) BibTeX
• Eric Allender, Lane A. Hemachandra:
  Lower Bounds for the Low Hierarchy. 234-251
  Electronic Edition (ACM DL) BibTeX

Volume 39, Number 2, April 1992

• Michael B. Dillencourt, Hanan Samet, Markku Tamminen:
  A General Approach to Connected-Component Labelling for Arbitrary Image Representations. 253-280
  Electronic Edition (ACM DL) BibTeX
• Jyrki Katajainen, Timo Raita:
  An Analysis of the Longest Match and the Greedy Heuristics in Text Encoding. 281-294
  Electronic Edition (ACM DL) BibTeX
• R. Ramesh, I. V. Ramakrishnan:
  Nonlinear Pattern Matching in Trees. 295-316
  Electronic Edition (ACM DL) BibTeX
• Renzo Sprugnoli:
  The Generation of Binary Trees as a Numerical Problem. 317-327
  Electronic Edition (ACM DL) BibTeX
• Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi:
  What Can Machines Know? On the Properties of Knowledge in Distributed Systems. 328-376
  Electronic Edition (ACM DL) BibTeX
• Jean H. Gallier, Paliath Narendran, Stan Raatz, Wayne Snyder:
  Theorem Proving Using Equational Matings and Rigid E-Unification. 377-429
  Electronic Edition (ACM DL) BibTeX
• Eugene W. Myers:
  A Four Russians Algorithm for Regular Expression Pattern Matching. 430-448
  Electronic Edition (ACM DL) BibTeX

Volume 39, Number 3, July 1992

• Joseph Y. Halpern, Lenore D. Zuck:
  A Little Knowledge Goes a Long Way: Knowledge-Based Derivations and Correctness Proofs for a Family of Protocols. 449-478
  Electronic Edition (ACM DL) BibTeX
• Lenwood S. Heath, Sorin Istrail:
  The Pagenumber of Genus g Graphs is O(g). 479-501
  Electronic Edition (ACM DL) BibTeX
• Alain Billionnet, Marie-Christine Costa, Alain Sutter:
  An Efficient Algorithm for a Task Allocation Problem. 502-518
  Electronic Edition (ACM DL) BibTeX
• David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano:
  Sparse Dynamic Programming I: Linear Cost Functions. 519-545
  Electronic Edition (ACM DL) BibTeX
• David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano:
  Sparse Dynamic Programming II: Convex and Concave Cost Functions. 546-567
  Electronic Edition (ACM DL) BibTeX
• Albert G. Greenberg, Neal Madras:
  How Fair is Fair Queuing? 568-598
  Electronic Edition (ACM DL) BibTeX
• Martin Beaudry, Pierre McKenzie, Denis Thérien:
  The Membership Problem in Aperiodic Transformation Monoids. 599-616
  Electronic Edition (ACM DL) BibTeX
• Amir M. Ben-Amram, Zvi Galil:
  On Pointers versus Addresses. 617-648
  Electronic Edition (ACM DL) BibTeX
• William I. Gasarch, Carl H. Smith:
  Learning via Queries. 649-674
  Electronic Edition (ACM DL) BibTeX
• Steven M. German, A. Prasad Sistla:
  Reasoning about Systems with Many Processes. 675-735
  Electronic Edition (ACM DL) BibTeX
• Ran Raz, Avi Wigderson:
  Monotone Circuits for Matching Require Linear Depth. 736-744
  Electronic Edition (ACM DL) BibTeX

Volume 39, Number 4, October 1992

• Allan Borodin, Nathan Linial, Michael E. Saks:
  An Optimal On-Line Algorithm for Metrical Task System. 745-763
  Electronic Edition (ACM DL) BibTeX
• Amos Fiat, Moni Naor, Jeanette P. Schmidt, Alan Siegel:
  Nonoblivious Hashing. 764-782
  Electronic Edition (ACM DL) BibTeX
• Yishay Mansour, Baruch Schieber:
  The Intractability of Bounded Protocols for On-Line Sequence Transmission over Non-FIFO Channels. 783-799
  Electronic Edition (ACM DL) BibTeX
• Cynthia Dwork, Larry J. Stockmeyer:
  Finite State Verifiers I: The Power of Interaction. 800-828
  Electronic Edition (ACM DL) BibTeX
• Cynthia Dwork, Larry J. Stockmeyer:
  Finite State Verifiers II: Zero Knowledge. 829-858
  Electronic Edition (ACM DL) BibTeX
• Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan:
  Algebraic Methods for Interactive Proof Systems. 859-868
  Electronic Edition (ACM DL) BibTeX
• Adi Shamir:
  IP = PSPACE. 869-877
  Electronic Edition (ACM DL) BibTeX
• A. Shen:
  IP = PSPACE: Simplified Proof. 878-880
  Electronic Edition (ACM DL) BibTeX
• Maurice Herlihy, Nancy A. Lynch, Michael Merritt, William E. Weihl:
  On the Correctness of Orphan Management Algorithms. 881-930
  Electronic Edition (ACM DL) BibTeX
• Oliver Collins, Sam Dolinar, Robert J. McEliece, Fabrizio Pollara:
  A VLSI Decomposition of the deBruijn Graph. 931-948
  Electronic Edition (ACM DL) BibTeX
• Saumya K. Debray:
  Efficient Dataflow Analysis of Logic Programs. 949-984
  Electronic Edition (ACM DL) BibTeX
• Michael B. Dillencourt, Hanan Samet, Markku Tamminen: Corrigenda: 'A General Approach to Connected-Component Labelling for Arbitrary Image Representations'. 985-986 BibTeX