Journal of the ACM -- 1992

Volume 39, Number 1, January 1992

• Bernard Chazelle and Herbert Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM, 39(1):1-54, January 1992. References and Citations. [BibTeX entry]

• Eli Upfal. An O(log N) deterministic packet-routing scheme. Journal of the ACM, 39(1):55-70, January 1992. References and Citations. [BibTeX entry]

• Robert Demolombe. Syntactical characterization of a subset of domain-independent formulas. Journal of the ACM, 39(1):71-94, January 1992. References and Citations. [BibTeX entry]

• Joseph A. Goguen and Rod M. Burstall. Institutions: Abstract model theory for specification and programming. Journal of the ACM, 39(1):95-146, January 1992. References and Citations. [BibTeX entry]

• L. Aceto and M. Hennessy. Termination, deadlock, and divergence. Journal of the ACM, 39(1):147-187, January 1992. References and Citations. [BibTeX entry]

• Lawrence W. Dowdy, Brian M. Carlson, Alan T. Krantz, and Satish K. Tripathi. Single-class bounds of multi-class queuing networks. Journal of the ACM, 39(1):188-213, January 1992. References and Citations. [BibTeX entry]

• Mihir Bellare and Silvio Micali. How to sign given any trapdoor permutation. Journal of the ACM, 39(1):214-233, January 1992. References and Citations. [BibTeX entry]

• Eric Allender and Lane A. Hemachandra. Lower bounds for the low hierarchy. Journal of the ACM, 39(1):234-251, January 1992. References and Citations. [BibTeX entry]

Volume 39, Number 2, April 1992

• Michael B. Dillencourt, Hannan Samet, and Markku Tamminen. A general approach to connected-component labeling for arbitrary image representations. Journal of the ACM, 39(2):253-280, April 1992. References and Citations. [BibTeX entry]

• Jyrki Katajainen and Timo Raita. An analysis of the longest match and the greedy heuristics in text encoding. Journal of the ACM, 39(2):281-294, April 1992. References and Citations. [BibTeX entry]

• R. Ramesh and I. V. Ramakrishnan. Nonlinear pattern matching in trees. Journal of the ACM, 39(2):295-316, April 1992. References and Citations. [BibTeX entry]

• Renzo Sprugnoli. The generation of binary trees as a numerical problem. Journal of the ACM, 39(2):317-327, April 1992. References. [BibTeX entry]

• Ronald Fagin, Joseph Y. Halpern, and Moshe Y. Vardi. What can machines know? on the properties of knowledge in distributed systems. Journal of the ACM, 39(2):328-376, April 1992. References and Citations. [BibTeX entry]

• Jean Gallier, Paliath Narendran, Stan Raatz, and Wayne Snyder. Theorem proving using equational matings and rigid E-unification. Journal of the ACM, 39(2):377-429, April 1992. References and Citations. [BibTeX entry]

• Gene Myers. A four Russians algorithm for regular expression pattern matching. Journal of the ACM, 39(2):430-448, April 1992. References and Citations. [BibTeX entry]

Volume 39, Number 3, July 1992

• Joseph Y. Halpern and Lenore D. Zuck. A little knowledge goes a long way: Knowledge-based derivations and correctness proofs for a family of protocols. Journal of the ACM, 39(3):449-478, July 1992. References and Citations. [BibTeX entry]

• Lenwood S. Heath and Sorin Istrail. The pagenumber of genus g graphs is O(g). Journal of the ACM, 39(3):479-501, July 1992. References. [BibTeX entry]

• A. Billionnet, M. C. Costa, and A. Sutter. An efficient algorithm for a task allocation problem. Journal of the ACM, 39(3):502-518, July 1992. Citations. [BibTeX entry]

• David Eppstein, Zvi Galil, Faffaele Giancarlo, and Giuseppe F. Italiano. Sparse dynamic programming I: Linear cost functions. Journal of the ACM, 39(3):519-545, July 1992. References and Citations. [BibTeX entry]

• David Eppstein, Zvi Galil, Faffaele Giancarlo, and Giuseppe F. Italiano. Sparse dynamic programming II: Convex and concave cost functions. Journal of the ACM, 39(3):546-567, July 1992. References and Citations. [BibTeX entry]

• Albert G. Greenberg and Neal Madras. How fair is fair queuing? Journal of the ACM, 39(3):568-598, July 1992. Citations. [BibTeX entry]

• M. Beaudry, P. McKenzie, and D. Thérien. The membership problem in aperiodic transformation monoids. Journal of the ACM, 39(3):599-616, July 1992. References and Citations. [BibTeX entry]

• Amir M. Ben-Amram and Zvi Galil. On pointers versus addresses. Journal of the ACM, 39(3):617-648, July 1992. References and Citations. [BibTeX entry]

• William I. Gasarch and Carl H. Smith. Learning via queries. Journal of the ACM, 39(3):649-674, July 1992. References and Citations. [BibTeX entry]

• Steven M. German and A. Prasad Sistla. Reasoning about systems with many processes. Journal of the ACM, 39(3):675-735, July 1992. References and Citations. [BibTeX entry]

• Ran Raz and Avi Wigderson. Monotone circuits for matching require linear depth. Journal of the ACM, 39(3):736-744, July 1992. References and Citations. [BibTeX entry]

Volume 39, Number 4, October 1992

• Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line algorithm for metrical task system. Journal of the ACM, 39(4):745-763, October 1992. References and Citations. [BibTeX entry]

• Amos Fiat, Moni Naor, Jeanette P. Schmidt, and Alan Siegel. Nonoblivious hashing. Journal of the ACM, 39(4):764-782, October 1992. References and Citations. [BibTeX entry]

• Yishay Mansour and Baruch Schieber. The intractability of bounded protocols for on-line sequence transmission over non-FIFO channels. Journal of the ACM, 39(4):783-799, October 1992. References and Citations. [BibTeX entry]

• Cynthia Dwork and Larry Stockmeyer. Finite state verifiers I: The power of interaction. Journal of the ACM, 39(4):800-828, October 1992. References and Citations. [BibTeX entry]

• Cynthia Dwork and Larry Stockmeyer. Finite state verifiers II: Zero knowledge. Journal of the ACM, 39(4):829-858, October 1992. References and Citations. [BibTeX entry]

• Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, October 1992. References and Citations. [BibTeX entry]

• Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, October 1992. References, Citations, etc. [BibTeX entry]

• A. Shen. IP = PSPACE: Simplified proof. Journal of the ACM, 39(4):878-880, October 1992. References and Citations. [BibTeX entry]

• Maurice Herlihy, Nancy Lynch, Michael Merritt, and William Weihl. On the correctness of orphan management algorithms. Journal of the ACM, 39(4):881-930, October 1992. [BibTeX entry]

• Oliver Collins, Sam Dolinar, Robert McEliece, and Fabrizio Pollara. A VLSI decomposition of the deBruijn graph. Journal of the ACM, 39(4):931-948, October 1992. References. [BibTeX entry]

• Saumya K. Debray. Efficient dataflow analysis of logic programs. Journal of the ACM, 39(4):949-984, October 1992. Citations. [BibTeX entry]

• M. B. Dillencourt, H. Samet, and M. Tamminen. Corrigenda: ``A general approach to connected component labeling for arbitrary image representations''. Journal of the ACM, 39(4):985-986, October 1992. References and Citations. [BibTeX entry]

Shortcuts: