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
Eli Upfal:
An O(log(N)) Deterministic Packet-Routing Scheme. 55-70
Robert Demolombe:
Syntactical Characterization of a Subset of Domain-Independent Formulas. 71-94
Joseph A. Goguen, Rod M. Burstall:
Institutions: Abstract Model Theory for Specification and Programming. 95-146
Luca Aceto, Matthew Hennessy:
Termination, Deadlock, and Divergence. 147-187
Lawrence W. Dowdy, Brian M. Carlson, Alan T. Krantz, Satish K. Tripathi:
Single-Class Bounds of Multi-Class Queuing Networks. 188-213
Mihir Bellare, Silvio Micali:
How to Sign Given Any Trapdoor Permutation. 214-233
Eric Allender, Lane A. Hemachandra:
Lower Bounds for the Low Hierarchy. 234-251

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

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

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