Journal of the ACM, Volume 28, 1981

Volume 28, Number 1, January 1981

• Shimon Even, Yossi Shiloach:
  An On-Line Edge-Deletion Problem. 1-4
  
• Yehoshua Perl, Stephen R. Schach:
  Max-Min Tree Partitioning. 5-15
  
• Michael Rodeh, Vaughan R. Pratt, Shimon Even:
  Linear Algorithm for Data Compression via String Matching. 16-24
  
• Philip A. Bernstein, Dah-Ming W. Chiu:
  Using Semi-Joins to Solve Relational Queries. 25-40
  
• Witold Lipski Jr.:
  On Databases with Incomplete Information. 41-70
  
• Grzegorz W. Wasilkowski:
  n-Evaluation Conjecture for Multipoint Iterations for the Solution of Scalar Nonlinear Equations. 71-80
  
• James O. Achugbue, Francis Y. L. Chin:
  Bounds on Schedules for Independent Tasks with Similar Execution Times. 81-99
  
• John L. Bruno, Peter J. Downey, Greg N. Frederickson:
  Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or Makespan. 100-113
  
• Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer:
  Alternation. 114-133
  
• Zvi Galil:
  String Matching in Real Time. 134-149
  
• David G. Kirkpatrick:
  A Unified Lower Bound for Selection and Set Partitioning Problems. 150-165
  
• Benton L. Leong, Joel I. Seiferas:
  New Real-Time Simulations of Multihead Tape Units. 166-180
  
• John H. Rowland, Philip J. Davis:
  On the Use of Transcendentals for Program Testing. 181-190
  

Volume 28, Number 2, April 1981

• Peter B. Andrews:
  Theorem Proving via General Mappings. 193-214
  
• Prabhaker Mateti:
  A Decision Procedure for the Correctness of a Class of Programs. 215-232
  
• Gerald E. Peterson, Mark E. Stickel:
  Complete Sets of Reductions for Some Equational Theories. 233-264
  
• C. K. Chu:
  A Note on Multiple Error Detection in ASCII Numeric Data Communication. 265-269
  
• Kishor S. Trivedi, Timothy M. Sigmon:
  Optimal Design of Linear Storage Hierarchies. 270-288
  
• Gaston H. Gonnet:
  Expected Length of the Longest Probe Sequence in Hash Code Searching. 289-304
  
• Michael Karr:
  Summation in Finite Terms. 305-350
  
• Richard M. Feldman, Gerald Wayne Adkins, Guy L. Curry, Udo W. Pooch:
  Measurement Bias in Feedback Queues. 351-357
  
• Kenneth C. Sevcik, Isi Mitrani:
  The Distribution of Queuing Network States at Input and Output Instants. 358-371
  
• Christopher J. Hogger:
  Derivation of Logic Programs. 372-392
  
• Martin Rem:
  The Closure Statement: A Programming Language Construct Allowing Ultraconcurrent Execution. 393-410
  
• Karl J. Lieberherr, Ernst Specker:
  Complexity of Partial Satisfaction. 411-421
  

Volume 28, Number 3, July 1981

• Mark E. Stickel:
  A Unification Algorithm for Associative-Commutative Functions. 423-434
  
• Yehoshua Sagiv, Claude Delobel, Douglas Stott Parker Jr., Ronald Fagin:
  An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic. 435-453
  
• David P. Dobkin, J. Ian Munro:
  Optimal Time Minimal Space Selection Algorithms. 454-461
  
• Francis Y. L. Chin, Long-Lieh Tsai:
  On J-maximal and J-minimal Flow-Shop Schedules. 462-476
  
• Leonard Kleinrock, Arne A. Nilsson:
  On Optimal Scheduling Algorithms for Time-Shared Systems. 477-486
  
• Hanan Samet:
  Connected Component Labeling Using Quadtrees. 487-501
  
• Sarangan Krishna Kumar, Melvin A. Breuer:
  Probabilistic Aspects of Boolean Switching Functions via a New Transform. 502-520
  
• Richard P. Brent, H. T. Kung:
  The Area-Time Complexity of Binary Multiplication. 521-534
  
• Eitan M. Gurari, Oscar H. Ibarra:
  The Complexity of the Equivalence Problem for Simple Programs. 535-560
  
• Ernst W. Mayr, Albert R. Meyer:
  The Complexity of the Finite Containment Problem for Petri Nets. 561-576
  
• Robert Endre Tarjan:
  A Unified Approach to Path Problems. 577-593
  
• Robert Endre Tarjan:
  Fast Algorithms for Solving Path Problems. 594-614
  
• Andrew Chi-Chih Yao:
  Should Tables Be Sorted? 615-628
  
• Martin Reiser, Stephen S. Lavenberg:
  Corrigendum: ``Mean-Value Analysis of Closed Multichain Queuing Networks''. 629
  

Volume 28, Number 4, October 1981

• Wolfgang Bibel:
  On Matrices with Connections. 633-645
  
• Donald W. Loveland, C. R. Reddy:
  Deleting Repeated Goals in the Problem Reduction Format. 646-661
  
• Guy Latouche:
  Algorithmic Analysis of a Multiprogramming-Multiprocessor Computer System. 662-679
  
• David Maier, Yehoshua Sagiv, Mihalis Yannakakis:
  On the Complexity of Testing Implications of Functional and Join Dependencies. 680-695
  
• Michael L. Fredman:
  A Lower Bound on the Complexity of Orthogonal Range Queries. 696-705
  
• Andrzej Ehrenfeucht, Grzegorz Rozenberg, Keijo Ruohonen:
  A Morphic Representation of Complements of Recursively Enumerable Sets. 706-714
  
• Mehdi Jazayeri:
  A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars. 715-720
  
• Ernest Davis, Jeffrey M. Jaffe:
  Algorithms for Scheduling Tasks on Unrelated Processors. 721-736
  
• Stefania Gnesi, Ugo Montanari, Alberto Martelli:
  Dynamic Programming as Graph Searching: An Algebraic Approach. 737-751
  
• Naoki Katoh, Toshihide Ibaraki, H. Mine:
  An Algorithm for the K Best Solutions of the Resource Allocation Problem. 752-764
  
• Christos H. Papadimitriou:
  On the complexity of integer programming. 765-768
  
• Robert E. Shostak:
  Deciding Linear Inequalities by Computing Loop Residues. 769-779
  
• Andrew Chi-Chih Yao:
  A Lower Bound to Finding Convex Hulls. 780-787