Journal of the ACM -- 1989

Volume 36, Number 1, January 1989

• John H. Muller and Jeremy Spinrad. Incremental modular decomposition. Journal of the ACM, 36(1):1-19, January 1989. Citations. [BibTeX entry]

• J. A. Brzozowski and C-J. Seger. A unified framework for race analysis of asynchronous networks. Journal of the ACM, 36(1):20-45, January 1989. [BibTeX entry]

• William W. McCune and Lawrence J. Henschen. Maintaining state constraints in relational databases: A proof theoretic basis. Journal of the ACM, 36(1):46-68, January 1989. Citations. [BibTeX entry]

• Jeffrey F. Naughton. Minimizing function-free recursive inference rules. Journal of the ACM, 36(1):69-91, January 1989. Citations. [BibTeX entry]

• Jens M. Dill. A counterexample for ``A simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars''. Journal of the ACM, 36(1):92-96, January 1989. References. [BibTeX entry]

• Paul Helman. A common schema for dynamic programming and branch and bound algorithms. Journal of the ACM, 36(1):97-128, January 1989. Citations. [BibTeX entry]

• Joan Boyar. Inferring sequences produced by pseudo-random number generators. Journal of the ACM, 36(1):129-141, January 1989. Citations. [BibTeX entry]

• Michael Kaminski. A note on probabilistically verifying integer and polynomial products. Journal of the ACM, 36(1):142-149, January 1989. [BibTeX entry]

• Michael Kaminski and Nader H. Bshouty. Multiplicative complexity of polynomial multiplication over finite fields. Journal of the ACM, 36(1):150-170, January 1989. [BibTeX entry]

• Edmundo de Souza e Silva and H. Richard Gail. Calculating availability and performability measures of repairable computer systems using randomization. Journal of the ACM, 36(1):171-193, January 1989. Citations. [BibTeX entry]

• Edmundo de Souza e Silva and S. S. Lavenberg. Calculating joint queue-length distributions in product-form queuing networks. Journal of the ACM, 36(1):194-207, January 1989. Citations. [BibTeX entry]

Volume 36, Number 2, April 1989

• John D. Hobby. Rasterizing curves of constant width. Journal of the ACM, 36(2):209-229, April 1989. [BibTeX entry]

• Catriel Beeri, Philip A. Bernstein, and Nathan Goodman. A model for concurrency in nested transactions systems. Journal of the ACM, 36(2):230-269, April 1989. Citations. [BibTeX entry]

• Walter Cunto and J. Ian Munro. Average case selection. Journal of the ACM, 36(2):270-279, April 1989. Citations. [BibTeX entry]

• Rolf Klein and Derick Wood. On the path length of binary trees. Journal of the ACM, 36(2):280-289, April 1989. Citations. [BibTeX entry]

• G. K. Manacher, T. D. Bui, and T. Mai. Optimum combinations of sorting and merging. Journal of the ACM, 36(2):290-334, April 1989. Citations. [BibTeX entry]

• Michael O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM, 36(2):335-348, April 1989. Citations. [BibTeX entry]

• Arnon Rosenthal and José A. Pino. A generalized algorithm for centrality problems on trees. Journal of the ACM, 36(2):349-361, April 1989. [BibTeX entry]

• G. Bilardi and F. P. Preparata. Size-time complexity of Boolean networks for prefix computations. Journal of the ACM, 36(2):362-382, April 1989. Citations. [BibTeX entry]

• L. Pitt. Probabilistic inductive inference. Journal of the ACM, 36(2):383-433, April 1989. Citations. [BibTeX entry]

Volume 36, Number 3, July 1989

• Csaba P. Gabor, Kenneth J. Supowit, and Wen-Lian Hsu. Recognizing circle graphs in polynomial time. Journal of the ACM, 36(3):435-473, July 1989. Citations. [BibTeX entry]

• Thomas Lengauer. Hierarchical planarity testing algorithms. Journal of the ACM, 36(3):474-509, July 1989. Citations. [BibTeX entry]

• David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36(3):510-530, July 1989. Citations. [BibTeX entry]

• Nicholas Pippenger. Invariance of complexity measures for networks with unreliable gates. Journal of the ACM, 36(3):531-539, July 1989. Citations. [BibTeX entry]

• Harold N. Gabow, Zvi Galil, and Thomas H. Spencer. Efficient implementation of graph algorithms using contraction. Journal of the ACM, 36(3):540-572, July 1989. Citations. [BibTeX entry]

• Sanjiv Kapoor and Edward M. Reingold. Optimum lopsided binary trees. Journal of the ACM, 36(3):573-590, July 1989. Citations. [BibTeX entry]

• Benny Chor, Michael Merritt, and David B. Shmoys. Simple constant-time consensus protocols in realistic failure models. Journal of the ACM, 36(3):591-614, July 1989. Citations. [BibTeX entry]

• François Baccelli, William A. Massey, and Don Towsley. Acyclic fork-join queuing networks. Journal of the ACM, 36(3):615-642, July 1989. Citations. [BibTeX entry]

• Paul Beame and Johan Hastad. Optimal bounds for decision problems on the CRCW PRAM. Journal of the ACM, 36(3):643-670, July 1989. Citations. [BibTeX entry]

• Ming Li and Yaacov Yesha. New lower bounds for parallel computation. Journal of the ACM, 36(3):671-680, July 1989. Citations. [BibTeX entry]

Volume 36, Number 4, October 1989

• Thomas Dean. Using temporal hierarchies to efficiently maintain large temporal databases. Journal of the ACM, 36(4):687-718, October 1989. [BibTeX entry]

• Loren K. Platzman and John J. Bartholdi, III. Spacefilling curves and the planar travelling salesman problem. Journal of the ACM, 36(4):719-737, October 1989. Citations. [BibTeX entry]

• Martin Dowd, Yehoshua Perl, Larry Rudolph, and Michael Saks. The periodic balanced sorting network. Journal of the ACM, 36(4):738-757, October 1989. Citations. [BibTeX entry]

• Serge Abiteboul and Victor Vianu. A transaction-based approach to relational database specification. Journal of the ACM, 36(4):758-789, October 1989. Citations. [BibTeX entry]

• Marc Gyssens, Jan Paredaens, and Dirk Van Gucht. A uniform approach toward handling atomic and structured information in the nested relational database model. Journal of the ACM, 36(4):790-825, October 1989. Citations. [BibTeX entry]

• Jan L. A. van de Snepscheut and Johan B. Swenker. On the design of some systolic algorithms. Journal of the ACM, 36(4):826-840, October 1989. Citations. [BibTeX entry]

• Joost Engelfriet and Gilberto Filé. Passes, sweeps, and visits in attribute grammars. Journal of the ACM, 36(4):841-869, October 1989. Citations. [BibTeX entry]

• Juha Kortelainen. The conjecture of Fliess on commutative context-free languages. Journal of the ACM, 36(4):870-872, October 1989. Citations. [BibTeX entry]

• Andrew V. Goldberg and Robert E. Tarjan. Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM, 36(4):873-886, October 1989. Citations. [BibTeX entry]

• Ilaria Castellani and Matthew Hennessy. Distributed bisimulations. Journal of the ACM, 36(4):887-911, October 1989. Citations. [BibTeX entry]

• Eric W. Allender. P-uniform circuit complexity. Journal of the ACM, 36(4):912-928, October 1989. Citations. [BibTeX entry]

• Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929-965, October 1989. Citations. [BibTeX entry]

Shortcuts: