Journal of the ACM, Volume 36, 1989

Volume 36, Number 1, January 1989

• John H. Muller, Jeremy Spinrad:
  Incremental modular decomposition. 1-19
  
• Janusz A. Brzozowski, Carl-Johan H. Seger:
  A unified framework for race analysis of asynchronous networks. 20-45
  
• William McCune, Lawrence J. Henschen:
  Maintaining state constraints in relational databases: a proof theoretic basis. 46-68
  
• Jeffrey F. Naughton:
  Minimizing function-free recursive inference rules. 69-91
  
• Jens M. Dill:
  A counter-example for ``A simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars''. 92-96
  
• Paul Helman:
  A common schema for dynamic programming and branch and bound algorithms. 97-128
  
• Joan Boyar:
  Inferring sequences produced by pseudo-random number generators. 129-141
  
• Michael Kaminski:
  A note on probabilistically verifying integer and polynomial products. 142-149
  
• Michael Kaminski, Nader H. Bshouty:
  Multiplicative complexity of polynomial multiplication over finite fields. 150-170
  
• Edmundo de Souza e Silva, H. Richard Gail:
  Calculating availability and performability measures of repairable computer systems using randomization. 171-193
  
• Edmundo de Souza e Silva, Stephen S. Lavenberg:
  Calculating joint queue-length distributions in product-form queuing networks. 194-207
  

Volume 36, Number 2, April 1989

• John D. Hobby:
  Rasterizing curves of constant width. 209-229
  
• Catriel Beeri, Philip A. Bernstein, Nathan Goodman:
  A model for concurrency in nested transactions systems. 230-269
  
• Walter Cunto, J. Ian Munro:
  Average case selection. 270-279
  
• Rolf Klein, Derick Wood:
  On the path length of binary trees. 280-289
  
• Glenn K. Manacher, T. D. Bui, T. Mai:
  Optimum combinations of sorting and merging. 290-334
  
• Michael O. Rabin:
  Efficient dispersal of information for security, load balancing, and fault tolerance. 335-348
  
• Arnon Rosenthal, José A. Pino:
  A generalized algorithm for centrality problems on trees. 349-361
  
• Gianfranco Bilardi, Franco P. Preparata:
  Size-time complexity of Boolean networks for prefix computations. 362-382
  
• Leonard Pitt:
  Probabilistic inductive inference. 383-433
  

Volume 36, Number 3, July 1989

• Csaba P. Gabor, Kenneth J. Supowit, Wen-Lian Hsu:
  Recognizing circle graphs in polynomial time. 435-473
  
• Thomas Lengauer:
  Hierarchical planarity testing algorithms. 474-509
  
• David Peleg, Eli Upfal:
  A trade-off between space and efficiency for routing tables. 510-530
  
• Nicholas Pippenger:
  Invariance of complexity measures for networks with unreliable gates. 531-539
  
• Harold N. Gabow, Zvi Galil, Thomas H. Spencer:
  Efficient implementation of graph algorithms using contraction. 540-572
  
• Sanjiv Kapoor, Edward M. Reingold:
  Optimum lopsided binary trees. 573-590
  
• Benny Chor, Michael Merritt, David B. Shmoys:
  Simple constant-time consensus protocols in realistic failure models. 591-614
  
• François Baccelli, William A. Massey, Donald F. Towsley:
  Acyclic fork-join queuing networks. 615-642
  
• Paul Beame, Johan Håstad:
  Optimal bounds for decision problems on the CRCW PRAM. 643-670
  
• Ming Li, Yaacov Yesha:
  New lower bounds for parallel computation. 671-680
  

Volume 36, Number 4, October 1989

• Thomas Dean:
  Using temporal hierarchies to efficiently maintain large temporal databases. 687-718
  
• Loren K. Platzman, John J. Bartholdi III:
  Spacefilling curves and the planar travelling salesman problem. 719-737
  
• Martin Dowd, Yehoshua Perl, Larry Rudolph, Michael E. Saks:
  The periodic balanced sorting network. 738-757
  
• Serge Abiteboul, Victor Vianu:
  A transaction-based approach to relational database specification. 758-789
  
• Marc Gyssens, Jan Paredaens, Dirk Van Gucht:
  A uniform approach toward handling atomic and structured information in the nested relational database model. 790-825
  
• Jan L. A. van de Snepscheut, Johan B. Swenker:
  On the design of some systolic algorithms. 826-840
  
• Joost Engelfriet, Gilberto Filé:
  Passes, sweeps, and visits in attribute grammars. 841-869
  
• Juha Kortelainen:
  The conjecture of Fliess on commutative context-free languages. 870-872
  
• Andrew V. Goldberg, Robert Endre Tarjan:
  Finding minimum-cost circulations by canceling negative cycles. 873-886
  
• Ilaria Castellani, Matthew Hennessy:
  Distributed bisimulations. 887-911
  
• Eric Allender:
  P-uniform circuit complexity. 912-928
  
• Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth:
  Learnability and the Vapnik-Chervonenkis dimension. 929-965