Journal of the ACM, Volume 22, 1975

Volume 22, Number 1, January 1975

• Leslie G. Valiant:
  Regularity and Related Problems for Deterministic Pushdown Automata. 1-10
  
• Harry T. Hsu:
  An Algorithm for Finding a Minimal Equivalent Graph of a Digraph. 11-16
  
• Clement T. Yu:
  A Formal Construction of Term Classes. 17-37
  
• Ellis Horowitz, Sartaj Sahni:
  On Computing the Exact Determinant of Matrices with Polynomial Entries. 38-50
  
• Charles A. Micchelli, Willard L. Miranker:
  High Order Search Methods for Finding Roots. 51-60
  
• John R. Rice:
  A Metalgorithm for Adaptive Quadrature. 61-82
  
• Samuel H. Fuller, Forest Baskett:
  An Analysis of Drum Storage Units. 83-105
  
• Walter H. Kohler, Kenneth Steiglitz:
  Exact, Approximate, and Guaranteed Accuracy Algorithms for the Flow-Shop Problem n/2/F/\bar F. 106-114
  
• Sartaj Sahni:
  Approximate Algorithms for the 0/1 Knapsack Problem. 115-124
  
• J. W. Wright:
  The Change-Making Problem. 125-128
  
• Robert S. Boyer, J. Strother Moore:
  Proving Theorems about LISP Functions. 129-144
  
• Lawrence Yelowitz:
  Derivation of a Path-Connectivity Matrix for Tagged Flowcharts. 145-154
  
• Richard E. Ladner:
  On the Structure of Polynomial Time Reducibility. 155-171
  
• C. C. Gotlieb, Glenn H. MacEwen:
  Errata: ``Performance of Movable-Head Disk Storage Devices''. 172
  

Volume 22, Number 2, April 1975

• Roy Lowrance, Robert A. Wagner:
  An Extension of the String-to-String Correction Problem. 177-183
  
• Jacques Morgenstern:
  The Linear Complexity of Computation. 184-194
  
• David E. Muller, Franco P. Preparata:
  Bounds to Complexities of Networks for Sorting and for Switching. 195-201
  
• Yehoshua Perl, M. R. Garey, Shimon Even:
  Efficient Generation of Optimal Prefix Code: Equiprobable Words Using Unequal Cost Letters. 202-214
  
• Robert Endre Tarjan:
  Efficiency of a Good But Not Linear Set Union Algorithm. 215-225
  
• Bernd Knauer:
  A Simple Planarity Criterion. 226-230
  
• Jair M. Babad:
  A Generalized Multi-Entrance Time-Sharing Priority Queue. 231-247
  
• Forest Baskett, K. Mani Chandy, Richard R. Muntz, Fernando G. Palacios:
  Open, Closed, and Mixed Networks of Queues with Different Classes of Customers. 248-260
  
• Erol Gelenbe:
  On Approximate Computer System Models. 261-269
  
• Micha Hofri, Micha Yadin:
  A Processor in Series with Demand-Interrupting Devices - A Stochastic Model. 270-290
  
• David R. Musser:
  Multivariate Polynomial Factorization. 291-308
  
• Arnold L. Rosenberg:
  Corrigendum: ``Allocating Storage for Extendible Arrays''. 308
  

Volume 22, Number 3, July 1975

• Roger C. Schank, Neil M. Goldman, Charles J. Rieger III, Christopher Riesbeck:
  Inference and Paraphrase by Computer. 309-328
  
• Gregory J. Chaitin:
  A Theory of Program Size Formally Identical to Information Theory. 329-340
  
• Nancy A. Lynch:
  On Reducibility to Complex or Sparse Sets. 341-345
  
• Glenn K. Manacher:
  A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a String. 346-351
  
• S. E. Goodman, Stephen T. Hedetniemi, Peter J. Slater:
  Advances on the Hamiltonian Completion Problem. 352-360
  
• John L. Pfaltz:
  Representing Graphs by Knuth Trees. 361-366
  
• Peter Elias, Richard A. Flower:
  The Complexity of Some Simple Retrieval Problems. 367-379
  
• Robert E. Dressler, S. Thomas Parker:
  Primes with a Prime Subscript. 380-381
  
• John L. Bruno, T. Lassagne:
  The Generation of Optimal Code for Stack Machines. 382-396
  
• Walter C. Oney:
  Queueing Analysis of the Scan Policy for Moving-Head Disks. 397-412
  
• G. Terry Ross, Darwin Klingman, H. Albert Napier:
  A Computational Study of the Effects of Problem Dimensions on Solution Times for Transportation Problems. 413-424
  
• Ravi Sethi:
  Errata: ``Testing for the Church-Rosser Property''. 424
  
• Antonin Svoboda:
  The Concept of Term Exclusiveness and Its Effect on the Theory of Boolean Functions. 425-440
  

Volume 22, Number 4, October 1975

• Malcolm C. Easton, C. K. Wong:
  The Effect of a Capacity Constraint on the Minimal Cost of a Partition. 441-449
  
• Ellis Horowitz:
  A Sorting Algorithm for Polynomial Multiplication. 450-462
  
• Oscar H. Ibarra, Chul E. Kim:
  Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems. 463-468
  
• H. T. Kung, Fabrizio Luccio, Franco P. Preparata:
  On Finding the Maxima of a Set of Vectors. 469-476
  
• Shmuel Winograd:
  On the Parallel Evaluation of Certain Arithmetic Expressions. 477-492
  
• Eberhard Bertsch:
  An Observation on Relative Parsing Time. 493-498
  
• Ivan Hal Sudborough:
  A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages. 499-500
  
• Bal Kishan Dass:
  A Sufficient Bound for Codes Correcting Bursts with Weight Constraint. 501-503
  
• Jeff R. Cash:
  A Class of Implicit Runge-Kutta Methods for the Numerical Integration of Stiff Ordinary Differential Equations. 504-511
  
• Webb Miller:
  Computer Search for Numerical Instability. 512-521
  
• K. L. Krause, V. Y. Shen, Herbert D. Schwetman:
  Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems. 522-550
  
• John P. Hayes:
  The Fanout Structure of Switching Functions. 551-571
  
• Robert A. Kowalski:
  A Proof Procedure Using Connection Graphs. 572-595
  
• J. Robert Jump, P. S. Thiagarajan:
  On the Interconnection of Asynchronous Control Structures. 596-612