Last update:
Thu Sep 10 16:14:57 MDT 2009
Paolo Ercoli Letters to the Editor: Errors Due to
Overflow in Arithmetic Operations . . . A9--A9
Robert Endre Tarjan and
Andrew Chi-Chih Yao Storing a Sparse Table . . . . . . . . . 606--611
S. B. Williams The Association for Computing Machinery 1--3
J. W. Backus The IBM 701 Speedcoding System . . . . . 4--6
R. T. Wiseman Life Insurance Premium Billing and
Combined Operations by Electronic
Equipment . . . . . . . . . . . . . . . 7--12
F. E. Hamilton and
E. C. Kubie The IBM Magnetic Drum Calculator Type
650 . . . . . . . . . . . . . . . . . . 13--20
H. Jacobs, Jr. Equipment Reliability as Applied to
Analogue Computers . . . . . . . . . . . 21--26
C. M. Edwards Survey of Analog Multiplication Schemes 27--35
Richmond Perley Automatic Strain-Gage and Thermocouple
Recording on Punched Cards . . . . . . . 36--43
Anonymous News and Notices . . . . . . . . . . . . 44--44
A. J. Neumann Supplement: ONR Digital Computer
Newsletter . . . . . . . . . . . . . . . 45--55
Alan L. Leiner System Specifications for the DYSEAC . . 57--81
Paul Brock and
Sybil Rock Problems in Acceptance Testing in
Digital Computers . . . . . . . . . . . 82--87
Jack Moshman The Generation of Pseudo-Random Numbers
on a Decimal Calculator . . . . . . . . 88--91
Anonymous News and Notices . . . . . . . . . . . . 92--92
A. J. Neumann Supplement: ONR Digital Computer
Newsletter . . . . . . . . . . . . . . . 93--100
Stefan Bergman A Method of Solving Boundary Value
Problems of Mathematical Physics on
Punch Card Machines . . . . . . . . . . 101--104
A. D. Wasel A Method of Determining Plate Bending by
Use of a Punched-Card Machine . . . . . 105--110
Stephen H. Crandall Numerical Treatment of a Fourth Order
Parabolic Partial Differential Equation 111--117
Calvin C. Elgot On Single vs. Triple Address Computing
Machines . . . . . . . . . . . . . . . . 118--123
C. C. Gotlieb Running a Computer Efficiently . . . . . 124--127
Louis B. Wadel An Electronic Differential Analyzer as a
Difference Analyzer . . . . . . . . . . 128--136
Anonymous News and Notices . . . . . . . . . . . . 137--138
A. J. Neumann Supplement: ONR Digital Computer
Newsletter . . . . . . . . . . . . . . . 139--148
C. J. Bashe and
W. Buchholz and
N. Rochester The IBM Type 702 . . . . . . . . . . . . 149--169
Susie E. Atta and
Ward C. Sangren Calculation of Generalized
Hypergeometric Series . . . . . . . . . 170--172
George F. Trexler Public Utility Customer Accounting on
the Type 650 Magnetic Drum Data
Processing Machine . . . . . . . . . . . 173--176
Walter F. Bauer and
John W. Carr III On the Demonstration of High-Speed
Digital Computers . . . . . . . . . . . 177--182
Philip Davis and
Philip Rabinowitz A Multiple Purpose Orthonormalizing Code
and Its Uses . . . . . . . . . . . . . . 183--191
Anonymous News and Notices . . . . . . . . . . . . 192--192
A. J. Neumann Supplement: ONR Digital Computer
Newsletter . . . . . . . . . . . . . . . 193--200
Heinz Rutishauser Some Programming Techniques for the
ERMETH . . . . . . . . . . . . . . . . . 1--4
H. J. Gray, Jr. Propagation of Truncation Errors in the
Numerical Solution of Ordinary
Differential Equations by Repeated
Closures . . . . . . . . . . . . . . . . 6--17
C. K. Titus A General Card-Program for the
Evaluation of the Inverse Laplace
Transform . . . . . . . . . . . . . . . 18--27
Benjamin F. Logan and
George R. Welti and
George C. Sponsler Analogue Study of Electron Trajectories 28--41
Stephen H. Crandall Implicit vs. Explicit Recurrence
Formulas for the Linear Diffusion
Equation . . . . . . . . . . . . . . . . 42--49
Anonymous News and Notices . . . . . . . . . . . . 50--52
A. J. Neumann Supplement: ONR Digital Computer
Newsletter . . . . . . . . . . . . . . . 53--60
F. J. Murray Mechanisms and Robots . . . . . . . . . 61--82
George J. Moshos Analog Interpolator for Automatic
Control . . . . . . . . . . . . . . . . 83--91
Howard Hamer and
Jerome D. Kennedy Testing of Operational Amplifiers . . . 92--94
Edward P. Graney Maintenance and Acceptance Tests Used on
the MIDAC . . . . . . . . . . . . . . . 95--98
Herschel Weil Reduction of Runs in Multiparameter
Computations . . . . . . . . . . . . . . 99--110
Harvey Cohn Some Experiments in Ideal Factorization
on the MIDAC . . . . . . . . . . . . . . 111--116
Anonymous News and Notices . . . . . . . . . . . . 117--118
A. J. Neumann Supplement: ONR Digital Computer
Newsletter . . . . . . . . . . . . . . . 119--136
David M. Young ORDVAC Solutions of the Dirichlet
Problem . . . . . . . . . . . . . . . . 137--161
Milton Abramowitz and
William F. Cahill On the Vibration of a Square Clamped
Plate . . . . . . . . . . . . . . . . . 162--168
Charles F. Pulvari Memory Matrix Using Ferroelectric
Condensers as Bistable Elements . . . . 169--185
Morris Rubinoff Digital Computers for Real-Time
Simulation . . . . . . . . . . . . . . . 186--204
Frances L. Parsons A Simple Desk-Calculator Method for
Checking Binary Results of Digital
Computer Arithmetic Operations . . . . . 205--207
Anonymous News and Notices . . . . . . . . . . . . 208--210
A. J. Neumann Supplement: ONR Digital Computer
Newsletter . . . . . . . . . . . . . . . 211--228
Carl G. Blanyer Precision Modulators and Demodulators 229--242
J. N. P. Hume and
Beatrice H. Worsley Transcode: A System of Automatic Coding
for FERUT . . . . . . . . . . . . . . . 243--252
T. P. Gorman and
R. G. Kelly and
R. B. Reddy Automatic Coding for the IBM 701 . . . . 253--261
Nathaniel Macon On the Computation of Exponential and
Hyperbolic Functions Using Continued
Fractions . . . . . . . . . . . . . . . 262--266
V. S. Haneman and
J. W. Senders Correlation Computation on Analog
Devices . . . . . . . . . . . . . . . . 267--279
Anonymous News and Notices . . . . . . . . . . . . 280--282
A. J. Neumann Supplement: ONR Digital Computer
Newsletter . . . . . . . . . . . . . . . 283--298
Alston S. Householder Presidential Address to the ACM,
Philadelphia, September 14, 1955 . . . . 1--2
Barry Gordon An Optimizing Program for the IBM 650 3--5
Peter Henrici A Subroutine for Computations with
Rational Numbers . . . . . . . . . . . . 6--9
Peter Henrici Automatic Computations with Power Series 10--15
Louis B. Wadel Simulation of Digital Filters on an
Electronic Analog Computer . . . . . . . 16--21
S. D. Conte and
R. F. Reeves A Kutta Third-Order Procedure for
Solving Differential Equations Requiring
Minimal Storage . . . . . . . . . . . . 22--25
Robert L. Young Report on Experiments in Approximating
the Solution of a Differential Equation 26--28
R. H. Stark Rates of Convergence in Numerical
Solution of the Diffusion Equation . . . 29--40
Anonymous News and Notices . . . . . . . . . . . . 41--43
Anonymous Digital Computer Newsletter . . . . . . 44--64
Robert Perkins EASIAC, A Pseudo-Computer . . . . . . . 65--72
J. M. Hammersley Conditional Monte Carlo . . . . . . . . 73--76
Herbert T. Glantz A Note on Microprogramming . . . . . . . 77--84
Alston S. Householder Bibliography on Numerical Analysis . . . 85--100
William R. Hoover and
John J. Wedel and
Joseph R. Bruman Wind Tunnel Data Reduction Using
Paper-Tape Storage Media . . . . . . . . 101--109
Anonymous News and Notices . . . . . . . . . . . . 110--111
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 112--113
Anonymous Digital Computer Newsletter . . . . . . 114--128
S. A. Lebedev The High-Speed Electronic Calculating
Machine of the Academy of Sciences of
the U.S.S.R. . . . . . . . . . . . . . . 129--133
Edward Harry Friend Sorting on Electronic Computer Systems 134--168
E. J. Isaac and
R. C. Singleton Sorting by Address Calculation . . . . . 169--174
Robert H. Bracken and
Bruce G. Oldfield A General System for Handling Alphameric
Information on the IBM 701 Computer . . 175--180
Walter F. Bauer An Integrated Computation System for the
ERA-1103 . . . . . . . . . . . . . . . . 181--185
L. E. Heizer and
S. J. Abraham Transfer Function Simulation by Means of
Amplifiers and Potentiometers . . . . . 186--198
Nathaniel Macon and
Margaret Baskervill On the Generation of Errors in the
Digital Evaluation of Continued
Fractions . . . . . . . . . . . . . . . 199--202
A. C. Downing, Jr. and
A. S. Householder Some Inverse Characteristic Value
Problems . . . . . . . . . . . . . . . . 203--207
Mark Lotkin A Note on the Midpoint Method of
Integration . . . . . . . . . . . . . . 208--211
Glenn H. Keitel An Extension of Milne's Three-Point
Method . . . . . . . . . . . . . . . . . 212--222
Richard Elton von Holdt An Iterative Procedure for the
Calculation of the Eigenvalues and
Eigenvectors of a Real Symmetric Matrix 223--238
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 239--239
Anonymous News and Notices . . . . . . . . . . . . 240--243
Anonymous Digital Computer Newsletter . . . . . . 244--263
Anonymous Editor's Note . . . . . . . . . . . . . 265--265
Wesley S. Melahn A Description of a Cooperative Venture
in the Production of an Automatic Coding
System . . . . . . . . . . . . . . . . . 266--271
Charles L. Baker The PACT I Coding System for the IBM
Type 701 . . . . . . . . . . . . . . . . 272--278
Owen R. Mock Logical Organization of the PACT I
Compiler . . . . . . . . . . . . . . . . 279--287
Robert C. Miller, Jr. and
Bruce G. Oldfield Producing Computer Instructions for the
PACT I Compiler . . . . . . . . . . . . 288--291
Gus Hempstead and
Jules I. Schwartz PACT Loop Expansion . . . . . . . . . . 292--298
J. I. Derr and
R. C. Luke Semi-Automatic Allocation of Data
Storage for PACT I . . . . . . . . . . . 299--308
I. D. Greenwald and
H. G. Martin Conclusions After Using the PACT I
Advanced Coding Technique . . . . . . . 309--313
Alston S. Householder On the Convergence of Matrix Iterations 314--324
Michael E. Fisher Higher Order Differences in the Analogue
Solution of Partial Differential
Equations . . . . . . . . . . . . . . . 325--347
J. H. Brown and
John W. Carr III and
Boyd Larrowe and
J. R. McReynolds Prevention of Propagation of Machine
Error in Long Problems . . . . . . . . . 348--354
Robert M. Mason The Digital Approximation of Contours 355--359
Richard C. Jeffrey Arithmetical Analysis of Digital
Computing Nets . . . . . . . . . . . . . 360--375
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 376--378
Anonymous News and Notices . . . . . . . . . . . . 379--382
Anonymous Digital Computer Newsletter . . . . . . 383--403
Alston S. Householder Retiring Presidential Address . . . . . 1--4
John W. Carr III Inaugural Presidential Address . . . . . 5--7
T. B. Steel, Jr. Pact IA . . . . . . . . . . . . . . . . 8--11
Walter F. Bauer and
George P. West A System for General-Purpose
Analog-Digital Computation . . . . . . . 12--17
S. D. Conte A Stable Implicit Finite Difference
Approximation to a Fourth Order
Parabolic Equation . . . . . . . . . . . 18--23
Yudell L. Luke Rational Approximations to the
Exponential Function . . . . . . . . . . 24--29
A. Shenitzer Chebyshev Approximation of a Continuous
Function by a Class of Functions . . . . 30--35
Susie E. Atta Effect of Propagated Error on Inverse of
Hilbert Matrix . . . . . . . . . . . . . 36--40
D. H. Lehmer Sorting Cards with Respect to a Modulus 41--46
David A. Huffman The Design and Use of Hazard-Free
Switching Networks . . . . . . . . . . . 47--62
Hao Wang A Variant to Turing's Theory of
Computing Machines . . . . . . . . . . . 63--92
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 93--94
F. L. Alt News and Notices . . . . . . . . . . . . 95--96
Gordon D. Goldstein Digital Computer Newsletter . . . . . . 97--120
J. H. Chung and
C. C. Gotlieb Test of an Inventory Control System on
FERUT . . . . . . . . . . . . . . . . . 121--130
R. H. Bracken and
H. E. Tillitt Information Searching with the 701
Calculator . . . . . . . . . . . . . . . 131--136
Francis H. Harlow Hydrodynamic Problems Involving Large
Fluid Distortions . . . . . . . . . . . 137--142
Gene H. Leichner Designing Computer Circuits With a
Computer . . . . . . . . . . . . . . . . 143--147
James A. Ward The Down-Hill Method of Solving $f(z) =
0$ . . . . . . . . . . . . . . . . . . . 148--150
F. Yates and
S. Lipton An Automatic Programming Routine for the
Elliott 401 . . . . . . . . . . . . . . 151--156
Robert J. Mercer Micro-Programming . . . . . . . . . . . 157--171
Charles J. Swift Machine Features for a More Automatic
Monitoring System on Digital Computers 172--173
J. Kister and
P. Stein and
S. Ulam and
W. Walden and
M. Wells Experiments in Chess . . . . . . . . . . 174--177
Herbert T. Glantz On the Recognition of Information With a
Digital Computer . . . . . . . . . . . . 178--188
William Miehle Burroughs Truth Function Evaluator . . . 189--192
Arthur W. Burks and
Hao Wang The Logic of Automata, Part I . . . . . 193--218
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 219--220
F. L. Alt News and Notices . . . . . . . . . . . . 221--224
Gordon D. Goldstein Digital Computer Newsletter . . . . . . 225--244
Anthony G. Oettinger Account Identification for Automatic
Data Processing . . . . . . . . . . . . 245--253
Saul Gorn Standardized Programming Methods and
Universal Coding . . . . . . . . . . . . 254--273
S. Lipton Two Programming Techniques for
One-Plus-One Address Computers . . . . . 274--278
Arthur W. Burks and
Hao Wang The Logic of Automata, Part II . . . . . 279--297
Wallace Givens The Characteristic Value-Vector Problem 298--307
Paul S. Dwyer and
Bernard A. Galler The Method of Reduced Matrices for a
General Transportation Problem . . . . . 308--313
Gene Thomas Thompson On Bateman's Method for Solving Linear
Integral Equations . . . . . . . . . . . 314--328
J. H. Halton and
D. C. Hanscomb A Method of Increasing the Efficiency of
Monte Carlo Integration . . . . . . . . 329--340
Allen A. Goldstein and
Norman Levine and
James B. Hereshoff On the ``Best'' and ``Least ${Q}$th''
Approximation of an Overdetermined
System of Linear Equations . . . . . . . 341--347
T. C. Rowan Psychological Tests and Selection of
Computer Programmers . . . . . . . . . . 348--353
David R. Israel Simulation Techniques for the Test and
Evaluation of Real-Time Computer
Programs . . . . . . . . . . . . . . . . 354--361
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 362--366
F. L. Alt News and Notices . . . . . . . . . . . . 367--370
Gordon D. Goldstein Digital Computer Newsletter . . . . . . 371--391
Theodore J. Williams and
R. Curtis Johnson and
Arthur Rose Computations in the Field of Engineering
Chemistry . . . . . . . . . . . . . . . 393--419
A. Weinberger and
H. Loberman Symbolic Designations for Electrical
Connections . . . . . . . . . . . . . . 420--427
H. Loberman and
A. Weinberger Formal Procedures for Connecting
Terminals with a Minimum Total Wire
Length . . . . . . . . . . . . . . . . . 428--437
R. T. Nelson and
J. R. Jackson SWAC Computations for Some $m \times n$
Scheduling Problems . . . . . . . . . . 438--441
Roger L. Boyell Programmed Multiplication on the IBM 407 442--449
Paolo Ercoli and
Roberto Vacca Errors Due to Overflow in Arithmetic
Operations Particularly as Regards FINAC
Electronic Computer . . . . . . . . . . 450--455
Nathaniel Macon Condensation and Look-Up Procedures for
Double Entry Tables . . . . . . . . . . 456--458
David A. Pope and
C. Tompkins Maximizing Functions of
Rotations---Experiments Concerning Speed
of Diagonalization of Symmetric Matrices
Using Jacobi's Method . . . . . . . . . 459--466
Stephen H. Crandall Optimum Recurrence Formulas for a Fourth
Order Parabolic Partial Differential
Equation . . . . . . . . . . . . . . . . 467--471
Bernard Sherman Determination of Three Percentiles of
the $\omega_n$ Distribution Function . . 472--476
C. L. Gerberich and
W. C. Sangren Codes for the Classical Membrane Problem 477--486
Robert C. Minnick Tshebysheff Approximations for Power
Series . . . . . . . . . . . . . . . . . 487--504
Emma Lehmer and
H. S. Vandiver On the Computation of the Number of
Solutions of Certain Trinomial
Congruences . . . . . . . . . . . . . . 505--510
IU. IA. Bazilevsk\t\i\i The Universal Electronic Digital Machine
(URAL) for Engineering Research . . . . 511--519
Anonymous Conference on Matrix Computations . . . 520--523
R. E. Cordray and
Robert M. Mason Remarks on a Recent Paper:
``Arithmetical Analysis of Digital
Computing Nets'' . . . . . . . . . . . . 524--529
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 530--533
F. L. Alt News and Notices . . . . . . . . . . . . 534--540
Gordon D. Goldstein Digital Computer Newsletter . . . . . . 541--558
A. F. R. Brown Language Translation . . . . . . . . . . 1--8
Marcia Ascher and
George E. Forsythe SWAC Experiments on the Use of
Orthogonal Polynomials for Data Fitting 9--21
A. Spitzbart and
D. L. Shell A Chebycheff Fitting Criterion . . . . . 22--31
Pentti Laasonen On the Truncation Error of Discrete
Approximations to the Solutions of
Dirichlet Problems in a Domain with
Corners . . . . . . . . . . . . . . . . 32--38
John W. Carr III Error Bounds for the Runge-Kutta
Single-Step Integration Process . . . . 39--44
J. N. Franklin On the Numerical Solution of
Characteristic Equations in Flutter
Analysis . . . . . . . . . . . . . . . . 45--51
T. R. Bashkow A ``Curve Plotting'' Routine for the
Inverse Laplace Transform of Rational
Functions . . . . . . . . . . . . . . . 52--56
A. E. Scott Automatic Preparation of Flow Chart
Listings . . . . . . . . . . . . . . . . 57--66
Edwin Hirschhorn Simplification of a Class of Boolean
Functions . . . . . . . . . . . . . . . 67--75
D. M. Baumann A High-Scanning-Rate Storage Device for
Computer Applications . . . . . . . . . 76--88
Serge J. Zaroodny and
Tadeusz Leser AYDAR, Special Purpose Analog Machine
for Yaw Data Reduction . . . . . . . . . 89--99
Wallace Givens Conference on Matrix Computations . . . 100--115
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 116--116
Anonymous Announcement . . . . . . . . . . . . . . 117--117
Leendeert de Witte and
Kenneth P. Fournier Evaluation of Integrals Involving
Combinations of Bessel Functions and
Circular Functions . . . . . . . . . . . 119--126
Robert L. Causey On Some Error Bounds of Givens . . . . . 127--131
Jack B. Dennis A High-Speed Computer Technique for the
Transportation Problem . . . . . . . . . 132--153
Werner L. Frank Finding Zeros of Arbitrary Functions . . 154--160
L. W. Ehrlich A Numerical Method of Solving a Heat
Flow Problem with Moving Boundary . . . 161--176
George N. Raney Sequential Functions . . . . . . . . . . 177--180
Irving M. Copi and
Calvin C. Elgot and
Jesse B. Wright Realization of Events by Logical Nets 181--196
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 197--203
A. S. Householder The Approximate Solution of Matrix
Problems . . . . . . . . . . . . . . . . 205--243
George G. den Broeder, Jr. and
Harry J. Smith A Property of Semi-Definite Hermitian
Matrices . . . . . . . . . . . . . . . . 244--245
F. L. Bauer On Modern Matrix Iteration Processes of
Bernoulli and Graeffe Type . . . . . . . 246--257
R. W. Cole A Note on Numerical Solution of Certain
Linear Boundary Value Problems . . . . . 258--260
Eve Bofinger and
V. J. Bofinger On a Periodic Property of Pseudo-Random
Sequences . . . . . . . . . . . . . . . 261--265
Seymour Ginsburg On the Length of the Smallest Uniform
Experiment Which Distinguishes the
Terminal States of a Machine . . . . . . 266--280
F. Lesh Methods of Simulating a Differential
Analyzer on a Digital Computer . . . . . 281--288
N. R. Goodman and
S. Katz Calculating Open Loop Transfer Functions
from Closed Loop Measurements . . . . . 289--297
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 298--308
Harley Tillitt Computer Programming for Young Students 309--318
Sherman Blumenthal A Dual Master File System for a Tape
Processing Computer . . . . . . . . . . 319--327
L. N. Korolev Coding and Code Compression . . . . . . 328--330
A. A. Markov On the Inversion Complexity of a System
of Functions . . . . . . . . . . . . . . 331--334
Alston S. Householder Generated Error in Rotational
Tridiagonalization . . . . . . . . . . . 335--338
Alston S. Householder Unitary Triangularization of a
Nonsymmetric Matrix . . . . . . . . . . 339--342
Jack Moshman The Application of Sequential Estimation
to Computer Simulation and Monte Carlo
Procedures . . . . . . . . . . . . . . . 343--352
J. Certaine On Sequences of Pseudo-Random Numbers of
Maximal Length . . . . . . . . . . . . . 353--356
Michael E. Fisher Proposed Methods for the Analog Solution
of Fredholm's Integral Equation . . . . 357--369
Pentti Laasonen On the Solution of Poisson's Difference
Equation . . . . . . . . . . . . . . . . 370--382
Martin F. Berman A Method for Transposing a Matrix . . . 383--384
Frederick H. Young Analysis of Shift Register Counters . . 385--388
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 389--396
Anonymous Author Index, 1954--1958 . . . . . . . . 397--403
W. C. McGee Generalization: Key to Successful
Electronic Data Processing . . . . . . . 1--23
Michael Zarechnak Three Levels of Linguistic Analysis in
Machine Translation . . . . . . . . . . 24--32
Richard D. Eldred Test Routines Based on Symbolic Logical
Statements . . . . . . . . . . . . . . . 33--36
R. W. Hamming Stable Predictor-Corrector Methods for
Ordinary Differential Equations . . . . 37--47
Jim Douglas, Jr. Round-Off Error in the Numerical
Solution of the Heat Equation . . . . . 48--58
H. H. Goldstine and
F. J. Murray and
J. von Neumann The Jacobi Method for Real Symmetric
Matrices . . . . . . . . . . . . . . . . 59--96
G. N. Lance Solution of Algebraic and Transcendental
Equations on an Automatic Digital
Computer . . . . . . . . . . . . . . . . 97--101
Shu-T'ien Li Origin and Development of the Chinese
Abacus . . . . . . . . . . . . . . . . . 102--110
René de Vogelaere Remarks on the Paper ``Tchebysheff
Approximations for Power Series'' . . . 111--114
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 115--120
Walter F. Bauer and
Mario L. Juncosa and
Alan J. Perlis ACM Publications Policies and Plans . . 121--122
Donald L. Shell The SHARE 709 System: A Cooperative
Effort . . . . . . . . . . . . . . . . . 123--127
Irwin D. Greenwald and
Maureen Kane The SHARE 709 System: Programming and
Modification . . . . . . . . . . . . . . 128--133
E. M. Boehm and
T. B. Steel, Jr. The SHARE 709 System: Machine
Implementation of Symbolic Programming 134--140
Vincent J. DiGri and
Jane E. King The SHARE 709 System: Input-Output
Translation . . . . . . . . . . . . . . 141--144
Owen Mock and
Charles J. Swift The SHARE 709 System: Programmed
Input-Output Buffering . . . . . . . . . 145--151
Harvey Bratman and
Ira V. Boldt, Jr. The SHARE 709 System: Supervisory
Control . . . . . . . . . . . . . . . . 152--155
Paul Hildebrandt and
Harold Isbitz Radix Exchange---An Internal Sorting
Method for Digital Computers . . . . . . 156--163
Rosalind B. Marimont A New Method for Checking the
Consistency of Precedence Matrices . . . 164--171
Gertrud S. Joachim Memory Efficiency . . . . . . . . . . . 172--175
H. H. Goldstine and
L. P. Horowitz A Procedure for the Diagonalization of
Normal Matrices . . . . . . . . . . . . 176--195
W. E. Milne and
R. R. Reynolds Stability of a Numerical Solution of
Differential Equations . . . . . . . . . 196--203
Louis W. Ehrlich Monte Carlo Solutions of Boundary Value
Problems Involving the Difference
Analogue of $\partial^2u/\partial x^2 +
\partial^2u/\partial y^2 +
({K}/y)(\partial u/\partial y) = 0$ . . 204--218
David Morrison Numerical Quadrature in Many Dimensions 219--222
George C. Caldwell A Note on the Downhill Method . . . . . 223--225
Harold W. Milnes and
Renfrey B. Potts Boundary Contraction Solution of
Laplace's Differential Equation . . . . 226--235
Elizabeth H. Cuthill and
Richard S. Varga A Method of Normalized Block Iteration 236--244
H. Allen Curtis A Functional Canonical Form . . . . . . 245--258
Seymour Ginsburg On the Reduction of Superfluous States
in a Sequential Machine . . . . . . . . 259--282
Marvin Blum On Exponential Digital Filters . . . . . 283--304
D. J. Wheeler and
H. P. F. Swinnerton-Dyer Letter to the Editor: ``A Method for
Transposing a Matrix'' . . . . . . . . . 305--305
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 306--312
A. L. Leiner and
W. A. Notz and
J. L. Smith and
A. Weinberger PILOT---A New Multiple Computer System 313--335
J. H. Wilkinson Stability of the Reduction of a Matrix
to Almost Triangular and Triangular
Forms by Elementary Similarity
Transformations . . . . . . . . . . . . 336--359
C. T. Fike Note on the Practical Computation of
Proper Values . . . . . . . . . . . . . 360--362
Herbert S. Wilf A Stability Criterion for Numerical
Integration . . . . . . . . . . . . . . 363--365
Fernando J. Corbató and
Jack L. Uretsky Generation of Spherical Bessel Functions
in Digital Computers . . . . . . . . . . 366--375
Mervin E. Muller A Comparison of Methods for Generating
Normal Deviates on Digital Computers . . 376--383
A. Ralston A Family of Quadrature Formulas Which
Achieve High Accuracy in Composite Rules 384--394
Philip C. Curtis, Jr. and
Werner L. Frank An Algorithm for the Determination of
the Polynomial of Best Minimax
Approximation to a Function Defined on a
Finite Point Set . . . . . . . . . . . . 395--404
Douglas B. Netherwood Logic Matrices and the Truth Function
Problem . . . . . . . . . . . . . . . . 405--414
R. L. Ashenhurst and
N. Metropolis Unnormalized Floating Point Arithmetic 415--428
Charles R. Blair On Computer Transcription of Manual
Morse . . . . . . . . . . . . . . . . . 429--442
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 443--458
H. Nagler Amphisbaenic Sorting . . . . . . . . . . 459--468
Julius Lieblein A General Analysis of Variance Scheme
Applicable to a Computer With a Very
Large Memory . . . . . . . . . . . . . . 469--475
E. J. Gauss A Comparison of Machine Organizations by
Their Performance of the Iteration
Solution of Linear Equations . . . . . . 476--485
Richard Bellman and
John Holland and
Robert Kalaba On an Application of Dynamic Programming
to the Synthesis of Logical Systems . . 486--493
J. W. Sheldon On the Spectral Norms of Several
Iterative Processes . . . . . . . . . . 494--505
Walter Hoffman and
Richard Pavley A Method for the Solution of the ${N}$th
Best Path Problem . . . . . . . . . . . 506--514
A. R. DiDonato and
A. V. Hershey New Formulas for Computing Incomplete
Elliptic Integrals of the First and
Second Kind . . . . . . . . . . . . . . 515--526
Bert F. Green, Jr. and
J. E. Keith Smith and
Laura Klem Empirical Tests of an Additive Random
Number Generator . . . . . . . . . . . . 527--537
H. Allen Curtis Multifunctional Circuits in Functional
Canonical Form . . . . . . . . . . . . . 538--547
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 548--556
David E. Ferguson Input-Output Buffering and Fortran . . . 1--9
Marvin L. Stein and
Jack Rose Changing from Analog to Digital
Programming by Digital Techniques . . . 10--23
Richard Bellman Sequential Machines, Ambiguity, and
Dynamic Programming . . . . . . . . . . 24--28
M. L. Juncosa and
T. W. Mullikin On the Increase of Convergence Rates of
Relaxation Procedures for Elliptic
Partial Differential Equations . . . . . 29--36
Tse-Sun Chow and
Harold Willis Milnes Boundary Contraction Solution of
Laplace's Differential Equation II . . . 37--45
W. E. Milne and
R. R. Reynolds Stability of a Numerical Solution of
Differential Equations---Part II . . . . 46--56
B. A. Galler and
D. P. Rozenburg A Generalization of a Theorem of Carr on
Error Bounds for Runge-Kutta Procedures 57--60
W. H. Anderson and
R. B. Ball and
J. R. Voss A Numerical Method for Solving Control
Differential Equations on Digital
Computers . . . . . . . . . . . . . . . 61--68
Gerard P. Weeg Truncation Error in the Graeffe
Root-Squaring Method . . . . . . . . . . 69--71
R. R. Coveyou Serial Correlation in the Generation of
Pseudo-Random Numbers . . . . . . . . . 72--74
A. Rotenburg A New Pseudo-Random Number Generator . . 75--77
H. H. Goldstine Footnote to a Recent Paper . . . . . . . 78--79
R. W. Hamming Book Reviews . . . . . . . . . . . . . . 80--86
Herbert Gelernter and
J. R. Hansen and
C. L. Gerberich A Fortran-Compiled List-Processing
Language . . . . . . . . . . . . . . . . 87--101
Dag Prawitz and
Håkan Prawitz and
Neri Voghera A Mechanical Proof Procedure and its
Realization in an Electronic Computer 102--128
Gerard Salton A New Method for the Payment of Bills
and the Transfer of Credit . . . . . . . 140--149
Hans J. Maehly Methods for Fitting Rational
Approximations, Part I: Telescoping
Procedures for Continued Fractions . . . 150--162
Robin E. Esch A Necessary and Sufficient Condition for
Stability of Partial Difference Equation
Problems . . . . . . . . . . . . . . . . 163--175
R. Alonso A Starting Method for the Three-Point
Adams Predictor-Corrector Method . . . . 176--180
E. A. Flinn A Modification of Filon's Method of
Numerical Integration . . . . . . . . . 181--184
David D. Morrison Remarks on the Unitary Triangularization
of a Nonsymmetric Matrix . . . . . . . . 185--186
J. A. Lively Letter to the Editor: Remarks on
``Amphisbaenic Sorting'' . . . . . . . . 187--187
E. J. Gauss Corrigendum: ``A Comparison of Machine
Organizations by Their Performance of
the Iteration Solution of Linear
Equations'' . . . . . . . . . . . . . . 188--188
Anonymous Book Reviews . . . . . . . . . . . . . . 189--200
Martin Davis and
Hilary Putman A Computing Procedure for Quantification
Theory . . . . . . . . . . . . . . . . . 201--215
M. E. Maron and
J. L. Kuhns On Relevance, Probabilistic Indexing and
Information Retrieval . . . . . . . . . 216--244
Walter F. Freiberger and
Richard H. Jones Computation of the Frequency Function of
a Quadratic Form in Random Normal
Variables . . . . . . . . . . . . . . . 245--250
Arthur Gill Analysis of Nets by Numerical Methods 251--254
Frank Harary On the Consistency of Precedence
Matrices . . . . . . . . . . . . . . . . 255--259
J. M. Ortega On Sturm Sequences for Tridiagonal
Matrices . . . . . . . . . . . . . . . . 260--263
Samuel D. Conte and
Ralph T. Dames On an Alternating Direction Method for
Solving the Plate Problem with Mixed
Boundary Conditions . . . . . . . . . . 264--273
Werner L. Frank Solution of Linear Systems by
Richardson's Method . . . . . . . . . . 274--286
G. B. Fitzpatrick Synthesis of Binary Ring Counters of
Given Periods . . . . . . . . . . . . . 287--297
Ronald Prather Computational Aids for Determining the
Minimal Form of a Truth Function . . . . 299--310
Seymour Ginsburg Connective Properties Preserved in
Minimal State Machines . . . . . . . . . 311--325
C. E. Miller and
A. W. Tucker and
R. A. Zemlin Integer Programming Formulation of
Traveling Salesman Problems . . . . . . 326--329
Erwin Kleinfeld Techniques for Enumerating
Veblen-Wedderburn Systems . . . . . . . 330--337
E. E. Osborne On Pre-Conditioning of Matrices . . . . 338--345
Erwin H. Bareiss Resultant Procedure and the
Mechanization of the Graeffe Process . . 346--386
N. L. Gordon and
A. H. Flasterstein A Note on a Method of Computing the
Gamma Function . . . . . . . . . . . . . 387--388
Ivan Flores Computer Time for Address Calculation
Sorting . . . . . . . . . . . . . . . . 389--409
W. G. Wadey Floating-Point Arithmetics . . . . . . . 129--139
Herbert B. Keller Finite Automata, Pattern Recognition and
Perceptrons . . . . . . . . . . . . . . 1--20
Walter Gautschi Recursive Computation of Certain
Integrals . . . . . . . . . . . . . . . 21--40
Ivan Flores Analysis of Internal Computer Sorting 41--80
Seymour Ginsburg Sets of Tapes Accepted by Different
Types of Automata . . . . . . . . . . . 81--86
Aviezri S. Fraenkel The User of Index Calculus and Mersenne
Primes for the Design of a High-Speed
Digital Multiplier . . . . . . . . . . . 87--96
A. L. Leiner and
W. W. Youden A System for Generating
``Pronounceable'' Names Using a Computer 97--103
Harry H. Denman Computer Generation of Optimized
Subroutines . . . . . . . . . . . . . . 104--116
H. Nagler Letter to the Editor: An Answer to Mr.
J. A. Lively's Remarks on the Paper
``Amphisbaenic Sorting'' . . . . . . . . 117--117
Donald E. Knuth Minimizing Drum Latency Time . . . . . . 119--150
D. H. Lehmer A Machine Method for Solving Polynomial
Equations . . . . . . . . . . . . . . . 151--162
Martin Greenberger Notes on a New Pseudo-Random Number
Generator . . . . . . . . . . . . . . . 163--167
Lionello Lombardi System Handling of Functional Operators 168--185
Peter Calingaert Two-Dimensional Parity Checking . . . . 186--200
John E. Walsh Computer-Feasible Method for Handling
Incomplete Data in Regression Analysis 201--211
Robert Hooke and
T. A. Jeeves ``Direct Search'' Solution of Numerical
and Statistical Problems . . . . . . . . 212--229
R. Totschek and
R. C. Wood An Investigation of Real-Time Solution
of the Transportation Problem . . . . . 230--239
L. I. Gutenmakher and
G. E. Vleduts The Prospects for the Utilization of
Informational-Logical Machines in
Chemistry (USSR) . . . . . . . . . . . . 240--251
R. C. Brigham and
P. D. Burgess Generalized Simulation of Post Office
Systems . . . . . . . . . . . . . . . . 252--259
Herbert M. Gurk and
Jack Minker The Design and Simulation of an
Information Processing System . . . . . 260--270
H. Edmund Stiles The Association Factor in Information
Retrieval . . . . . . . . . . . . . . . 271--279
J. H. Wilkinson Error Analysis of Direct Methods of
Matrix Inversion . . . . . . . . . . . . 281--330
Donald E. Johansen A Modified Givens Method for the
Eigenvalue Evaluation of Large Matrices 331--335
Tse-Sun Chow and
Harold Willis Milnes Numerical Solution of the Neumann and
Mixed Boundary Value Problems by
Boundary Contraction . . . . . . . . . . 336--358
Seymour V. Parter Some Computational Results on
``Two-line'' Iterative Methods for the
Biharmonic Difference Equation . . . . . 359--365
R. W. Klopfenstein Zeros of Nonlinear Functions . . . . . . 366--373
Edwin S. Campbell and
R. Buehler and
J. O. Hirschfelder and
D. Hughes Numerical Construction of Taylor Series
Approximations for a Set of Simultaneous
First Order Differential Equations . . . 374--383
C. Y. Lee Categorizing Automata by ${W}$-Machine
Programs . . . . . . . . . . . . . . . . 384--399
Seymour Ginsburg Compatibility of States in
Input-Independent Machines . . . . . . . 400--403
M. E. Maron Automatic Indexing: An Experiment
Inquiry . . . . . . . . . . . . . . . . 404--417
E. J. Gauss Locating the Largest Word in a File
Using a Modified Memory . . . . . . . . 418--425
J. Heller Sequencing Aspects of Multiprogramming 426--439
Joseph F. A. Ormsby Design of Numerical Filters with
Applications to Missile Data Processing 440--466
Michael Arbib Turing Machines, Finite Automata and
Neural Nets . . . . . . . . . . . . . . 467--475
Shigere Watanabe $5$-Symbol $8$-State and $5$-Symbol
$6$-State Universal Turing Machines . . 476--483
H. Allen Curtis A Generalized Tree Circuit . . . . . . . 484--496
J. T. Chu Some Methods for Simplifying Switching
Circuits Using ``Don't Care'' Conditions 497--512
Eugene S. Schwartz An Automatic Sequencing Procedure With
Application to Parallel Programming . . 513--537
Charles P. Bourne and
Donald F. Ford A Study of Methods for Systematically
Abbreviating English Words and Names . . 538--552
Lauren B. Doyle Semantic Road Maps for Literature
Searchers . . . . . . . . . . . . . . . 553--578
Robert W. Floyd A Descriptive Language for Symbol
Manipulation . . . . . . . . . . . . . . 579--584
Gene Ott and
Neil H. Feinstein Design of Sequential Machines from Their
Regular Expressions . . . . . . . . . . 585--600
Thomas N. Hibbard Least Upper Bounds on Minimal Terminal
State Experiments for Two Classes of
Sequential Machines . . . . . . . . . . 601--612
Kurt Spielberg Representation of Power Series in Terms
of Polynomials, Rational Approximations
and Continued Fractions . . . . . . . . 613--627
E. E. Osborne On Least Squares Solutions of Linear
Equations . . . . . . . . . . . . . . . 628--636
Charlotte Froese An Evaluation of Runge-Kutta Type
Methods for Higher Order Differential
Equations . . . . . . . . . . . . . . . 637--644
E. K. Blum and
P. C. Curtis, Jr. Asymptotic Behavior of the Best
Polynomial Approximation . . . . . . . . 645--647
R. J. Gardner and
T. H. Gosling Letter to the Editor: ``Optimized
Subroutines'' . . . . . . . . . . . . . 648--649
Martin Goetz Letter to the Editor: ``Internal Sorting
and External Merging'' . . . . . . . . . 649--650
R. A. Brooker and
D. Morris A General Translation Program for Phrase
Structure Languages . . . . . . . . . . 1--10
Stephen Warshall A Theorem on Boolean Matrices . . . . . 11--12
Thomas N. Hibbard Some Combinatorial Properties of Certain
Trees With Applications to Sorting and
Searching . . . . . . . . . . . . . . . 13--28
Leland H. Williams Algebra of Polynomials in Several
Variables for a Digital Computer . . . . 29--40
G. Estrin and
C. R. Viswanathan Organization of a
``Fixed-Plus-Variable'' Structure
Computer for Computation of Eigenvalues
and Eigenvectors of Real Symmetric
Matrices . . . . . . . . . . . . . . . . 41--60
Richard Bellman Dynamic Programming Treatment of the
Travelling Salesman Problem . . . . . . 61--63
W. E. Milne and
R. R. Reynolds Fifth-Order Methods for the Numerical
Solution of Ordinary Differential
Equations . . . . . . . . . . . . . . . 64--70
Richard E. von Holdt Inversion of Triple-Diagonal Compound
Matrices . . . . . . . . . . . . . . . . 71--83
David L. Phillips A Technique for the Numerical Solution
of Certain Integral Equations of the
First Kind . . . . . . . . . . . . . . . 84--97
D. Morrison Optimal Mesh Size in the Numerical
Integration of an Ordinary Differential
Equation . . . . . . . . . . . . . . . . 98--103
Roger L. Crane and
Robert J. Lambert Stability of a Generalized Corrector
Formula . . . . . . . . . . . . . . . . 104--117
Eldon R. Hansen On Quasicyclic Jacobi Methods . . . . . 118--135
Lionello Lombardi Mathematical Structure of Nonarithmetic
Data Processing Procedures . . . . . . . 136--159
H. Bottenbruch Structure and Use of ALGOL 60 . . . . . 161--221
Bruce W. Arden and
Bernard A. Galler and
Robert M. Graham An Algorithm for Translating Boolean
Expressions . . . . . . . . . . . . . . 222--239
Franz L. Alt Digital Pattern Recognition by Moments 240--258
W. Doyle Operations Useful for
Similarity-Invariant Pattern Recognition 259--267
D. R. Smith and
C. H. Davidson Maintained Activity in Neural Nets . . . 268--279
Henry P. Kramer A Note on the Self-Consistency
Definitions of Generalization and
Inductive Inference . . . . . . . . . . 280--281
R. C. Bose and
R. J. Nelson A Sorting Problem . . . . . . . . . . . 282--296
John H. Holland Outline for a Logical Theory of Adaptive
Systems . . . . . . . . . . . . . . . . 297--314
Joyce Friedman A Decision Procedure for Computations of
Finite Automata . . . . . . . . . . . . 315--323
H. Allen Curtis Multiple Reduction of Variable
Dependency of Sequential Machines . . . 324--344
G. P. Weeg The Structure of an Automaton and Its
Operation-Preserving Transformation
Group . . . . . . . . . . . . . . . . . 345--349
Seymour Ginsburg and
H. Gordon Rice Two Families of Languages Related to
ALGOL . . . . . . . . . . . . . . . . . 350--371
Sheldon Sobel Oscillating Sort---A New Sort Merging
Technique . . . . . . . . . . . . . . . 372--374
John S. Bailey and
George Epstein Single Function Shifting Counters . . . 375--378
James J. Peterka A Method for Obtaining Specific Values
of Compiling-Parameter Functions . . . . 379--386
Thomas A. Holdiman Management Techniques for Real Time
Computer Programming . . . . . . . . . . 387--404
Sol Weintraub Cumulative Binomial Probabilities . . . 405--407
A. L. Dulmage and
N. S. Mendelsohn Matrices Associated with the Hitchcock
Problem . . . . . . . . . . . . . . . . 409--418
Jerome M. Kurtzberg On Approximation Methods for the
Assignment Problem . . . . . . . . . . . 419--439
Terence G. Jones An Algorithm for the Numerical
Application of a Linear Operator . . . . 440--449
Jim Douglas, Jr. and
James E. Gunn Alternating Direction Methods for
Parabolic Systems in $m$ Space Variables 450--456
P. E. Chase Stability Properties of
Predictor-Corrector Methods for Ordinary
Differential Equations . . . . . . . . . 457--468
A. C. Fleck Isomorphism Groups of Automata . . . . . 469--476
David G. Cantor On the Ambiguity Problem of Backus
Systems . . . . . . . . . . . . . . . . 477--479
A. A. Grau A Translator-Oriented Symbolic
Programming Language . . . . . . . . . . 480--487
A. D. Falkoff Algorithms for Parallel-Search Memories 488--511
Frank B. Baker Information Retrieval Based Upon Latent
Class Analysis . . . . . . . . . . . . . 512--521
G. Estrin and
C. R. Viswanathan Correction and Addendum: ``Organization
of a `Fixed-Plus-Variable' Structure
Computer for Computation of Eigenvalues
and Eigenvectors of Real Symmetric
Matrices'' . . . . . . . . . . . . . . . 522--522
J. Hartmanis Further Results on the Structure of
Sequential Machines . . . . . . . . . . 78--88
Brian Gluss A Method for Obtaining Suboptimal
Group-Testing Policies Using Dynamic
Programming and Information Theory . . . 89--96
S. Twomey On the Numerical Solution of Fredholm
Integral Equations of the First Kind by
the Inversion of the Linear System
Produced by Quadrature . . . . . . . . . 97--101
Eldon R. Hansen On the Danilewski Method . . . . . . . . 102--109
Arthur Gill On a Weight Distribution Problem, with
Application to the Design of Stochastic
Generators . . . . . . . . . . . . . . . 110--122
F. J. Corbató On the Coding of Jacobi's Method for
Computing Eigenvalues and Eigenvectors
of Symmetric Matrices . . . . . . . . . 123--125
J. L. Allard and
A. R. Dobell and
T. E. Hull Mixed Congruential Random Number
Generators for Decimal Machines . . . . 131--141
Thomas N. Hibbard A Simple Sorting Algorithm . . . . . . . 142--150
Harold Borko and
Myrna Bernick Automatic Document Classification . . . 151--162
J. A. Robinson Theorem-Proving on the Computer . . . . 163--174
Seymour Ginsburg and
G. F. Rose Operations Which Preserve Definability
in Languages . . . . . . . . . . . . . . 175--195
Saul Gorn Detection of Generative Ambiguities in
Context-Free Mechanical Languages . . . 196--208
C. N. Liu A State Variable Assignment Method for
Asynchronous Sequential Switching
Circuits . . . . . . . . . . . . . . . . 209--216
R. W. House and
T. Rado Erratum: ``On a Computer Program for
Obtaining Irreducible Representations
for Two-Level Multiple Input-Output
Logical Systems'' . . . . . . . . . . . 256--256
Hans J. Maehly Methods for Fitting Rational
Approximations, Parts II and III . . . . 257--278
Anthony Ralston On Economization of Rational Functions 279--282
Charles W. Valentine and
C. Peter Van Dine An Algorithm for Mimimax Polynomial
Curve-Fitting of Discrete Data . . . . . 283--290
T. E. Hull and
A. L. Creemer Efficiency of Predictor-Corrector
Procedures . . . . . . . . . . . . . . . 291--301
H. O. Hartley and
D. L. Harris Monte Carlo Computations in Normal
Correlation Problems . . . . . . . . . . 302--306
Robert W. Floyd Syntactic Analysis and Operator
Precedence . . . . . . . . . . . . . . . 316--333
Sheldon Klein and
Robert F. Simmons A Computational Approach to Grammatical
Coding of English Words . . . . . . . . 334--347
Joyce Friedman A Computer Program for a Solvable Case
of the Decision Problem . . . . . . . . 348--356
Elwyn R. Berlekamp Program for Double-Dummy Bridge
Problems---A New Strategy for Mechanical
Game Playing . . . . . . . . . . . . . . 357--364
Edwin H. Farr Lattice Properties of Sequential
Machines . . . . . . . . . . . . . . . . 365--385
H. Allen Curtis Use of Decomposition Theory in the
Solution of the State Assignment Problem
of Sequential Machines . . . . . . . . . 386--411
G. E. Lee-Whiting Erratum: ``Formulas for Computing
Incomplete Elliptic Integrals of the
First and Second Kinds'' . . . . . . . . 412--412
Gerard Salton Associative Document Retrieval
Techniques Using Bibliographic
Information . . . . . . . . . . . . . . 440--457
R. L. Mattson and
O. Firschein Feature Word Construction for Use with
Pattern Recognition Algorithms: An
Experimental Study . . . . . . . . . . . 458--477
Seymour Ginsburg and
Edwin H. Spanier Quotients of Context-Free Languages . . 487--492
Herbert A. Simon Experiments with a Heuristic Compiler 493--506
James R. Slagle A Heuristic Program that Solves Symbolic
Integration Problems in Freshman
Calculus . . . . . . . . . . . . . . . . 507--520
Robert H. Oehmke On the Structures of an Automaton and
Its Input Semigroup . . . . . . . . . . 521--525
Michael O. Rabin and
Hao Wang Words in the History of a Turing Machine
with a Fixed Input . . . . . . . . . . . 526--527
Robert W. Ritchie Finite Automata and the Set of Squares 528--531
A. Ben-Israel and
S. J. Wersan An Elimination Method for Computing the
Generalized Inverse of an Arbitrary
Complex Matrix . . . . . . . . . . . . . 532--537
A. A. Grau On the Reduction of Number Range in the
Use of the Graeffe Process . . . . . . . 538--544
Robert P. Rich and
Harry Shaw A Method for Finding All the Zeros of
$f(z)$ . . . . . . . . . . . . . . . . . 545--549
Ferdinand Freudenstein and
Bernard Roth Numerical Solution of Systems of
Nonlinear Equations . . . . . . . . . . 550--556
George Emanuel The Wilf Stability Criterion for
Numerical Integration . . . . . . . . . 557--561
H. Allen Curtis Generalized Tree Circuit---The Basic
Building Block of an Extended
Decomposition Theory . . . . . . . . . . 562--581
W. W. Youden Index, Volumes 1--10 (1954--1963) . . . 583--646
Joyce Friedman A Semi-Decision Procedure for the
Functional Calculus . . . . . . . . . . 1--24
Michael A. Harrison The Number of Classes of Invertible
Boolean Functions . . . . . . . . . . . 25--28
Seymour Ginsburg and
Gene F. Rose Some Recursively Unsolvable Problems in
ALGOL-Like Languages . . . . . . . . . . 29--47
R. W. House and
T. Rado On a Computer Program for Obtaining
Irreducible Representations for
Two-Level Multiple Input-Output Logical
Systems . . . . . . . . . . . . . . . . 48--77
G. E. Lee-Whiting Formulas for Computing Incomplete
Elliptic Integrals of the First and
Second Kinds . . . . . . . . . . . . . . 126--130
J. C. Shepherdson and
H. E. Sturgis Computability of Recursive Functions . . 217--255
M. Trainiter Addressing for Random-Access Storage
with Multiple Bucket Capabilities . . . 307--315
Eugene S. Schwartz A Dictionary for Minimum Redundancy
Encoding . . . . . . . . . . . . . . . . 413--439
R. L. Baber Tape Searching Techniques . . . . . . . 478--486
J. D. Rutledge On Ianov's Program Schemata . . . . . . 1--9
R. R. Brown Tape Sets and Automata . . . . . . . . . 10--14
John Cocke and
Marvin Minsky Universality of Tag Systems with ${P} =
2$ . . . . . . . . . . . . . . . . . . . 15--20
D. J. Farber and
R. E. Griswold and
I. P. Polonsky SNOBOL, A String Manipulation Language 21--30
T. E. Hull and
A. R. Dobell Mixed Congruential Random Number
Generators for Binary Machines . . . . . 31--40
Frank Stockmal Calculations with Pseudo-Random Numbers 41--52
C. Donald La Budde Two New Classes of Algorithms for
Finding the Eigenvalues and Eigenvectors
of Real Symmetric Matrices . . . . . . . 53--58
Josef Stoer A Direct Method for Chebyshev
Approximation by Rational Functions . . 59--69
William F. Pickard Tables of the Generalized Stirling
Numbers of the First Kind . . . . . . . 70--78
T. Giammo A Mathematical Model for the Automatic
Scaling of a Function . . . . . . . . . 79--83
Michael Yoeli and
Shlomo Rinon Application of Ternary Algebra to the
Study of Static Hazards . . . . . . . . 84--97
E. J. Gauss Estimation of Power Spectral Density by
Filters . . . . . . . . . . . . . . . . 98--103
Maurice Pollack Message Route Control in a Large
Teletype Network . . . . . . . . . . . . 104--116
William S. Cooper Fact Retrieval and Deductive
Question-Answering Information Retrieval
Systems . . . . . . . . . . . . . . . . 117--137
Harold Borko and
Myrna Bernick Automatic Document Classification. Part
II. Additional Experiments . . . . . . . 138--151
R. Schroeder Input Data Source Limitations for
Real-Time Operation of Digital Computers 152--158
B. Randell and
L. J. Russell Single-Scan Techniques for the
Translation of Arithmetic Expressions in
ALGOL 60 . . . . . . . . . . . . . . . . 159--167
R. L. Ashenhurst Function Evaluation in Unnormalized
Arithmetic . . . . . . . . . . . . . . . 168--187
William B. Gragg and
Hans J. Stetter Generalized Multistep
Predictor-Corrector Methods . . . . . . 188--209
Leonard Tornheim Convergence of Multipoint Iterative
Methods . . . . . . . . . . . . . . . . 210--220
James Ferguson Multivariable curve interpolation . . . 221--228
William F. Pickard Tables for the Step-by-Step Integration
of Ordinary Differential Equations of
the First Order . . . . . . . . . . . . 229--233
W. J. Hemmerle Algebraic Specification of Statistical
Models for Analysis of Variance
Computations . . . . . . . . . . . . . . 234--239
K. U. Smith and
S. D. Ansell and
J. Koehler and
G. H. Servos Digital Computer System for Dynamic
Analysis of Speech and Sound Feedback
Mechanisms . . . . . . . . . . . . . . . 240--251
James R. Slagle An Efficient Algorithm for Finding
Certain Minimum-Cost Procedures for
Making Binary Decisions . . . . . . . . 253--264
Ivan Flores Derivation of a Waiting-Time Factor for
a Multiple-Bank Memory . . . . . . . . . 265--282
Eugene L. Lawler An Approach to Multilevel Boolean
Minimization . . . . . . . . . . . . . . 283--294
Martin Cohn Properties of Linear Machines . . . . . 296--301
Seymour Ginsburg and
Thomas N. Hibbard Solvability of Machine Mappings of
Regular Sets to Regular Sets . . . . . . 302--312
C. C. Elgot and
J. D. Rutledge RS-Machines with Almost Blank Tape . . . 313--337
S. Winograd Input-Error-Limiting Automata . . . . . 338--351
Morris Gershinsky and
David A. Levine Aitken-Hermite Interpolation . . . . . . 352--356
Richard Kronmal Evaluation of a Pseudorandom Normal
Number Generator . . . . . . . . . . . . 357--363
Calvin C. Elgot and
Abraham Robinson Random-Access Stored Program Machines,
an Approach to Programming Languages . . 365--399
W. R. Klingman and
D. M. Himmelblau Nonlinear Programming with the Aid of a
Multiple-Gradient Summation Technique 400--415
Kenneth Hartt Some Analytical Procedures for Computers
and their Applications to a Class of
Multidimensional Integrals . . . . . . . 416--421
L. Duane Pyle Generalized Inverse Computations Using
the Gradient Projection Method . . . . . 422--428
Lee Krider A Flow Analysis Algorithm . . . . . . . 429--436
John O'Connor Mechanized Indexing Methods and their
Testing . . . . . . . . . . . . . . . . 437--449
Harold Sackman and
J. B. Munson Investigation of Computer Operating Time
and System Capacity for Man-Machine
Digital Systems . . . . . . . . . . . . 450--464
A. Wood Edwards and
Robert L. Chambers Can A Priori Probabilities Help in
Character Recognition? . . . . . . . . . 465--470
R. F. Dressler and
W. Werner Error Rates for Two Methods of
Statistical Pattern Recognition . . . . 471--480
Janusz A. Brzozowski Derivatives of Regular Expressions . . . 481--494
M. W. Curtis A Turing Machine Simulator . . . . . . . 1--13
Robert M. McLure A Programming Language for Simulating
Digital Systems . . . . . . . . . . . . 14--22
J. A. Robinson A Machine-Oriented Logic Based on the
Resolution Principle . . . . . . . . . . 23--41
Sheila A. Greibach A New Normal-Form Theorem for
Context-Free Phrase Structure Grammars 42--52
Eric Wolman A Fixed Optimum Cell-Size for Records of
Various Lengths . . . . . . . . . . . . 53--70
H. Glass and
L. Cooper Sequential Search: A Method for Solving
Constrained Optimized Problems . . . . . 71--82
M. Donald MacLaren and
George Marsaglia Uniform Random Number Generators . . . . 83--89
Aaron Booker Numerical Evaluation of Symmetric
Polynomials . . . . . . . . . . . . . . 90--94
R. W. Hockney A Fast Direct Solution of Poisson's
Equation Using Fourier Analysis . . . . 95--113
J. H. Bramble and
B. E. Hubbard Approximation of Solutions of Mixed
Boundary Value Problems for Poisson's
Equation by Finite Differences . . . . . 114--123
J. C. Butcher A Modified Multistep Method for the
Numerical Integration of Ordinary
Differential Equations . . . . . . . . . 124--135
Edward B. Anders An Error Bound for a Numerical Filtering
Technique . . . . . . . . . . . . . . . 136--140
Arthur Gill Analysis and Synthesis of Stable Linear
Sequential Circuits . . . . . . . . . . 141--149
Paul W. Broome Discrete Orthogonal Sequences . . . . . 151--168
David G. Moursund Examination of Multiple Roots and Root
Clusters of a Polynomial Using the
Bernoulli Procedure . . . . . . . . . . 169--174
R. D. Glauz On the Numerical Solution of Ordinary
and Partial Differential Equations Using
Integral Relations . . . . . . . . . . . 175--180
Charles B. Dunham Convergence Problems in Maehly's Second
Method . . . . . . . . . . . . . . . . . 181--186
G. P. Weeg The Automorphism Group of the Direct
Product of Strongly Related Automata . . 187--195
Shen Lin and
Tibor Rado Computer Studies of Turing Machine
Problems . . . . . . . . . . . . . . . . 196--212
J. T. Chu Optimum Decision Functions for Computer
Character Recognition . . . . . . . . . 213--226
R. L. Crane and
R. W. Klopfenstein A Predictor-Corrector Algorithm with an
Increased Range of Absolute Stability 227--241
Herbert Kanner Number Base Conversion in Significant
Digit Arithmetic . . . . . . . . . . . . 242--246
Walter Penney A ``Binary'' System for Complex Numbers 247--248
Jerry Sanders Document Association and Classification
Based on ${L}$-Languages . . . . . . . . 249--253
Stephen Glicksman Concerning the Merging of Equal Length
Tape Files . . . . . . . . . . . . . . . 254--258
W. J. Dixon and
R. A. Kronmal The Choice of Origin and Scale for
Graphs . . . . . . . . . . . . . . . . . 259--261
C. L. Sheng Threshold Logic Elements Used as a
Probability Transformer . . . . . . . . 262--276
S. Winograd On the Time Required to Perform Addition 277--285
R. W. Stineman Digital Time-Domain Analysis of Systems
with Widely Separated Poles . . . . . . 286--294
W. Fraser A Survey of Methods for Computing
Minimax and Near-Minimax Polynomial
Approximations for Functions of a Single
Independent Variable . . . . . . . . . . 295--314
A. P. Yershóv One View of Man-Machine Interaction
(Translated by Nicholas Zvegintzov) . . 315--325
Richard W. Conn and
Richard E. von Holdt An Online Display for the Study of
Approximating Functions . . . . . . . . 326--349
M. V. Menon On a Problem Concerning a Central
Storage Device Served by Multiple
Terminals . . . . . . . . . . . . . . . 350--355
William K. Winters A Modified Method of Latent Class
Analysis for File Organization in
Information Retrieval . . . . . . . . . 356--363
Franco Mileto and
Gianfranco Putzolu Statistical Complexity of Algorithms for
Boolean Function Minimization . . . . . 364--375
J. M. S. Simões Pereira On the Boolean Matrix Equation
$M'=\vee_{i=1}M^i$ . . . . . . . . . . . 376--382
David Moursund Chebyshev Solution of $n + 1$ Linear
Equations in $n$ Unknowns . . . . . . . 383--387
Patrick C. Fischer Generation of Primes by a
One-Dimensional Real-Time Iterative
Array . . . . . . . . . . . . . . . . . 388--394
D. J. Newman Location of the Maximum on Unimodal
Surfaces . . . . . . . . . . . . . . . . 395--398
A. Paz and
B. Peleg Ultimate-Definite and Symmetric-Definite
Events and Automata . . . . . . . . . . 399--410
Michael Yoeli Generalized Cascade Decompositions of
Automata . . . . . . . . . . . . . . . . 411--422
Seymour Ginsburg and
Edwin H. Spanier Mappings of Languages by Two-Tape
Devices . . . . . . . . . . . . . . . . 423--434
C. L. Sheng Correction: ``Threshold Logic Elements
Used as a Probability Transformer'' . . 435--435
Leroy F. Meyers Morphological Classification in the
National Bureau of Standards Mechanical
Translation System . . . . . . . . . . . 437--472
Lauren B. Doyle Is Automatic Classification a Reasonable
Application of Statistical Analysis of
Text? . . . . . . . . . . . . . . . . . 473--489
John O'Connor Automatic Subject Recognition in
Scientific Papers: An Empirical Study 490--515
Solomon W. Golomb and
Leonard D. Baumert Backtrack Programming . . . . . . . . . 516--524
A. V. Srinivasan An Investigation of Some Computational
Aspects of Integer Programming . . . . . 525--535
Lawrence Wos and
George A. Robinson and
Daniel F. Carson Efficiency and Completeness of the Set
of Support Strategy in Theorem Proving 536--541
T. R. N. Rao and
N. Zierler On Mappings for Modular Arithmetic, I 542--544
S. Berkovits and
M. Schlessing and
N. Zierler On Mappings for Modular Arithmetic, II 545--546
Donald G. Anderson Iterative Procedures for Nonlinear
Integral Equations . . . . . . . . . . . 547--560
Bruce Barnes Groups of Automorphisms and Sets of
Equivalence Classes of Input for
Automata . . . . . . . . . . . . . . . . 561--565
A. C. Fleck On the Automorphism Group of an
Automaton . . . . . . . . . . . . . . . 566--569
Patrick C. Fischer On Formalisms for Turing Machines . . . 570--580
Wei Chang and
Donald J. Wong Analysis of Real Time Multiprogramming 581--588
Jack B. Dennis Segmentation and the Design of
Multiprogrammed Computer Systems . . . . 589--602
G. B. Dantzig and
R. P. Harvey and
R. D. McKnight Updating the Product Form of the Inverse
for the Revised Simplex Method (A
Summary) . . . . . . . . . . . . . . . . 603--603
B. W. Arden and
B. A. Galler and
T. C. O'Brien and
F. H. Westervelt Program and Addressing Structure in a
Time-Sharing Environment . . . . . . . . 1--16
A. P. Yershóv ALPHA---An Automatic Programming System
of High Efficiency . . . . . . . . . . . 17--24
J. Schwartz Large Parallel Computers . . . . . . . . 25--32
A. Gill Realization of Input-Output Relations by
Sequential Machines . . . . . . . . . . 33--42
L. P. Horwitz and
R. M. Karp and
R. E. Miller and
S. Winograd Index Register Allocation . . . . . . . 43--61
Seymour Ginsburg and
Joseph Ullian Ambiguity in Context Free Languages . . 62--89
Philip Gilbert On the Syntax of Algorithmic Languages 90--107
Charles B. Dunham Convergence Problems in Maehly's Second
Method: Part II . . . . . . . . . . . . 108--113
George D. Byrne and
Robert J. Lambert Pseudo-Runge-Kutta Methods Involving Two
Points . . . . . . . . . . . . . . . . . 114--123
R. N. Maddison A Procedure for Nonlinear Least Squares
Refinement in Adverse Practical
Conditions . . . . . . . . . . . . . . . 124--134
C. A. Barlow, Jr. and
E. L. Jones A Method for the Solution of Roots of a
Nonlinear Equation and for Solution of
the General Eigenvalue Problem . . . . . 135--142
Takao Tsuda and
Hiroshi Matsumoto A Note on Linear Extrapolation of
Multivariable Functions by the Monte
Carlo Method . . . . . . . . . . . . . . 143--150
Michael A. Harrison On Asymptotic Estimates in Switching and
Automata Theory . . . . . . . . . . . . 151--157
Arto Salomaa Two Complete Axiom Systems for the
Algebra of Regular Events . . . . . . . 158--169
Charles A. Trauth, Jr. Group-Type Automata . . . . . . . . . . 170--175
Leonard Kleinrock Sequential Processing Machines (S.P.M.)
Analyzed with a Queueing Theory Model 179--193
Ruth A. Weiss BE VISION, A Package of IBM 7090 FORTRAN
Programs to Draw Orthographic Views of
Combinations of Plane and Quadric
Surfaces . . . . . . . . . . . . . . . . 194--204
John T. Welch, Jr. A Mechanical Analysis of the Cyclic
Structure of Undirected Linear Graphs 205--210
C. V. Ramamoorthy Analysis of Graphs by Connectivity
Considerations . . . . . . . . . . . . . 211--222
Stephen A. Cook The Solvability of the Derivability
Problem for One-Normal Systems . . . . . 223--225
Ward Douglas Maurer A Theory of Computer Instructions . . . 226--235
Kojiro Kobayashi and
Shigeru Sekiguchi On the Class of Predicates Decidable by
Two-Way Multitape Finite Automata . . . 236--261
Howard Holtz and
C. T. Leondes The Synthesis of Recursive Digital
Filters . . . . . . . . . . . . . . . . 262--280
Marvin Minsky and
Seymour Papert Unrecognizable Sets of Numbers . . . . . 281--286
Riaz A. Usmani Boundary Value Techniques for the
Numerical Solution of Certain Initial
Value Problems in Ordinary Differential
Equations . . . . . . . . . . . . . . . 287--295
Philip Rabinowitz Numerical Experiments in Conformal
Mapping by the Method of Orthonormal
Polynomials . . . . . . . . . . . . . . 296--303
W. W. Bledsoe Some Results on Multicategory Pattern
Recognition . . . . . . . . . . . . . . 304--316
B. Krishnamoorthi and
Roger C. Wood Time-Shared Operations with Both
Interarrival and Service Times
Exponential . . . . . . . . . . . . . . 317--338
Lewis T. Reinwald and
Richard M. Soland Conversion of Limited-Entry Decision
Tables to Optimal Computer Programs I:
Minimum Average Processing Time . . . . 339--358
Philip K. Hooper Monogenic Post Normal Systems of
Arbitrary Degree . . . . . . . . . . . . 359--363
Seymour Ginsburg and
Joseph Ullian Preservation of Unambiguity and Inherent
Ambiquity in Context-Free Languages . . 364--368
Sigmund N. Porter Use of Multiwrite for General
Programmability of Search Memories . . . 369--373
Fred T. Krogh Predictor-Corrector Methods of High
Order With Improved Stability
Characteristics . . . . . . . . . . . . 374--385
Bruce A. Chartres Automatic Controlled Precision
Calculations . . . . . . . . . . . . . . 386--403
M. Donald MacLaren Internal Sorting by Radix Plus Sifting 404--411
John S. Bailey Generalized Single-Ended Counters . . . 412--418
William T. Weeks Numerical Inversion of Laplace
Transforms Using Laguerre Functions . . 419--429
R. W. Hamming and
R. S. Pinkham A Class of Integration Formulas . . . . 430--438
Ivan Erdelyi On the ``Reverse Order Law'' Related to
the Generalized Inverse of Matrix
Products . . . . . . . . . . . . . . . . 439--443
D. L. Overheu An Abstract Machine for Symbolic
Computation . . . . . . . . . . . . . . 444--468
Franco Mileto and
Gianfranco Potzolu Corrigenda: ``Statistical Complexity of
Algorithms for Boolean Function
Minimization'' . . . . . . . . . . . . . 469--469
Azriel Rosenfeld and
John L. Pfaltz Sequential Operations in Digital Picture
Processing . . . . . . . . . . . . . . . 471--494
E. K. Blum A Formal System of Differentiation . . . 495--504
Edward B. Anders An Extension of Romberg Integration
Procedures to ${N}$-Variables . . . . . 505--510
Satya D. Dubey Statistical Determination of Certain
Mathematical Constants and Functions
Using Computers . . . . . . . . . . . . 511--525
Junichi Toyoda and
Yoshikazu Tezuka and
Yoshiro Kasahara Analysis of the Address Assignment
Problem for Clustered Keys . . . . . . . 526--532
F. C. Hennie and
R. E. Stearns Two-Tape Simulations of Multitape Turing
Machines . . . . . . . . . . . . . . . . 533--546
Gregory J. Chaitin On the Length of Programs for Computing
Finite Binary Sequences . . . . . . . . 547--569
Rohit J. Parikh On Context-Free Languages . . . . . . . 570--581
Sheila A. Greibach The Unsolvability of the Recognition of
Linear Context-Free Languages . . . . . 582--587
Thomas N. Hibbard and
Joseph Ullian The Independence of Inherent Ambiguity
From Complementedness Among Context-Free
Languages . . . . . . . . . . . . . . . 588--593
Philip K. Hooper The Immortality Problem for Post Normal
Systems . . . . . . . . . . . . . . . . 594--599
H. Shaw Discrete Analogs for Continuous Filters 600--604
C. D. Negron Digital One-Third Octave Spectral
Analysis . . . . . . . . . . . . . . . . 605--614
J. S. Mamelak The Placement of Computer Logic Modules 615--629
Alan J. Perlis The Synthesis of Algorithmic Systems . . 1--9
Marvin C. Wunderlich Sieving Procedures on a Digital Computer 10--19
P. A. W. Lewis and
P. B. Baxendale and
J. L. Bennett Statistical Discrimination of the
Synonymy/Antonymy Relationship Between
Words . . . . . . . . . . . . . . . . . 20--44
Carl H. Brans A Computer Program for the Nonnumerical
Testing and Reduction of Sets of
Algebraic Partial Differential Equations 45--62
Bruce A. Chartres and
James C. Geuder Computable Error Bounds for Direct
Solution of Linear Equations . . . . . . 63--71
G. W. Stewart III A Modification of Davidon's Minimization
Method to Accept Difference
Approximations to Derivatives . . . . . 72--83
John C. Butcher A Multistep Generalization of
Runge-Kutta Methods With Four or Five
Stages . . . . . . . . . . . . . . . . . 84--99
R. R. Coveyou and
R. D. MacPherson Fourier Analysis of Uniform Random
Number Generators . . . . . . . . . . . 100--119
Tzay Y. Young Binomial-Weighted Orthogonal Polynomials 120--127
George E. Collins Subresultants and Reduced Polynomial
Remainder Sequences . . . . . . . . . . 128--142
Brian Shaw Modified Multistep Methods Based on a
Nonpolynomial Interpolant . . . . . . . 143--154
J. J. Kohfeld and
G. T. Thompson Multistep Methods With Modified
Predictors and Correctors . . . . . . . 155--166
Ann Yasuhara A Remark on Post Normal Systems . . . . 167--171
Seymour Ginsburg and
Sheila A. Greibach and
Michael A. Harrison Stack Automata and Compiling . . . . . . 172--201
Robert C. Minnick Survey of Microcellular Research . . . . 203--241
Leonard Kleinrock Time-shared Systems: A Theoretical
Treatment . . . . . . . . . . . . . . . 242--261
Jack E. Shemer Some Mathematical Considerations of
Time-Sharing Scheduling Algorithms . . . 262--272
J. T. Chu and
J. C. Chueh Error Probability in Decision Functions
for Character Recognition . . . . . . . 273--280
David Martin and
Gerald Estrin Models of Computations and
Systems---Evaluation of Vertex
Probabilities in Graph Models of
Computations . . . . . . . . . . . . . . 281--299
William M. Waite Path Detection in Multidimensional
Iterative Arrays . . . . . . . . . . . . 300--310
J. B. Moore A Convergent Algorithm for Solving
Polynomial Equations . . . . . . . . . . 311--315
Cleve B. Moler Iterative Refinement in Floating Point 316--321
Manuel Blum A Machine-Independent Theory of the
Complexity of Recursive Functions . . . 322--336
W. J. Westlake A Uniform Random Number Generator Based
on the Combination of Two Congruential
Generators . . . . . . . . . . . . . . . 337--340
O. G. Mancino Resolution by Iteration of Some
Nonlinear Systems . . . . . . . . . . . 341--350
Fred T. Krogh A Test for Instability in the Numerical
Solution of Ordinary Differential
Equations . . . . . . . . . . . . . . . 351--354
A. Ginzburg A Procedure for Checking Equality of
Regular Expressions . . . . . . . . . . 355--362
C. W. Cryer On the Numerical Solution of a
Quasi-Linear Elliptic Equation . . . . . 363--375
Alan Natapoff Irreducible Topological Components of an
Arbitrary Boolean Truth Function and
Generation of Their Minimal Coverings 376--381
H. E. Pickett Note Concerning the Algebraic Theory of
Automata . . . . . . . . . . . . . . . . 382--388
Seymour Ginsburg and
Sheila A. Greibach and
Michael A. Harrison One-Way Stack Automata . . . . . . . . . 389--418
J. M. S. Simões Pereira Corrigendum: ``On the Boolean Matrix
Equation $M'=\vee_{i=1}M^i$'' . . . . . 419--420
G. P. Weeg Corrigendum: ``The Automorphism Group of
the Direct Product of Strongly Related
Automata'' . . . . . . . . . . . . . . . 421--421
D. P. Gaver, Jr. Probability Models for Multiprogramming
Computer Systems . . . . . . . . . . . . 423--438
G. K. Manacher Production and Stabilization of
Real-Time Task Schedules . . . . . . . . 439--465
J. A. Brzozowski Roots of Star Events . . . . . . . . . . 466--477
Richard M. Karp Some Bounds on the Storage Requirements
of Sequential Machines and Turing
Machines . . . . . . . . . . . . . . . . 478--489
Robert McNaughton Parenthesis Grammars . . . . . . . . . . 490--500
Daniel J. Rosenkrantz Matrix Equations and Normal Forms for
Context-Free Grammars . . . . . . . . . 501--507
I. Oliver Analysis of Factorial Experiments Using
Generalized Matrix Operations . . . . . 508--519
Victor Klee A Method for Constructing Circuit Codes 520--528
Frederic J. Mowle An Algorithm for Generating Stable
Feedback Shift Registers of Order $n$ 529--542
J. L. Rigal and
J. Gaches On the Compatibility of a Given Solution
With the Data of a Linear System . . . . 543--548
J. S. Hicks and
J. Wei Numerical Solution of Parabolic Partial
Differential Equations With Two-Point
Boundary Conditions by Use of the Method
of Lines . . . . . . . . . . . . . . . . 549--562
Richard M. Karp and
Raymond E. Miller and
Shmuel Winograd The Organization of Computations for
Uniform Recurrence Relations . . . . . . 563--590
A. B. Carroll and
R. T. Wetherald Applications of Parallel Processing to
Numerical Weather Prediction . . . . . . 591--614
Donald E. Knuth and
Richard H. Bigelow Programming Languages for Automata . . . 615--635
Robert W. Floyd Nondeterministic Algorithms . . . . . . 636--644
Arnold L. Rosenberg Real-Time Definable Languages . . . . . 645--662
J. Hartmanis On Memory Requirements for Context-Free
Language Recognition . . . . . . . . . . 663--665
Arthur Gill and
J. Robert Flexer Periodic Decomposition of Sequential
Machines . . . . . . . . . . . . . . . . 666--676
Stål Aanderaa and
Patrick C. Fischer The Solvability of the Halting Problem
for $2$-State Post Machines . . . . . . 677--682
Bruce H. Barnes and
John M. Fitzgerald Minimal Experiments for
Input-Independent Machines . . . . . . . 683--686
James R. Slagle Automatic Theorem Proving with Renamable
and Semantic Resolution . . . . . . . . 687--697
Lawrence Wos and
George A. Robinson and
Daniel F. Carson and
Leon Shalla The Concept of Demodulation in Theorem
Proving . . . . . . . . . . . . . . . . 698--709
Robert A. Fairthorne Morphology of ``Information Flow'' . . . 710--719
Marvin B. Shapiro An Algorithm for Reconstructing Protein
and RNA Sequences . . . . . . . . . . . 720--731
V. G. Sigillito On a Continuous Method of Approximating
Solutions of the Heat Equation . . . . . 732--741
Lewis T. Reinwald and
Richard M. Soland Conversion of Limited-Entry Decision
Tables to Optimal Computer Programs II:
Minimum Storage Requirement . . . . . . 742--756
Marshall C. Pease Matrix Inversion Using Parallel
Processing . . . . . . . . . . . . . . . 757--764
P. L. Odell and
H. P. Decell On Computing the Fixed-Point Probability
Vector of Ergodic Transition Matrices 765--768
D. G. Brush and
J. J. Kohfeld and
G. T. Thompson Solution of Ordinary Differential
Equations Using Two ``Off-Step'' Points 769--784
A. Van Gelder Some New Results in Pseudo-Random Number
Generation . . . . . . . . . . . . . . . 785--792
S. Winograd On the Time Required to Perform
Multiplication . . . . . . . . . . . . . 793--802
Maurice V. Wilkes Computers Then and Now . . . . . . . . . 1--7
G. Salton and
M. E. Lesk Computer Evaluation of Indexing and Text
Processing . . . . . . . . . . . . . . . 8--36
Niklaus Wirth PL360, A Programming Language for the
360 Computers . . . . . . . . . . . . . 37--74
Robert E. Echols and
Leon Cooper Solution of Integer Linear Programming
Problems by Direct Search . . . . . . . 75--84
James R. Slagle and
Philip Bursky Experiments With a Multipurpose,
Theorem-Proving Heuristic Program . . . 85--99
Otto Neall Strand and
Ed R. Westwater Statistical Estimation of the Numerical
Solution of a Fredholm Integral Equation
of the First Kind . . . . . . . . . . . 100--114
H. Dubner and
J. Abate Numerical Inversion of Laplace
Transforms by Relating Them to the
Finite Fourier Cosine Transform . . . . 115--123
Donald M. Kaplan Some Completeness Results in the
Mathematical Theory of Computation . . . 124--134
Zamir Bavel Structure and Transition-Preserving
Functions of Finite Automata . . . . . . 135--158
Abraham Waksman A Permutation Network . . . . . . . . . 159--163
J. Sklansky and
M. Finkelstein and
E. C. Russell A Formalism for Program Translation . . 165--175
P. A. Gilmore Structuring of Parallel Algorithms . . . 176--192
B. Kubert and
J. Szabo and
S. Guilieri The Perspective Representation of
Functions of Two Variables . . . . . . . 193--204
Stephen P. Morse A Mathematical Model for the Analysis of
Contour-Line Data . . . . . . . . . . . 205--220
A. Orden and
V. Nalbandian A Bidirectional Simplex Algorithm . . . 221--235
Donald W. Loveland Mechanical Theorem-Proving by Model
Elimination . . . . . . . . . . . . . . 236--251
Marshall C. Pease An Adaptation of the Fast Fourier
Transform for Parallel Processing . . . 252--264
Frank J. Zeleznik Quasi-Newton Methods for Nonlinear
Equations . . . . . . . . . . . . . . . 265--271
Gerald L. Morris and
Patrick L. Odell Common Solutions for $n$ Matrix
Equations With Applications . . . . . . 272--274
Oliver Aberth Analysis in the Computable Number Field 275--299
Marcel Paul Schützenberger A Remark on Acceptable Sets of Numbers 300--303
Raymond T. Yeh Generalized Pair Algebra With
Applications to Automata Theory . . . . 304--316
J. E. Hopcroft and
J. D. Ullman Decidable and Undecidable Questions
About Automata . . . . . . . . . . . . . 317--324
J. Hartmanis Computational Complexity of One-Tape
Turing Machine Computations . . . . . . 325--339
Abraham Waksman Corrigendum: ``A Permutation Network'' 340--340
E. G. Coffman, Jr. Analysis of Two Time-Sharing Algorithms
Designed for Limited Swapping . . . . . 341--353
Paul G. Comba A Procedure for Detecting Intersections
of Three-Dimensional Objects . . . . . . 354--366
Peter B. Andrews Resolution With Merging . . . . . . . . 367--381
J. Hartmanis and
H. Shank On the Recognition of Primes by Automata 382--389
J. J. Kohfeld and
G. T. Thompson A Modification of Nordsieck's method
Using an ``Off-Step'' Point . . . . . . 390--401
Gerhard Zielke Inversion of Modified Symmetric Matrices 402--408
T. V. Griffiths The Unsolvability of the Equivalence
Problem for ${\Lambda}$-Free
Nondeterministic Generalized Machines 409--413
John E. Hopcroft and
Jeffrey D. Ullman Relations Between Time and Tape
Complexities . . . . . . . . . . . . . . 414--427
Seymour Ginsburg and
Michael A. Harrison One-Way Nondeterministic Real-Time
List-Storage Languages . . . . . . . . . 428--446
B. A. Chartres and
J. J. Florentin A Universal Syntax-Directed Top-Down
Analyzer . . . . . . . . . . . . . . . . 447--464
P. M. Lewis II and
R. E. Stearns Syntax-Directed Transduction . . . . . . 465--488
Niklaus Wirth Corrigendum: ``PL360, A Programming
Language for the 360 Computers'' . . . . 489--489
Anonymous Contributions to the Journal of the
Association for Computing Machinery; ACM
Author Instructions for Manuscript
Documentation Unit; Categories of the
Computing Sciences . . . . . . . . . . . 490--492
C. C. Gotlieb and
S. Kumar Semantic Clustering of Index Terms . . . 493--513
Donald R. Morrison PATRICIA--Practical Algorithm To
Retrieve Information Coded in
Alphanumeric . . . . . . . . . . . . . . 514--534
Thomas C. Lowe The Influence of Data Base
Characteristics and Usage on Direct
Access File Organization . . . . . . . . 535--548
Edward G. Coffman and
Leonard Kleinrock Feedback Queueing Models for Time-Shared
Systems . . . . . . . . . . . . . . . . 549--576
Joseph Abate and
Harvey Dubner and
Sheldon B. Weinberg Queueing Analysis of the IBM 2314 Disk
Storage Facility . . . . . . . . . . . . 577--589
Raymond Reiter Scheduling Parallel Computations . . . . 590--599
U. Montanari A Method for Obtaining Skeletons Using a
Quasi-Euclidean Distance . . . . . . . . 600--624
J. R. Quinlan and
E. B. Hunt A Formal Deductive Problem-Solving
System . . . . . . . . . . . . . . . . . 625--646
Alfred V. Aho Indexed Grammars --- An Extension of
Context-Free Grammars . . . . . . . . . 647--671
Arnold L. Rosenberg On the Independence of Real-Time
Definability and Certain Structural
Properties of Context-Free Languages . . 672--679
Dennis F. Cudia and
Wilson E. Singletary Degrees of Unsolvability in Formal
Grammars . . . . . . . . . . . . . . . . 680--692
Amar Mukhopadhyay Representation of Events in the von
Neumann Cellular Model . . . . . . . . . 693--705
Abbas I. Abdel Karim A Theorem for the Stability of General
Predictor-Corrector Methods for the
Solution of Systems of Differential
Equations . . . . . . . . . . . . . . . 706--711
James Dyer Generalized Multistep Methods in
Satellite Orbit Computation . . . . . . 712--719
Peter B. Andrews A Correction Concerning Resolution . . . 720--720
G. Salton A Policy for JACM . . . . . . . . . . . 1--2
R. W. Hamming One Man's View of Computer Science . . . 3--12
W. S. Brown and
J. F. Traub MERCURY: A System for the Computer-Aided
Distribution of Technical Reports . . . 13--25
Manfred Kochen Automatic Question-Answering of
English-Like Questions About Simple
Diagrams . . . . . . . . . . . . . . . . 26--48
J. R. Guard and
F. C. Oglesby and
J. H. Bennett and
L. G. Settle Semi-Automated Mathematics . . . . . . . 49--62
H. H. Trauboth Recursive Formulas for the Evaluation of
the Convolution Integral . . . . . . . . 63--72
E. G. Coffman, Jr. Analysis of a Drum Input/Output Queue
Under Scheduled Operation in a Paged
Computer System . . . . . . . . . . . . 73--90
Sheila A. Greibach An Infinite Hierarchy of Context-Free
Languages . . . . . . . . . . . . . . . 91--106
Daniel J. Rosenkrantz Programmed Grammars and Classes of
Formal Languages . . . . . . . . . . . . 107--131
J. A. Brzozowski and
Rina Cohen On Decompositions of Regular Events . . 132--144
Gregory J. Chaitin On the Length of Programs for Computing
Finite Binary Sequences: Statistical
Considerations . . . . . . . . . . . . . 145--159
J. Hartmanis On the Complexity of Undecidable
Problems in Automata Theory . . . . . . 160--167
J. E. Hopcroft and
J. D. Ullman Some Results on Tape-Bounded Turing
Machines . . . . . . . . . . . . . . . . 168--177
Abraham Waksman A Model of Replication . . . . . . . . . 178--188
James H. Slagle and
John K. Dixon Experiments With Some Programs That
Search Game Trees . . . . . . . . . . . 189--207
Jerzy W. Grzymala-Busse Automorphisms of Polyadic Automata . . . 208--219
Albert R. Meyer A Note on Star-Free Events . . . . . . . 220--225
B. G. Reynolds and
W. F. Cutlip Synchronization and General Repetitive
Machines, with Applications to Ultimate
Definite Automata . . . . . . . . . . . 226--234
Philip M. Spira The Time Required for Group
Multiplication . . . . . . . . . . . . . 235--243
Zohar Manna Properties of Programs and the
First-Order Predicate Calculus . . . . . 244--255
Herman A. Maurer A Direct Proof of the Inherent Ambiguity
of a Simple Context-Free Language . . . 256--260
Peter Wegner Translation Networks and Function
Composition . . . . . . . . . . . . . . 261--263
H. P. Edmundson New Methods in Automatic Extracting . . 264--285
Gerald Berman Lattice Approximations to the Minima of
Functions of Several Variables . . . . . 286--294
Peter Linz Linear Multistep Methods for Volterra
Integro-Differential Equations . . . . . 295--301
Marshall C. Pease Inversion of Matrices by Partitioning 302--314
I. Adiri and
B. Avi-Itzhak A Time-Sharing Queue with a Finite
Number of Customers . . . . . . . . . . 315--323
Robert A. Di Paola The Recursive Unsolvability of the
Decision Problem for the Class of
Definite Formulas . . . . . . . . . . . 324--327
Paul R. Young Toward a Theory of Enumerations . . . . 328--348
D. W. Loveland A Simplified Format for the Model
Elimination Theorem-Proving Procedure 349--363
Erik J. Sandewall A Planning Problem Solver Based on
Look-Ahead in Stochastic Game Trees . . 364--382
Alfred V. Aho Nested Stack Automata . . . . . . . . . 383--406
Gregory J. Chaitin On the Simplicity and Speed of Programs
for Computing Infinite Sets of Natural
Numbers . . . . . . . . . . . . . . . . 407--422
T. Kasami and
K. Torii A Syntax-Analysis Procedure for
Unambiguous Context-Free Grammars . . . 423--431
Jerzy W. Grzymala-Busse On the Periodic Representations and the
Reducibility of Periodic Automata . . . 432--441
C. L. Liu Lattice Functions, Pair Algebras, and
Finite-State Machines . . . . . . . . . 442--454
Dennis M. Moyles and
Gerald L. Thompson An Algorithm for Finding a Minimum
Equivalent Graph of a Digraph . . . . . 455--460
I. S. Reed and
Rein Turn A Generalization of Shift-Register
Sequence Generators . . . . . . . . . . 461--473
Marshall C. Pease Organization of Large Scale Fourier
Processors . . . . . . . . . . . . . . . 474--482
J. N. Lyness Notes on the Adaptive Simpson Quadrature
Routine . . . . . . . . . . . . . . . . 483--495
H. S. Rahme A New Look at the Numerical Integration
of Ordinary Differential Equations . . . 496--506
A. Tal On Monotone Decomposable Operators . . . 507--510
Tamio Shimizu A Stochastic Approximation Method for
Optimization Problems . . . . . . . . . 511--516
George W. Ernst Sufficient Conditions for the Success of
GPS . . . . . . . . . . . . . . . . . . 517--533
Ugo Montanari Continuous Skeletons from Digitized
Images . . . . . . . . . . . . . . . . . 534--549
J. D. Ullman Halting Stack Automata . . . . . . . . . 550--563
Norman E. Gibbs A Cycle Generation Algorithm for Finite
Undirected Linear Graphs . . . . . . . . 564--568
S. P. Ghosh and
M. E. Senko File Organization: On the Selection of
Random Access Index Points for
Sequential Files . . . . . . . . . . . . 569--579
Georghios Loizou Nonnormality and Jordan Condition
Numbers of Matrices . . . . . . . . . . 580--584
A. Zafarullah Finite Difference Scheme for a Third
Boundary Value Problem . . . . . . . . . 585--591
Shalhav Zohar Toeplitz Matrix Inversion: The Algorithm
of W. F. Trench . . . . . . . . . . . . 592--601
H. Frank Analysis and Optimization of Disk
Storage Devices for Time-Sharing Systems 602--620
Robert A. Di Paola Random Sets in Subrecursive Hierarchies 621--630
Igal Adiri Computer Time-Sharing Queues with
Priorities . . . . . . . . . . . . . . . 631--645
E. G. Coffman, Jr. Errata: ``Analysis of a Drum
Input/Output Queue Under Scheduled
Operation in a Paged Computer System'' 646--646
Jerzy W. Grzymala-Busse Errata: ``Automorphisms of Polyadic
Automata'' . . . . . . . . . . . . . . . 646--646
Donald W. Loveland Errata: ``Mechanical Theorem-Proving by
Model Elimination'' . . . . . . . . . . 646--646
G. Salton On the Role of the ACM Journal . . . . . 1--2
Seymour Ginsburg and
John Hopcroft Two-Way Balloon Automata and AFL . . . . 3--13
Alain Colmerauer Total Precedence Relations . . . . . . . 14--30
Dennis F. Cudia General Problems of Formal Grammars . . 31--43
Arnold L. Rosenberg A Note on Ambiguity of Context-Free
Languages and Presentations of
Semilinear Sets . . . . . . . . . . . . 44--50
D. G. Corneil and
C. C. Gotlieb An Efficient Algorithm for Graph
Isomorphism . . . . . . . . . . . . . . 51--64
Herbert M. Gurk and
Jack Minker Storage Requirements for Information
Handling Centers . . . . . . . . . . . . 65--77
Donald R. Chand and
Sham S. Kapur An Algorithm for Convex Polytopes . . . 78--86
F. G. Gustavson and
W. Liniger and
R. Willoughby Symbolic Generation of an Optimal Crout
Algorithm for Sparse Systems of Linear
Equations . . . . . . . . . . . . . . . 87--109
C. D. Meyer and
R. J. Painter Note on a Least Squares Inverse for a
Matrix . . . . . . . . . . . . . . . . . 110--112
S. K. Chang and
A. Gill Algorithmic Solution of the
Change-Making Problem . . . . . . . . . 113--122
E. G. Coffman, Jr. and
R. R. Muntz and
H. Trotter Waiting Time Distributions for
Processor-Sharing Systems . . . . . . . 123--130
Philip J. Rasch A Queueing Theory Study of Round-Robin
Scheduling of Time-Shared Computer
Systems . . . . . . . . . . . . . . . . 131--145
Azriel Rosenfeld Connectivity in Digital Pictures . . . . 146--160
J. Sklansky Thresholded Convolution Operations . . . 161--165
M. A. Breuer Simplification of the Covering Problem
with Application to Boolean Expressions 166--181
Harold S. Stone An Algorithm for Modular Partitioning 182--195
Marvin L. Minsky Form and Content in Computer Science . . 197--215
Arthur J. Nevins A Programming Language with Automatic
Goal Generation and Selection . . . . . 216--230
Zamir Bavel and
David E. Muller Connectivity and Reversibility in
Automata . . . . . . . . . . . . . . . . 231--240
David G. Willis Computational Complexity and Probability
Constructions . . . . . . . . . . . . . 241--259
H. C. Andrews and
J. Kane Kronecker Matrices, Computer
Implementation, and Generalized Spectra 260--268
Seymour Haber Sequences of Numbers That Are
Approximately Completely Equidistributed 269--272
Peter Henrici Methods of Search for Solving Polynomial
Equations . . . . . . . . . . . . . . . 273--283
H. S. Rahme Stability Analysis of a New Algorithm
Used for Integrating a System of
Ordinary Differential Equations . . . . 284--293
A. Zafarullah Application of the Method of Lines to
Parabolic Partial Differential Equations
with Error Estimates . . . . . . . . . . 294--302
Richard H. Roth An Approach to Solving Linear Discrete
Optimization Problems . . . . . . . . . 303--313
L. E. N. Delbrouck A Feedback Queueing System with Batch
Arrivals, Bulk Service, and
Queue-Dependent Service Time . . . . . . 314--323
R. R. Muntz and
E. G. Coffman, Jr. Preemptive Scheduling of Real-Time Tasks
on Multiprocessor Systems . . . . . . . 324--338
Louis Hodes The Logical Complexity of Geometric
Properties in the Plane . . . . . . . . 339--347
G. Ugo Montanari On Limit Properties in Digitization
Schemes . . . . . . . . . . . . . . . . 348--360
J. M. Boyle and
A. A. Grau An Algorithmic Semantics for ALGOL 60
Identifier Denotation . . . . . . . . . 361--382
B. L. Fox Accelerating List Processing in Discrete
Programming . . . . . . . . . . . . . . 383--384
B. F. Caviness On Canonical Forms and Simplification 385--396
H. H. Kagiwada and
R. Kalaba An Initial-Value Theory for Fredholm
Integral Equations with Semidegenerate
Kernels . . . . . . . . . . . . . . . . 412--419
Takao Tsuda and
Kozo Ichida Nonlinear Interpolation of Multivariable
Functions by the Monte Carlo Method . . 420--425
C. W. Cryer On the Approximate Solution of Free
Boundary Problems Using Finite
Differences . . . . . . . . . . . . . . 397--411
C. V. Ramamoorthy and
K. M. Chandy Optimization of Memory Hierarchies in
Multiprogrammed Systems . . . . . . . . 426--445
Richard I. Shrager Nonlinear Regression With Linear
Constraints: An Extension of the
Magnified Diagonal Method . . . . . . . 446--452
Alan C. Shaw Parsing of Graph-Representable Pictures 453--481
H. Lynn Beus The Use of Information in Sorting . . . 482--495
W. D. Frazer and
A. C. McKellar Samplesort: A Sampling Approach to
Minimal Storage Tree Sorting . . . . . . 496--507
Larry E. Stanfel Tree Structures for Optimal Searching 508--517
Frederic J. Mowle Controllability of Nonlinear Sequential
Networks . . . . . . . . . . . . . . . . 518--524
Robert Anderson and
W. W. Bledsoe A Linear Format for Resolution With
Merging and a New Technique for
Establishing Completeness . . . . . . . 525--534
James R. Slagle Interpolation Theorems for Resolution in
Lower Predicate Calculus . . . . . . . . 535--542
J. L. Baer and
D. P. Bovet and
G. Estrin Legality and Other Properties of Graph
Models of Computations . . . . . . . . . 543--554
Zohar Manna and
Amir Pnueli Formalization of Properties of
Functional Programs . . . . . . . . . . 555--569
J. Gary Augustson and
Mack Minker An Analysis of Some Graph Theoretical
Cluster Techniques . . . . . . . . . . . 571--588
Hiroshi Akima A New Method of Interpolation and Smooth
Curve Fitting Based on Local Procedures 589--602
Donald I. Good and
Ralph L. London Computer Interval Arithmetic: Definition
and Proof of Correct Implementation . . 603--612
William B. Gruttke Pseudo-Runge-Kutta Methods of the Fifth
Order . . . . . . . . . . . . . . . . . 613--628
Masahiro Hashimoto A Method for Solving Large Matrix
Equations Reduced from Fredholm Integral
Equations of the Second Kind . . . . . . 629--636
Toyohisa Kaneko and
Bede Liu Accumulation of Round-off Error in Fast
Fourier Transforms . . . . . . . . . . . 637--654
L. F. Shampine Efficiency of a Procedure for
Near-Minimax Approximation . . . . . . . 655--660
Brian T. Smith Error Bounds for Zeros of a Polynomial
Based Upon Gerschgorin's Theorems . . . 661--674
P. Bonzon Necessary and Sufficient Conditions for
Dynamic Programming of Combinatorial
Type . . . . . . . . . . . . . . . . . . 675--682
Paul W. Purdom, Jr. and
Stephen M. Stigler Statistical Properties of the Buddy
System . . . . . . . . . . . . . . . . . 683--697
C. L. Chang The Unit Proof and the Input Proof in
Theorem Proving . . . . . . . . . . . . 698--707
David Pager On the Efficiency of Algorithms . . . . 708--714
Ravi Sethi and
J. D. Ullman The Generation of Optimal Code for
Arithmetic Expressions . . . . . . . . . 715--728
D. Tsichritzis The Equivalence Problem of Simple
Programs . . . . . . . . . . . . . . . . 729--738
Jerzy W. Grzymala-Busse Errata: ``On the Periodic
Representations and the Reducibility of
Periodic Automata'' . . . . . . . . . . 739--739
G. Salton Editorial: Some Thoughts on Scientific
Information Dissemination . . . . . . . 1--3
Stephen A. Cook Characterizations of Pushdown Machines
in Terms of Time-Bounded Computers . . . 4--18
William H. Kautz An Augmented Content-Addressed Memory
Array for Implementation with
Large-Scale Integration . . . . . . . . 19--33
Brian W. Kernighan Optimal Sequential Partitions of Graphs 34--40
Nabih N. Abdelmalek Linear ${L}_1$ Approximation for a
Discrete Point Set and ${L}_1$ Solutions
of Overdetermined Linear Equations . . . 41--47
N. F. Benschop and
H. C. Ratz A Mean Square Estimate of the Generated
Roundoff Error in Constant Matrix
Iterative Processes . . . . . . . . . . 48--62
Colin W. Cryer Topological Problems Arising When
Solving Boundary Value Problems for
Elliptic Partial Differential Equations
by the Method of Finite Differences . . 63--74
C. Dill and
C. W. Gear A Graphical Search for Stiffly Stable
Methods for Ordinary Differential
Equations . . . . . . . . . . . . . . . 75--79
Alfred V. Aho and
Peter J. Denning and
Jeffrey D. Ullman Principles of Optimal Page Replacement 80--93
G. C. Philippatos and
D. R. Moscato Effects of Constrained Information on
Player Decisions in Experimental
Business Simulation: Some Empirical
Evidence . . . . . . . . . . . . . . . . 94--104
J. C. Alexander and
A. I. Thaler The Boundary Count of Digital Pictures 105--112
Manfred H. Hueckel An Operator Which Locates Edges in
Digitized Pictures . . . . . . . . . . . 113--125
C. L. Chang and
J. R. Slagle Completeness of Linear Refutation for
Theories with Equality . . . . . . . . . 126--136
Michael A. Harrison and
Mario Schkolnick A Grammatical Characterization of
One-Way Nondeterministic Stack Languages 148--172
William Goffman A Mathematical Method for Analyzing the
Growth of a Scientific Discipline . . . 173--185
Donald P. Gaver, Jr. and
Peter A. W. Lewis Probability Models for Buffer Storage
Allocation Problems . . . . . . . . . . 186--198
P. A. W. Lewis and
G. S. Shedler A Cyclic-Queue Model of System Overhead
in Multiprogrammed Computer Systems . . 199--220
J. H. Wilkinson Some Comments from a Numerical Analyst 137--147
U. Narayan Bhat and
Richard E. Nance Busy Period Analysis of a Time-Sharing
System Modeled as a Semi-Markov Process 221--238
J. P. Mylopoulos and
T. Pavlidis On the Topological Properties of
Quantized Spaces. I. The Notion of
Dimension . . . . . . . . . . . . . . . 239--246
J. P. Mylopoulos and
T. Pavlidis On the Topological Properties of
Quantized Spaces. II. Connectivity and
Order of Connectivity . . . . . . . . . 247--254
R. Steffanelli and
A. Rosenfeld Some Parallel Thinning Algorithms for
Digital Pictures . . . . . . . . . . . . 255--264
Robert O. Winder Chow Parameters in Threshold Logic . . . 265--289
Manuel Blum On Effective Procedures for Speeding Up
Algorithms . . . . . . . . . . . . . . . 290--305
Stephen N. Cole Deterministic Pushdown Store Machines
and Real-Time Computation . . . . . . . 306--328
John Case A Note on Degrees of Self-Describing
Turing Machines . . . . . . . . . . . . 329--338
Alvy Ray Smith III Simple Computation-Universal Cellular
Spaces . . . . . . . . . . . . . . . . . 339--353
Richard Simon and
Richard C. T. Lee On the Optimal Solutions to AND/OR
Series-Parallel Graphs . . . . . . . . . 354--372
M. S. Mock Numerical Analysis of a Nonlinear
Diffusion Problem . . . . . . . . . . . 373--380
J. P. R. Tootill and
W. D. Robinson and
A. G. Adams The Runs Up-and-Down Performance of
Tausworthe Pseudo-Random Number
Generators . . . . . . . . . . . . . . . 381--399
William H. Burge and
Alan G. Konheim An Accessing Model . . . . . . . . . . . 400--404
Donald P. Gaver Analysis of Remote Terminal Backlogs
under Heavy Demand Conditions . . . . . 405--415
J. M. Robson An Estimate of the Store Size Necessary
for Dynamic Storage Allocation . . . . . 416--423
John Lions Some Results Concerning the Reduction of
Binary Matrices . . . . . . . . . . . . 424--430
Ronald C. de Vries Minimal Sets of Distinct Literals for a
Logically Passive Function . . . . . . . 431--443
J. Hartmanis and
J. E. Hopcroft An Overview of the Theory of
Computational Complexity . . . . . . . . 444--476
G. Salton Introduction . . . . . . . . . . . . . . 477--477
W. S. Brown On Euclid's Algorithm and the
Computation of Polynomial Greatest
Common Divisors . . . . . . . . . . . . 478--504
W. S. Brown and
J. F. Traub On Euclid's Algorithm and the Theory of
Subresultants . . . . . . . . . . . . . 505--514
George E. Collins The Calculation of Multivariate
Polynomial Resultants . . . . . . . . . 515--532
Lee E. Heindel Integer Arithmetic Algorithms for
Polynomial Real Zero Determination . . . 533--548
William A. Martin Determining the Equivalence of Algebraic
Expressions by Hash Coding . . . . . . . 549--558
S. C. Johnson On the Problem of Recognizing Zero . . . 559--565
James R. Bunch Equilibration of Symmetric Matrices in
the Max-Norm . . . . . . . . . . . . . . 566--572
Donald J. Rose A Note on Consistent Ordering and Zero
Circulation . . . . . . . . . . . . . . 573--575
M. A. Kaplan and
R. A. Papetti A Note on Quadrilateral Interpolation 576--585
C. S. Smith Multiplicative Pseudo-Random Number
Generators with Prime Modulus . . . . . 586--593
E. Wasserstrom Solving Boundary-Value Problems by
Imbedding . . . . . . . . . . . . . . . 594--602
Igal Adiri A Dynamic Time-Sharing Priority Queue 603--610
Igal Adiri A Note on Some Mathematical Models of
Time-Sharing Systems . . . . . . . . . . 611--615
K. B. Irani and
V. L. Wallace On Network Linguistics and the
Conversational Design of Queueing
Networks . . . . . . . . . . . . . . . . 616--629
Raymond Reiter Two Results on Ordering for Resolution
with Merging and Linear Format . . . . . 630--646
G. Salton Editorial: What Is Computer Science? . . 1--2
A. C. Fleck and
S. T. Hedetniemi and
R. H. Oehmke \cal S-Semigroups of Automata . . . . . 3--10
T. Pavlidis Linear and Context-Free Graph Grammars 11--22
C. P. Earnest and
K. G. Balke and
J. Anderson Analysis of Graphs by Ordering of Nodes 23--42
Herbert Weinblatt A New Search Algorithm for Finding the
Simple Cycles of a Finite Directed Graph 43--56
Y. E. Chen and
D. L. Epley Memory Requirements in a Multiprocessing
Environment . . . . . . . . . . . . . . 57--69
Harry C. Heacox, Jr. and
Paul W. Purdom, Jr. Analysis of Two Time-Sharing Queueing
Models . . . . . . . . . . . . . . . . . 70--91
Alan G. Konheim and
Bernd Meister Service in a Loop System . . . . . . . . 92--108
Richard C. T. Lee Fuzzy Logic and the Resolution Principle 109--119
James R. Slagle Automatic Theorem Proving with Built-in
Theories Including Equality, Partial
Ordering, and Sets . . . . . . . . . . . 120--135
Andrzej Blikle Addressless Units for Carrying Out
Loop-Free Computations . . . . . . . . . 136--157
A. Borodin Computational Complexity and the
Existence of Complexity Gaps . . . . . . 158--174
Robert L. Constable The Operator Gap . . . . . . . . . . . . 175--183
Norman Zadeh Theoretical Efficiency of the
Edmonds-Karp Algorithm for Computing
Maximal Flows . . . . . . . . . . . . . 184--192
Sheila Greibach and
Seymour Ginsburg Multitape AFA . . . . . . . . . . . . . 193--221
Eugene S. Santos A Note on Bracketed Grammars . . . . . . 222--224
A. V. Aho and
P. J. Denning and
J. D. Ullman Weak and Mixed Strategy Precedence
Parsing . . . . . . . . . . . . . . . . 225--243
Gordon D. Mulligan and
D. G. Corneil Corrections to Bierstone's Algorithm for
Generating Cliques . . . . . . . . . . . 244--247
Jack Edmonds and
Richard M. Karp Theoretical Improvements in Algorithmic
Efficiency for Network Flow Problems . . 248--264
Peter L. Hammer and
Uri N. Peled On the Maximization of a Pseudo-Boolean
Function . . . . . . . . . . . . . . . . 265--282
Stanley M. Selkow One-Pass Complexity of Digital Picture
Properties . . . . . . . . . . . . . . . 283--295
L. H. Landweber and
E. L. Robertson Recursive Properties of Abstract
Complexity Classes . . . . . . . . . . . 296--308
Arnold L. Rosenberg Addressable Data Graphs . . . . . . . . 309--340
Robert Tarjan Sorting Using Networks of Queues and
Stacks . . . . . . . . . . . . . . . . . 341--346
S. C. van Westrhenen Statistical Studies of Theoremhood in
Classical Propositional and First Order
Predicate Calculus . . . . . . . . . . . 347--365
D. W. Loveland A Unifying View of Some Linear Herbrand
Procedures . . . . . . . . . . . . . . . 366--384
J. McAfee and
L. Presser An Algorithm for the Design of Simple
Precedence Grammars . . . . . . . . . . 385--395
Clarence A. Ellis The Halting Problem for Probabilistic
Context-Free Generators . . . . . . . . 396--399
S. Even and
A. Pnueli and
A. Lempel Permutation Graphs and Transitive Graphs 400--410
John L. Pfaltz Graph Structures . . . . . . . . . . . . 411--422
Jin Y. Yen Finding the Lengths of All Shortest
Paths in ${N}$-Node Nonnegative-Distance
Complete Networks Using $1/2 {N}^3$
Additions and ${N}^3$ Comparisons . . . 423--424
L. E. Stanfel Practical Aspects of Doubly Chained
Trees for Retrieval . . . . . . . . . . 425--436
Nancy M. Huang and
Randall E. Cline Inversion of Persymmetric Matrices
Having Toeplitz Inverses . . . . . . . . 437--444
I. Mitrani Nonpriority Multiprogramming Systems
Under Heavy Demand Conditions ---
Customers' Viewpoint . . . . . . . . . . 445--452
Richard E. Nance and
U. Narayan Bhat and
Billy G. Claybrook Busy Period Analysis of a Time-Sharing
System: Transform Inversion . . . . . . 453--463
L. Kleinrock and
R. R. Muntz Processor Sharing Queueing Models of
Mixed Scheduling Disciplines for Time
Shared Systems . . . . . . . . . . . . . 464--482
Gary D. Schultz A Stochastic Model for Message Assembly
Buffering with a Comparison of Block
Assignment Strategies . . . . . . . . . 483--495
James R. Slagle An Approach for Finding ${C}$-Linear
Complete Inference Systems . . . . . . . 496--516
J. Bruno and
K. Steiglitz The Expression of Algorithms by Charts 517--525
Robert L. Constable and
Allan B. Borodin Subrecursive Programming Languages, Part
I: Efficiency and Program Structure . . 526--568
J. D. Ullman A Note on the Efficiency of Hashing
Functions . . . . . . . . . . . . . . . 569--575
A. Borodin Corrigendum: ``Computational Complexity
and the Existence of Complexity Gaps'' 576--576
Robert E. Beck and
Bernard Kolman Computer Approaches to the
Representation of Lie Algebras . . . . . 577--589
Patrick C. Fischer and
Albert R. Meyer and
Arnold L. Rosenberg Real-Time Simulation of Multihead Tape
Units . . . . . . . . . . . . . . . . . 590--607
Oscar H. Ibarra A Note Concerning Nondeterministic Tape
Complexities . . . . . . . . . . . . . . 608--612
James C. Beatty An Axiomatic Approach to Code
Optimization for Expressions . . . . . . 613--640
W. D. Frazer and
B. T. Bennett Bounds on Optimal Merge Performance, and
a Strategy for Optimality . . . . . . . 641--648
Edward M. Reingold On the Optimality of Some Set Algorithms 649--659
J. E. Savage Computational Work and Time on Finite
Machines . . . . . . . . . . . . . . . . 660--674
James N. Gray and
Michael A. Harrison On the Covering and Reduction Problems
for Context-Free Grammars . . . . . . . 675--698
Shi-Kuo Chang The Generation of Minimal Trees with a
Steiner Topology . . . . . . . . . . . . 699--711
V. Srinivasan and
G. L. Thompson Accelerated Algorithms for Labeling and
Relabeling of Trees, with Applications
to Distribution Problems . . . . . . . . 712--726
Carl M. Harris and
Paul G. Marlin A Note on Feedback Queues with Bulk
Service . . . . . . . . . . . . . . . . 727--733
A. J. Bayes A Minimum Variance Sampling Technique
for Simulation Models . . . . . . . . . 734--741
Bernard P. Zeigler Towards a Formal Theory of Modeling and
Simulation: Structure Preserving
Morphisms . . . . . . . . . . . . . . . 742--764
J. Nievergelt and
C. K. Wong Upper Bounds for the Total Path Length
of Binary Trees . . . . . . . . . . . . 1--6
Harry M. Sloate and
Theodore A. Bickart ${A}$-Stable Composite Multistep Methods 7--26
Harold S. Stone An Efficient Parallel Algorithm for the
Solution of a Tridiagonal Linear System
of Equations . . . . . . . . . . . . . . 27--38
G. J. Burnett and
E. G. Coffman, Jr. A Combinatorial Problem Related to
Interleaved Memory Systems . . . . . . . 39--45
C. L. Liu and
James W. Layland Scheduling Algorithms for
Multiprogramming in a Hard-Real-Time
Environment . . . . . . . . . . . . . . 46--61
Arnold K. Griffith Mathematical Models for Automatic Line
Detection . . . . . . . . . . . . . . . 62--80
Azriel Rosenfeld Arcs and Curves in Digital Pictures . . 81--87
Donald L. Richards Efficient Exercising of Switching
Elements in Nets of Identical Gates . . 88--111
Robert A. Di Paola The Solvability of the Decision Problem
for Classes of Proper Formulas and
Related Results . . . . . . . . . . . . 112--126
John K. Dixon ${Z}$-Resolution: Theorem-Proving with
Compiled Axioms . . . . . . . . . . . . 127--147
F. K. Hwang and
D. N. Deutsch A Class of Merging Algorithms . . . . . 148--159
Barry K. Rosen Tree-Manipulation Systems and
Church-Rosser Theorems . . . . . . . . . 160--187
James C. Beatty Errata: ``An Axiomatic Approach to Code
Optimization for Expressions'' . . . . . 188--188
Harvey M. Salkin and
Ronald D. Koncal Set Covering by an All Integer
Algorithm: Computational Experience . . 189--193
V. Srinivasan and
G. L. Thompson Benefit-Cost Analysis of Coding
Techniques for the Primal Transportation
Algorithm . . . . . . . . . . . . . . . 194--213
James N. Gray and
Michael A. Harrison Canonical Precedence Schemes . . . . . . 214--234
David Bruce Lomet A Formalization of Transition Diagram
Systems . . . . . . . . . . . . . . . . 235--257
G. Salton Recent Studies in Automatic Text
Analysis and Document Retrieval . . . . 258--278
John F. Dalphin and
Victor Lovass-Nagy Best Least Squares Solutions to Finite
Difference Equations Using the
Generalized Inverse and Tensor Product
Methods . . . . . . . . . . . . . . . . 279--289
Armin Friedli Optimal Covering Algorithms in Methods
of Search for Solving Polynomial
Equations . . . . . . . . . . . . . . . 290--300
A. J. Goldstein and
P. L. Richman A Midpoint Phenomenon . . . . . . . . . 301--304
Jacques Morgenstern Note on a Lower Bound of the Linear
Complexity of the Fast Fourier Transform 305--306
S. R. Arora and
A. Gallo Optimization of Static Loading and
Sizing of Multilevel Memory Systems . . 307--319
Donald L. Richards Efficient Exercising of Switching
Elements in Combinational Nets . . . . . 320--332
Tomasz Pietrzykowski A Complete Mechanization of Second-Order
Type Theory . . . . . . . . . . . . . . 333--364
A. T. Berztiss A Backtrack Procedure for Isomorphism of
Directed Graphs . . . . . . . . . . . . 365--377
Christopher D. Green A Path Entropy Function for Rooted Trees 378--384
Donald B. Johnson A Note on Dijkstra's Shortest Path
Algorithm . . . . . . . . . . . . . . . 385--388
Thomas A. Williams and
Gregory P. White A Note on Yen's Algorithm for Finding
the Length of All Shortest Paths in
${N}$-Node Nonnegative-Distance Networks 389--390
Toyohisa Kaneko and
Bede Liu On Local Roundoff Errors in
Floating-Point Arithmetic . . . . . . . 391--398
Webb Miller Toward Abstract Numerical Analysis . . . 399--408
G. A. Watson An Algorithm for the Inversion of Block
Matrices of Toeplitz Form . . . . . . . 409--415
Igal Adiri Cyclic Queues with Bulk Arrivals . . . . 416--428
David D. Grossman and
Harvey F. Silverman Placement of Records on a Secondary
Storage Device to Minimize Access Time 429--438
G. Tourlakis and
J. Mylopoulos Some Results in Computational Topology 439--455
T. G. Lewis and
W. G. Payne Generalized Feedback Shift Register
Pseudorandom Number Algorithm . . . . . 456--468
J. P. R. Tootill and
W. D. Robinson and
D. J. Eagle An Asymptotically Random Tausworthe
Sequence . . . . . . . . . . . . . . . . 469--481
R. B. Worrell and
B. L. Hulme Efficient Ordering of Set Expressions
for Symbolic Expansion . . . . . . . . . 482--488
Edward Ashcroft and
Zohar Manna and
Amir Pnueli Decidable Properties of Monadic
Functional Schemas . . . . . . . . . . . 489--499
Gideon Ehrlich Loopless Algorithms for Generating
Permutations, Combinations, and Other
Combinatorial Configurations . . . . . . 500--513
Robert M. Keller Parallel Program Schemata and Maximal
Parallelism I. Fundamental Results . . . 514--537
James C. Beatty Errata: ``An Axiomatic Approach to Code
Optimization for Expressions'' . . . . . 538--538
M. A. Jenkins Bernouilli's Method with Implicit
Shifting . . . . . . . . . . . . . . . . 539--544
Fred T. Krogh On Testing a Subroutine for the
Numerical Integration of Ordinary
Differential Equations . . . . . . . . . 545--562
Michael T. McClellan The Exact Solution of Systems of Linear
Equations with Polynomial Coefficients 563--588
I. Adiri and
M. Hofri and
M. Yadin A Multiprogramming Queue . . . . . . . . 589--603
C. C. Gotlieb and
G. H. MacEwen Performance of Movable-Head Disk Storage
Devices . . . . . . . . . . . . . . . . 604--623
P. C. Yue and
C. K. Wong On the Optimality of the Probability
Ranking Scheme in Storage Applications 624--633
Manfred H. Hueckel A Local Visual Operator Which Recognizes
Edges and Lines . . . . . . . . . . . . 634--647
Rona B. Stillman The Concept of Weak Substitution in
Theorem-Proving . . . . . . . . . . . . 648--667
Leonard Bass and
Paul Young Ordinal Hierarchies and Naming
Complexity Classes . . . . . . . . . . . 668--686
Robert P. Daley An Example of Information and
Computation Resource Trade-Off . . . . . 687--695
Robert M. Keller Parallel Program Schemata and Maximal
Parallelism II: Construction of Closures 696--710
David G. Herr On a Statistical Model of Strand and
Westwater for the Numerical Solution of
a Fredholm Integral Equation of the
First Kind . . . . . . . . . . . . . . . 1--5
Nai-Kuan Tsao Some a Posteriori Error Bounds in
Floating-Point Computations . . . . . . 6--17
L. W. Cotten and
A. M. Abd-Alla Processing Times for Segmented Jobs with
I/O Compute Overlap . . . . . . . . . . 18--30
P. A. Franaszek and
T. J. Wagner Some Distribution-Free Aspects of Paging
Algorithm Performance . . . . . . . . . 31--39
Giorgio Ingargiola and
James F. Korsh Finding Optimal Demand Paging Algorithms 40--53
Debasis Mitra Some Aspects of Hierarchical Memory
Systems . . . . . . . . . . . . . . . . 54--65
Kenneth C. Sevcik Scheduling for Minimum Total Loss Using
Service Time Distributions . . . . . . . 66--75
Christopher Earnest Some Topics in Code Optimization . . . . 76--102
Michael A. Crane and
Donald L. Iglehart Simulating Stable Stochastic Systems, I:
General Multiserver Queues . . . . . . . 103--113
Michael A. Crane and
Donald L. Iglehart Simulating Stable Stochastic Systems,
II: Markov Chains . . . . . . . . . . . 114--123
S. Fleisig and
D. Loveland and
A. K. Smiley III and
D. L. Yarmush An Implementation of the Model
Elimination Proof Procedure . . . . . . 124--139
Walter H. Kohler and
Kenneth Steiglitz Characterization and Theoretical
Comparison of Branch-and-Bound
Algorithms for Permutation Problems . . 140--156
P. S. Kritzinger and
J. W. Graham A Theorem in the Theory of Compromise
Merge Methods . . . . . . . . . . . . . 157--160
Mary Shaw and
J. F. Traub On the Number of Multiplications for the
Evaluation of a Polynomial and Some of
Its Derivatives . . . . . . . . . . . . 161--167
Robert A. Wagner and
Michael J. Fischer The String-to-String Correction Problem 168--173
D. Michie and
E. E. Sibert Some Binary Derivation Systems . . . . . 175--190
Ross A. Overbeek A New Class of Automated Theorem-Proving
Algorithms . . . . . . . . . . . . . . . 191--200
Richard P. Brent The Parallel Evaluation of General
Arithmetic Expressions . . . . . . . . . 201--206
David Pager Further Results on the Problem of
Finding Minimal Length Programs for
Decision Tables . . . . . . . . . . . . 207--212
Armen Gabrielian and
Seymour Ginsburg Grammar Schemata . . . . . . . . . . . . 213--226
G. Berman and
A. W. Colijn A Modified List Technique Allowing
Binary Search . . . . . . . . . . . . . 227--232
R. T. Chien and
E. A. Mark A Document Storage Method Based on
Polarized Distance . . . . . . . . . . . 233--245
Peter Elias Efficient Storage and Retrieval by
Content and Address of Static Files . . 246--260
M. M. Blevins and
G. W. Stewart Calculating the Eigenvectors of
Diagonally Dominant Matrices . . . . . . 261--271
Shalhav Zohar The Solution of a Toeplitz Set of Linear
Equations . . . . . . . . . . . . . . . 272--276
Ellis Horowitz and
Sartaj Sahni Computing Partitions with Applications
to the Knapsack Problem . . . . . . . . 277--292
William J. Gordon and
Richard F. Riesenfeld Bernstein-Bézier Methods for the
Computer-Aided Design of Free Form
Curves and Surfaces . . . . . . . . . . 293--310
Charles B. Dunham Efficiency of Chebyshev Approximation on
Finite Subsets . . . . . . . . . . . . . 311--313
E. Balkovich and
W. Chiu and
L. Presser and
R. Wood Comments on a Paper by Gaver . . . . . . 314--315
Hisashi Kobayashi Application of the Diffusion
Approximation to Queueing Networks I:
Equilibrium Queue Distributions . . . . 316--328
J. A. Michel and
E. G. Coffman, Jr. Synthesis of a Feedback Queueing
Discipline for Computer Operation . . . 329--339
Steven Katz and
Alan G. Konheim Priority Disciplines in a Loop System 340--349
Manfred H. Hueckel Erratum: ``A Local Visual Operator Which
Recognizes Edges and Lines'' . . . . . . 350--350
Ramachendra P. Batni and
Jeffrey D. Russell and
Charles R. Kime An Efficient Algorithm for Finding an
Irredundant Set Cover . . . . . . . . . 351--355
Robert M. Haralick The Diclique Representation and
Decomposition of Binary Relations . . . 356--366
M. S. Hecht and
J. D. Ullman Characterizations of Reducible Flow
Graphs . . . . . . . . . . . . . . . . . 367--375
E. M. Palmer and
M. A. Rahimi and
R. W. Robinson Efficiency of a Binary Comparison
Storage Technique . . . . . . . . . . . 376--384
Chung C. Wang An Algorithm for the Chromatic Number of
a Graph . . . . . . . . . . . . . . . . 385--391
C. K. Wong and
Don Coppersmith A Combinatorial Problem Related to
Multimodule Memory Organizations . . . . 392--402
Gregory J. Chaitin Information-Theoretic Limitations of
Formal Systems . . . . . . . . . . . . . 403--424
John Gill and
Manuel Blum On Almost Everywhere Complex Recursive
Functions . . . . . . . . . . . . . . . 425--435
L. K. Schubert Iterated Limiting Recursion and the
Program Minimization Problem . . . . . . 436--445
Thomas N. Hibbard Context-Limited Grammars . . . . . . . . 446--453
Paul L. Richman Computing a Subinterval of the Image . . 454--458
Hisashi Kobayashi Application of the Diffusion
Approximation to Queueing Networks II:
Nonequilibrium Distributions and
Applications to Computer Modeling . . . 459--469
Alan G. Konheim and
Bernd Meister Waiting Lines and Times in a System with
Polling . . . . . . . . . . . . . . . . 470--490
J. M. Robson Bounds for Some Functions Concerning
Dynamic Storage Allocation . . . . . . . 491--499
Mandell Bellmore and
Saman Hong Transformation of Multisalesmen Problem
to the Standard Traveling Salesman
Problem . . . . . . . . . . . . . . . . 500--504
L. E. Trotter, Jr. and
C. M. Shetty An Algorithm for the Bounded Variable
Integer Programming Problem . . . . . . 505--513
T. I. Fenner and
G. Loizou Some New Bounds on the Condition Numbers
of Optimally Scaled Matrices . . . . . . 514--524
Anonymous Contributions to the Journal of the
Association of Computing Machinery . . . 525--526
Michael A. Harrison and
Ivan M. Havel On the Parsing of Deterministic
Languages . . . . . . . . . . . . . . . 525--548
John Hopcroft and
Robert Tarjan Efficient Planarity Testing . . . . . . 549--568
Philippe G. H. Lehot An Optimal Algorithm to Detect a Line
Graph and Output Its Root Graph . . . . 569--575
Frank Rubin A Search Procedure for Hamilton Paths
and Circuits . . . . . . . . . . . . . . 576--580
Robert J. Plemmons Linear Least Squares by Elimination and
MGS . . . . . . . . . . . . . . . . . . 581--585
Paul S. Wang The Undecidability of the Existence of
Zeros of Real Elementary Functions . . . 586--589
L. Henschen and
L. Wos Unit Refutations and Horn Sets . . . . . 590--605
Arthur J. Nevins A Human Oriented Logic for Automatic
Theorem-Proving . . . . . . . . . . . . 606--621
James R. Slagle Automated Theorem-Proving for Theories
with Simplifiers, Commutativity, and
Associativity . . . . . . . . . . . . . 622--642
H. T. Kung and
J. F. Traub Optimal Order of One-Point and
Multipoint Iteration . . . . . . . . . . 643--651
Arnold L. Rosenberg Allocating Storage for Extendible Arrays 652--670
Ravi Sethi Testing for the Church-Rosser Property 671--679
Anthony S. Wojcik and
Gernot Metze An Analysis of Some Relationships
Between Post and Boolean Algebras . . . 680--696
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
E. Horowitz and
S. Sahni On Computing the Exact Determinant of
Matrices with Polynomial Entries . . . . 38--50
C. A. Micchelli and
W. L. Miranker High Order Search Methods for Finding
Roots . . . . . . . . . . . . . . . . . 51--60
John R. Rice A Metalgorithm for Adaptive Quadrature 61--82
Samuel H. Fuller and
Forest Baskett An Analysis of Drum Storage Units . . . 83--105
Walter H. Kohler and
Kenneth Steiglitz Exact, Approximate, and Guaranteed
Accuracy Algorithms for the Flow-Shop
Problem $n/2/{F}/{\overline 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 and
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 and
G. H. MacEwen Errata: ``Performance of Movable-Head
Disk Storage Devices'' . . . . . . . . . 172--172
Roy Lowrance and
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 and
Franco P. Preparata Bounds to Complexities of Networks for
Sorting and for Switching . . . . . . . 195--201
Y. Perl and
M. R. Garey and
S. 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 and
K. Mani Chandy and
Richard R. Muntz and
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 and
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--308
Roger C. Schank and
Neil M. Goldman and
Charles J. Rieger III and
Christopher K. Riesbeck Inference and Paraphrase by Computer . . 309--328
Gregory J. Chaitin A Theory of Program Size Formally
Identical to Information Theory . . . . 329--340
Nancy Lynch On Reducibility to Complex or Sparse
Sets . . . . . . . . . . . . . . . . . . 341--345
Glenn Manacher A New Linear-Time ``On-Line'' Algorithm
for Finding the Smallest Initial
Palindrome of a String . . . . . . . . . 346--351
S. E. Goodman and
S. T. Hedetniemi and
P. J. Slater Advances on the Hamiltonian Completion
Problem . . . . . . . . . . . . . . . . 352--360
John L. Pfaltz Representing Graphs by Knuth Trees . . . 361--366
Peter Elias and
Richard A. Flower The Complexity of Some Simple Retrieval
Problems . . . . . . . . . . . . . . . . 367--379
Robert E. Dressler and
S. Thomas Parker Primes with a Prime Subscript . . . . . 380--381
J. L. Bruno and
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 and
D. Klingman and
A. 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--424
Antonin Svoboda The Concept of Term Exclusiveness and
Its Effect on the Theory of Boolean
Functions . . . . . . . . . . . . . . . 425--440
M. C. Easton and
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 and
Chul E. Kim Fast Approximation Algorithms for the
Knapsack and Sum of Subset Problems . . 463--468
H. T. Kung and
F. Luccio and
F. P. Preparata On Finding the Maxima of a Set of
Vectors . . . . . . . . . . . . . . . . 469--476
S. Winograd On the Parallel Evaluation of Certain
Arithmetic Expressions . . . . . . . . . 477--492
Eberhard Bertsch An Observation on Relative Parsing Time 493--498
I. H. 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
J. 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 and
V. Y. Shen and
H. 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 Kowalski A Proof Procedure Using Connection
Graphs . . . . . . . . . . . . . . . . . 572--595
J. Robert Jump and
P. S. Thiagarajan On the Interconnection of Asynchronous
Control Structures . . . . . . . . . . . 596--612
A. V. Aho and
D. S. Hirschberg and
J. D. Ullman Bounds on the Complexity of the Longest
Common Subsequence Problem . . . . . . . 1--12
C. K. Wong and
Ashok K. Chandra Bounds for the String Editing Problem 13--16
M. Dennis Mickunas On the Complete Covering Problem for
LR(k) Grammars . . . . . . . . . . . . . 17--30
J. R. Ullmann An Algorithm for Subgraph Isomorphism 31--42
M. R. Garey and
D. S. Johnson The Complexity of Near-Optimal Graph
Coloring . . . . . . . . . . . . . . . . 43--49
Robert A. Wagner A Shortest Path Algorithm for
Edge-Sparse Graphs . . . . . . . . . . . 50--57
Alberto Martelli A Gaussian Elimination Algorithm for the
Enumeration of Cut Sets in a Graph . . . 58--73
Narsingh Deo Note on Hopcroft and Tarjan's Planarity
Algorithm . . . . . . . . . . . . . . . 74--75
C. T. Yu and
G. Salton Precision Weighting --- An Effective
Automatic Indexing Method . . . . . . . 76--88
Kenny S. Crump Numerical Inversion of Laplace
Transforms Using a Fourier Series
Approximation . . . . . . . . . . . . . 89--96
D. Potier and
E. Gelenbe and
J. Lenfant Adaptive Allocation of Central
Processing Unit Quanta . . . . . . . . . 97--102
R. A. Cody and
E. G. Coffman, Jr. Record Allocation for Minimizing
Expected Retrieval Costs on Drum-Like
Storage Devices . . . . . . . . . . . . 103--115
Sartaj K. Sahni Algorithms for Scheduling Independent
Tasks . . . . . . . . . . . . . . . . . 116--127
Ronald Fagin and
Malcolm C. Easton The Independence of Miss Ratio on Page
Size . . . . . . . . . . . . . . . . . . 128--146
D. S. Hirschberg and
C. K. Wong A Polynomial-Time Algorithm for the
Knapsack Problem with Two Variables . . 147--154
Britton Harris A Code for the Transportation Problem of
Linear Programming . . . . . . . . . . . 155--157
John B. Kam and
Jeffrey D. Ullman Global Data Flow Analysis and Iterative
Algorithms . . . . . . . . . . . . . . . 158--171
Susan L. Graham and
Mark Wegman A Fast and Usually Linear Algorithm for
Global Flow Analysis . . . . . . . . . . 172--202
Christoph M. Hoffmann and
Lawrence H. Landweber A Completeness Theorem for Straight-Line
Programs with Structured Variables . . . 203--220
Harold N. Gabow An Efficient Implementation of Edmonds'
Algorithm for Maximum Matching in Graphs 221--234
Richard G. Larson Efficiency of Computation of Cayley
Tables of $2$-Groups . . . . . . . . . . 235--241
Richard P. Brent Fast Multiple-Precision Evaluation of
Elementary Functions . . . . . . . . . . 242--251
H. T. Kung New Algorithms and Lower Bounds for the
Parallel Evaluation of Certain Rational
Expressions and Recurrences . . . . . . 252--261
Edward M. McCreight A Space-Economical Suffix Tree
Construction Algorithm . . . . . . . . . 262--272
C. T. Yu and
W. S. Luk and
T. Y. Cheung A Statistical Model for Relevance
Feedback in Information Retrieval . . . 273--286
Alan Feldstein and
Richard Goodman Convergence Estimates for the
Distribution of Trailing Digits . . . . 287--297
Donald Fraser Array Permutation by Index-Digit
Permutation . . . . . . . . . . . . . . 298--309
Marcello Pagano On the Linear Convergence of a
Covariance Factorization Algorithm . . . 310--316
Ellis Horowitz and
Sartaj Sahni Exact and Approximate Algorithms for
Scheduling Nonidentical Processors . . . 317--327
Alan G. Konheim and
Martin Reiser A Queueing Model with Finite Waiting
Room and Blocking . . . . . . . . . . . 328--341
Thomas G. Price A Note on the Effect of the Central
Processor Service Time Distribution on
Processor Utilization in Multiprogrammed
Computer Systems . . . . . . . . . . . . 342--346
Donald L. Iglehart Simulating Stable Stochastic Systems,
VI: Quantile Estimation . . . . . . . . 347--360
Kenneth Lloyd Rider A Simple Approximation to the Average
Queue Size in the Time-Dependent M/M/1
Queue . . . . . . . . . . . . . . . . . 361--367
Steven L. Horowitz and
Theodosios Pavlidis Picture Segmentation by a Tree Traversal
Algorithm . . . . . . . . . . . . . . . 368--388
Ben Wegbreit and
Jay M. Spitzen Proving Properties of Complex Data
Structures . . . . . . . . . . . . . . . 389--396
William H. Joyner, Jr. Resolution Strategies as Decision
Procedures . . . . . . . . . . . . . . . 398--417
Lena Chang and
James F. Korsh Canonical Coin Changing and Greedy
Solutions . . . . . . . . . . . . . . . 418--422
Nicholas Pippenger and
Leslie G. Valiant Shifting Graphs and Their Applications 423--432
Douglas C. Schmidt and
Larry E. Druffel A Fast Backtracking Algorithm to Test
Directed Graphs for Isomorphism Using
Distance Matrices . . . . . . . . . . . 433--445
Peter J. Slater ${R}$-Domination in Graphs . . . . . . . 446--450
William H. Burge An Analysis of Binary Search Trees
Formed from Sequences of Nondistinct
Keys . . . . . . . . . . . . . . . . . . 451--454
J. R. Cash Semi-Implicit Runge-Kutta Procedures
with Error Estimates for the Numerical
Integration of Stiff Systems of Ordinary
Differential Equations . . . . . . . . . 455--460
M. R. Garey and
D. S. Johnson Scheduling Tasks with Nonuniform
Deadlines on Two Processors . . . . . . 461--467
Ta Huu Phuong Solution of Integer Programs with a
Quadratic Objective Function . . . . . . 468--474
V. Srinivasan Linear Programming Computational
Procedures for Ordinal Regression . . . 475--487
A. V. Aho and
S. C. Johnson Optimal Code Generation for Expression
Trees . . . . . . . . . . . . . . . . . 488--501
John Bruno and
Ravi Sethi Code Generation for a One-Register
Machine . . . . . . . . . . . . . . . . 502--510
M. D. Mickunas and
R. L. Lancaster and
V. B. Schneider Transforming LR($k$) Grammars To LR(1),
SLR(1), and (1,1) bounded right-context
grammars . . . . . . . . . . . . . . . . 511--533
David E. Muller and
Franco P. Preparata Restructuring of Arithmetic Expressions
For Parallel Evaluation . . . . . . . . 534--543
Christos H. Papadimitriou On the Complexity of Edge Traversing . . 544--554
Sartaj Sahni and
Teofilo Gonzalez ${P}$-Complete Approximation Problems 555--565
Andrew Chi-Chih Yao and
Foong Frances Yao Lower Bounds on Merging Networks . . . . 566--571
R. A. Cody and
E. G. Coffman, Jr. Errata: ``Record Allocation for
Minimizing Expected Retrieval Costs on
Drum-Like Storage Devices'' . . . . . . 572--572
G. E. Peterson Theorem Proving with Lemmas . . . . . . 573--581
Seymour Ginsburg and
Nancy Lynch Size Complexity in Context-Free Grammar
Forms . . . . . . . . . . . . . . . . . 582--598
Yoram Yakimovsky Boundary and Object Detection in Real
World Images . . . . . . . . . . . . . . 599--618
Mark J. Eisner and
Dennis G. Severance Mathematical Techniques for Efficient
Record Segmentation in Large Shared
Databases . . . . . . . . . . . . . . . 619--635
D. E. Heller and
D. K. Stevenson and
J. F. Traub Accelerated Iterative Methods for the
Solution of Tridiagonal Systems on
Parallel Computers . . . . . . . . . . . 636--654
John L. Bruno Sequencing Jobs with Stochastic Task
Structures on a Single Machine . . . . . 655--664
Teofilo Gonzalez and
Sartaj Sahni Open Shop Scheduling to Minimize Finish
Time . . . . . . . . . . . . . . . . . . 665--679
Z. Rosberg and
I. Adiri Multilevel Queues with External
Priorities . . . . . . . . . . . . . . . 680--690
Ben Wegbreit Verifying Program Performance . . . . . 691--699
John P. Hayes Enumeration of Fanout-Free Boolean
Functions . . . . . . . . . . . . . . . 700--709
S. Even and
R. E. Tarjan A Combinatorial Problem Which Is
Complete in Polynomial Space . . . . . . 710--719
R. J. Lipton and
S. C. Eisenstat and
R. A. DeMillo Space and Time Hierarchies for Classes
of Control Structures and Data
Structures . . . . . . . . . . . . . . . 720--732
M. H. Van Emden and
R. A. Kowalski The Semantics of Predicate Logic as a
Programming Language . . . . . . . . . . 733--742
Donald B. Johnson Efficient Algorithms for Shortest Paths
in Sparse Networks . . . . . . . . . . . 1--13
Neil C. Wilhelm A General Model for the Performance of
Disk Systems . . . . . . . . . . . . . . 14--31
Edward C. Horvath and
Shui Lam and
Ravi Sethi A Level Algorithm for Preemptive
Scheduling . . . . . . . . . . . . . . . 32--43
R. M. Burstall and
John Darlington A Transformation System for Developing
Recursive Programs . . . . . . . . . . . 44--67
J. A. Goguen and
J. W. Thatcher and
E. G. Wagner and
J. B. Wright Initial Algebra Semantics and Continuous
Algebras . . . . . . . . . . . . . . . . 68--95
Susan L. Graham Papers from Third ACM Symposium on
Principles of Programming Languages . . 96--97
Brenda S. Baker An Algorithm for Structuring Flowgraphs 98--120
David B. Loveman Program Improvement by Source-to-Source
Transformation . . . . . . . . . . . . . 121--145
A. V. Aho and
S. C. Johnson and
J. D. Ullman Code Generation for Expressions with
Common Subexpressions . . . . . . . . . 146--160
Phillip D. Summers A Methodology for LISP Program
Construction from Examples . . . . . . . 161--175
Dennis de Champeaux and
Lenie Sint An Improved Bidirectional Heuristic
Search Algorithm . . . . . . . . . . . . 177--191
F. T. Boesch and
J. F. Gimpel Covering the Points of a Digraph with
Point-Disjoint Paths and Its Application
to Code Optimization . . . . . . . . . . 192--198
Arnold L. Rosenberg and
Larry J. Stockmeyer Hashing Schemes for Extendible Arrays 199--221
Alexandre Brandwajn A Queueing Model of Multiprogrammed
Computer Systems Under Full Load
Conditions . . . . . . . . . . . . . . . 222--240
Micha Hofri On Certain Output-Buffer Management
Techniques --- a Stochastic Model . . . 241--249
K. Mani Chandy and
John H. Howard and
Donald F. Towsley Product Form and Local Balance in
Queueing Networks . . . . . . . . . . . 250--263
Toshihide Ibaraki The Power of Dominance Relations in
Branch-and-Bound Algorithms . . . . . . 264--279
Oscar H. Ibarra and
Chul E. Kim Heuristic Algorithms for Scheduling
Independent Tasks on Nonidentical
Processors . . . . . . . . . . . . . . . 280--289
Eric C. R. Hehner Information Content of Programs and
Operation Encoding . . . . . . . . . . . 290--297
Philip J. Davis Proof, Completeness, Transcendentals,
and Sampling . . . . . . . . . . . . . . 298--310
C. M. Fiduccia and
Y. Zalcstein Algebras Having Linear Multiplicative
Complexities . . . . . . . . . . . . . . 311--331
John Hopcroft and
Wolfgang Paul and
Leslie Valiant On Time Versus Space . . . . . . . . . . 332--337
N. D. Jones and
S. S. Muchnick Even Simple Programs Are Hard to Analyze 338--350
A. Michael Ballantyne and
W. W. Bledsoe Automatic Proofs of Theorems in Analysis
Using Nonstandard Techniques . . . . . . 353--374
Guy Fayolle and
Erol Gelenbe and
Jacques Labetoulle Stability and Optimal Control of the
Packet Switching Broadcast Channel . . . 375--386
Harry B. Hunt III and
Daniel J. Rosenkrantz On Equivalence and Containment Problems
for Formal Languages . . . . . . . . . . 387--396
R. Attar and
A. S. Fraenkel Local Feedback in Full-Text Retrieval
Systems . . . . . . . . . . . . . . . . 397--417
Abraham Bookstein and
Don Kraft Operations Research Applied to Document
Indexing and Retrieval Decisions . . . . 418--427
Douglas Comer and
Ravi Sethi The Complexity of Trie Index
Construction . . . . . . . . . . . . . . 428--440
K. Hwang and
S. B. Yao Optimal Batched Searching of Tree
Structured Files in Multiprocessor
Computer Systems . . . . . . . . . . . . 441--454
R. J. Lipton and
L. Snyder A Linear Time Algorithm for Deciding
Subject Security . . . . . . . . . . . . 455--464
Benjamin W. Y. Lin and
Ronald L. Rardin Development of a Parametric Generating
Procedure for Integer Programming Test
Problems . . . . . . . . . . . . . . . . 465--472
Lawrence T. Kou On Live-Dead Analysis for Global Data
Flow Problems . . . . . . . . . . . . . 473--483
John C. Reynolds Semantics of the Domain of Flow Diagrams 484--503
Ben Wegbreit Complexity of Synthesizing Inductive
Assertions . . . . . . . . . . . . . . . 504--512
L. Hyafil and
H. T. Kung The Complexity of Parallel Evaluation of
Linear Recurrences . . . . . . . . . . . 513--521
Richard J. Lipton and
Yechezkel Zalcstein Word Problems Solvable in Logspace . . . 522--526
K. L. Krause and
V. Y. Shen and
H. D. Schwetman Errata: ``Analysis of Several
Task-Scheduling Algorithms for a Model
of Multiprogramming Computer Systems'' 527--527
Robert E. Shostak On the SUP-INF Method for Proving
Presburger Formulas . . . . . . . . . . 529--543
R. A. DeMillo and
K. Vairavan and
E. Sycara-Cyranski A Study of Schedules as Models of
Synchronous Parallel Computation . . . . 544--565
Mamoru Maekawa Queueing Models for Computer Systems
Connected by a Communication Line . . . 566--582
Nancy Lynch Log Space Recognition and Translation of
Parenthesis Languages . . . . . . . . . 583--590
Ian F. Blake and
Alan G. Konheim Big Buckets Are (Are Not) Better! . . . 591--606
C. T. Yu and
W. S. Luk Analysis of Effectiveness of Retrieval
in Clustered Files . . . . . . . . . . . 607--622
T. D. Bui Errata and Comments on a Paper by J. R.
Cash . . . . . . . . . . . . . . . . . . 623--623
S. E. Sahasrabudhe and
A. D. Kulkarni On Solving Fredholm Integral Equations
of the First Kind . . . . . . . . . . . 624--629
Bharat Kinariwala and
A. G. Rao Flow Switching Approach to the Maximum
Flow Problem: I . . . . . . . . . . . . 630--645
Kenneth J. Omahen Capacity Bounds for Multiresource Queues 646--663
Daniel S. Hirschberg Algorithms for the Longest Common
Subsequence Problem . . . . . . . . . . 664--675
Shawpawn Kumar Das A Machine Representation of Finite
${T}_0$ Topologies . . . . . . . . . . . 676--692
Paul Young Optimization Among Provably Equivalent
Programs . . . . . . . . . . . . . . . . 693--700
Y. Perl and
Y. Shiloach Finding Two Disjoint Paths Between Two
Pairs of Vertices in a Graph . . . . . . 1--9
Luigi Logrippo Renamings and Economy of Memory in
Program Schemata . . . . . . . . . . . . 10--22
Ronald V. Book Simple Representations of Certain
Classes of Languages . . . . . . . . . . 23--31
Harry B. Hunt, III and
Thomas G. Szymanski Lower Bounds and Reductions Between
Grammar Problems . . . . . . . . . . . . 32--51
R. Attar and
Y. Choueka and
N. Dershowitz and
A. S. Fraenkel Kedma --- Linguistic Tools for Retrieval
Systems . . . . . . . . . . . . . . . . 52--66
W. S. Cooper and
M. E. Maron Foundations of Probabilistic and
Utility-Theoretic Indexing . . . . . . . 67--80
A. H. Sameh and
D. J. Kuck On Stable Parallel Linear System Solvers 81--91
Teofilo Gonzalez and
Sartaj Sahni Preemptive Scheduling of Uniform
Processor Systems . . . . . . . . . . . 92--101
Zvi Galil and
Joel Seiferas A Linear-Time On-Line Recognition
Algorithm for ``Palstar'' . . . . . . . 102--111
W. Morven Gentleman Some Complexity Results for Matrix
Computations on Parallel Processors . . 112--115
O. H. Ibarra Reversal-Bounded Multicounter Machines
and Their Decision Problems . . . . . . 116--133
Harry R. Lewis Renaming a Set of Clauses as a Horn Set 134--135
C. P. Schnorr Satisfiability is Quasilinear Complete
in NQL . . . . . . . . . . . . . . . . . 136--145
Joel I. Seiferas and
Michael J. Fischer and
Albert R. Meyer Separating Nondeterministic Time
Complexity Classes . . . . . . . . . . . 146--167
Mitchell Wand A new Incompleteness Result for Hoare's
System . . . . . . . . . . . . . . . . . 168--175
Edward C. Horvath Stable Sorting in Asymptotically Optimal
Time and Extra Space . . . . . . . . . . 177--199
Ronald L. Rivest Optimal Arrangement of Keys in a Hash
Table . . . . . . . . . . . . . . . . . 200--209
C. T. Yu and
G. Salton and
M. K. Siu Effective Automatic Indexing Using Term
Addition and Deletion . . . . . . . . . 210--225
Gérard M. Baudet Asynchronous Iterative Methods for
Multiprocessors . . . . . . . . . . . . 226--244
H. T. Kung and
J. F. Traub All Algebraic Functions Can Be Computed
Fast . . . . . . . . . . . . . . . . . . 245--260
William McKie An Example of a Skewing Function . . . . 261--265
John M. Mulvey Pivot Strategies for Primal-Simplex
Network Codes . . . . . . . . . . . . . 266--270
David R. Musser On the Efficiency of a Polynomial
Irreducibility Test . . . . . . . . . . 271--282
K. Omahen and
V. Marathe Analysis and Applications of the Delay
Cycle for the M/M/C Queueing System . . 283--303
Andris A. Zoltners A Direct Descent Binary Knapsack
Algorithm . . . . . . . . . . . . . . . 304--311
Neil D. Jones and
Steven S. Muchnick The Complexity of Finite Memory Programs
with Recursion . . . . . . . . . . . . . 312--321
David Maier The Complexity of Some Problems on
Subsequences and Supersequences . . . . 322--336
Andrew C. Yao and
Ronald L. Rivest $k + 1$ Heads Are Better than $k$ . . . 337--340
Harrison and
Rubin Another Generalization of Resolution . . 341--351
L. H. Landweber and
E. L. Robertson Properties of Conflict-Free and
Persistent Petri Nets . . . . . . . . . 352--364
D. G. Kafura and
V. Y. Shen An Algorithm to Design the Memory
Configuration of a Computer Network . . 365--377
Gururaj S. Rao Performance Analysis of Cache Memories 378--395
Doron Rotem and
Y. L. Varol Generation of Binary Trees from Ballot
Sequences . . . . . . . . . . . . . . . 396--404
I. H. Sudborough On the Tape Complexity of Deterministic
Context-Free Languages . . . . . . . . . 405--414
Herbert S. Wilf A Global Bisection Algorithm for
Computing the Zeros of Polynomials in
the Complex Plane . . . . . . . . . . . 415--420
A. C. McKellar and
C. K. Wong Dynamic Placement of Records in Linear
Storage . . . . . . . . . . . . . . . . 421--434
R. S. Garfinkel and
K. C. Gilbert The Bottleneck Traveling Salesman
Problem: Algorithms and Probabilistic
Analysis . . . . . . . . . . . . . . . . 435--448
Donald L. Iglehart and
Gerald S. Shedler Regenerative Simulation of Response
Times in Networks of Queues . . . . . . 449--460
C. A. R. Hoare Some Properties of Predicate
Transformers . . . . . . . . . . . . . . 461--480
Jon T. Butler Analysis and Design of Fanout-Free
Networks of Positive Symmetric Gates . . 481--498
M. R. Garey and
D. S. Johnson ``Strong'' NP-Completeness Results:
Motivation, Examples, and Implications 499--508
Nicholas Pippenger A Time-Space Trade-Off . . . . . . . . . 509--515
Alon Itai and
Michael Rodeh and
Steven L. Tanimoto Some Matching Problems for Bipartite
Graphs . . . . . . . . . . . . . . . . . 517--525
Brian Allen and
Ian Munro Self-Organizing Binary Search Trees . . 526--535
J. L. Bentley and
H. T. Kung and
M. Schkolnick and
C. D. Thompson On the Average Number of Maxima in a Set
of Vectors and Applications . . . . . . 536--543
Leo J. Guibas The Analysis of Hashing Techniques that
Exhibit $k$-ary Clustering . . . . . . . 544--555
Donald B. Johnson and
Samuel D. Kashdan Lower Bounds for Selection in ${X} +
{Y}$ and Other Multisets . . . . . . . . 556--570
S. Crespi-Reghizzi and
G. Guida and
D. Mandrioli Noncounting Context-Free Languages . . . 571--580
R. P. Brent and
H. T. Kung Fast Algorithms for Manipulating Formal
Power Series . . . . . . . . . . . . . . 581--595
Alon Itai Two-Commodity Flow . . . . . . . . . . . 596--611
E. L. Lawler and
J. Labetoulle On Preemptive Scheduling of Unrelated
Parallel Processors by Linear
Programming . . . . . . . . . . . . . . 612--619
Hendrik Vantilborgh Exact Aggregation in Exponential
Queueing Networks . . . . . . . . . . . 620--629
Daniel Brand Path Calculus in Program Verification 630--651
Peter J. Downey and
Ravi Sethi Assignment Commands with Array
References . . . . . . . . . . . . . . . 652--666
Ravi Sethi Conditional Expressions with Equality
Tests . . . . . . . . . . . . . . . . . 667--674
A. C. Arvillias and
D. G. Maritsas Partitioning the Period of a Class of
$m$-Sequences and Application to
Pseudorandom Number Generation . . . . . 675--686
H. B. Hunt, III and
T. G. Szymanski Corrigendum: ``Lower Bounds and
Reductions Between Grammar Problems'' 687--688
Rainer Parchmann Control System Model for Critically
Timed Sources . . . . . . . . . . . . . 1--5
Alan Jay Smith Characterizing the Storage Process and
its Effect on the Update of Main Memory
by Write Through . . . . . . . . . . . . 6--27
Udaiprakash Gupta Bounds on Storage for Consecutive
Retrieval . . . . . . . . . . . . . . . 28--36
Alberto O. Mendelzon On Axiomatizing Multivalued Dependencies
in Relational Databases . . . . . . . . 37--44
Steven P. Reiss Security in Databases; A Combinatorial
Study . . . . . . . . . . . . . . . . . 45--57
Zvi Galil and
Nimrod Megiddo A Fast Selection Algorithm and the
Problem of Optimum Distribution of
Effort . . . . . . . . . . . . . . . . . 58--64
James M. Lemme and
John R. Rice Speedup in Parallel Algorithms for
Adaptive Quadrature . . . . . . . . . . 65--71
Garry H. Rodrigue and
Niel K. Madsen and
Jack I. Karush Odd-Even Reductions for Banded Linear
Equations . . . . . . . . . . . . . . . 72--81
George S. Fishman and
Louis R. Moore Estimating the Mean of a Correlated
Binary Sequence with an Application to
Discrete Event Simulation . . . . . . . 82--94
Christos H. Papadimitriou Optimality of the Fast Fourier Transform 95--102
Walter J. Savitch and
Michael J. Stimson Time Bounded Random Access Machines with
Parallel Processing . . . . . . . . . . 103--118
John C. Cherniavsky and
Samuel N. Kamin A Complete and Consistent Hoare
Axiomatics for a Simple Programming
Language . . . . . . . . . . . . . . . . 119--128
Edmund Melson Clarke, Jr. Programming Language Constructs for
Which It Is Impossible To Obtain Good
Hoare Axiom Systems . . . . . . . . . . 129--147
Gérard Berry and
Jean-Jacques Lévy Minimal and Optimal Computations of
Recursive Programs . . . . . . . . . . . 148--175
F. K. Hwang An $O(n \log n)$ Algorithm for
Rectilinear Minimal Spanning Tree . . . 177--182
George S. Lueker and
Kellogg S. Booth A Linear Time Algorithm for Deciding
Interval Graph Isomorphism . . . . . . . 183--195
Azad Bolour Optimality Properties of Multiple-Key
Hashing Functions . . . . . . . . . . . 196--210
Mark R. Brown and
Robert E. Tarjan A Fast Merging Algorithm . . . . . . . . 211--226
Frank Fussenegger and
Harold N. Gabow A Counting Approach to Lower Bounds for
Selection Problems . . . . . . . . . . . 227--238
Boleslaw Kacewicz Integrals with a Kernel in the Solution
of Nonlinear Equations in ${N}$
Dimensions . . . . . . . . . . . . . . . 239--249
J. F. Traub and
H. Wo\'zniakowski Convergence and Complexity of Newton
Iteration for Operator Equations . . . . 250--258
Erol Gelenbe On the Optimum Checkpoint Interval . . . 259--270
Donald L. Iglehart and
Peter A. W. Lewis Regenerative Simulation with Internal
Controls . . . . . . . . . . . . . . . . 271--282
Tomasz Kowaltowski Data Structures and Correctness of
Programs . . . . . . . . . . . . . . . . 283--301
George Milne and
Robin Milner Concurrent Processes and Their Syntax 302--321
Barry K. Rosen Data Flow Analysis for Procedural
Languages . . . . . . . . . . . . . . . 322--344
K. Culik, II A Purely Homomorphic Characterization of
Recursively Enumerable Sets . . . . . . 345--350
Robert E. Shostak A Practical Decision Procedure for
Arithmetic with Function Symbols . . . . 351--360
Nicholas Pippenger and
Michael J. Fischer Relations Among Complexity Measures . . 361--381
Anonymous Corrigendum: ``Papers from the Fourth
ACM Symposium on Principles of
Programming Languages'' . . . . . . . . 382--382
L. J. Henschen Theorem Proving by Covering Expressions 385--400
Jacques Cohen and
Timothy Hickey Two Algorithms for Determining Volumes
of Convex Polyhedra . . . . . . . . . . 401--414
D. T. Lee and
F. P. Preparata An Optimal Algorithm for Finding the
Kernel of a Polygon . . . . . . . . . . 415--421
Kuo-Chung Tai The Tree-to-Tree Correction Problem . . 422--433
Glenn K. Manacher Significant Improvements to the
Hwang-Lin Merging Algorithm . . . . . . 434--440
Glenn K. Manacher The Ford-Johnson Sorting Algorithm Is
Not Optimal . . . . . . . . . . . . . . 441--456
H. R. Strong and
G. Markowsky and
A. K. Chandra Search Within a Page . . . . . . . . . . 457--482
T. D. Bui Some ${A}$-Stable and ${L}$-Stable
Methods for the Numerical Integration of
Stiff Ordinary Differential Equations 483--493
Robert D. Skeel Scaling for Numerical Stability in
Gaussian Elimination . . . . . . . . . . 494--526
Arthur G. Werschulz Maximal Order and Order of Information
for Numerical Quadrature . . . . . . . . 527--537
Greg N. Frederickson Approximation Algorithms for Some
Postman Problems . . . . . . . . . . . . 538--554
Brenda S. Baker and
S. Rao Kosaraju A Comparison of Multilevel break and
next Statements . . . . . . . . . . . . 555--566
Eitan M. Gurari and
Oscar H. Ibarra An NP-Complete Number-Theoretic Problem 567--581
Zvi M. Kedem Combining Dimensionality and Rate of
Growth Arguments for Establishing Lower
Bounds on the Number of Multiplications
and Divisions . . . . . . . . . . . . . 582--601
T. Beyer and
W. Jones and
S. Mitchell Linear Algorithms for Isomorphism of
Maximal Outerplanar Graphs . . . . . . . 603--610
Jonathan L. Gross and
Ronald H. Rosen A Linear Time Planarity Algorithm for
$2$-Complexes . . . . . . . . . . . . . 611--617
Mihalis Yannakakis The Effect of a Connectivity Requirement
on the Complexity of Maximum Subgraph
Problems . . . . . . . . . . . . . . . . 618--630
Christos H. Papadimitriou The Serializability of Concurrent
Database Updates . . . . . . . . . . . . 631--653
Haim Mendelson and
Uri Yechiali Performance Measures for Ordered Lists
in Random-Access Files . . . . . . . . . 654--667
Arnold L. Rosenberg Encoding Data Structures in Trees . . . 668--689
Robert Endre Tarjan Applications of Path Compression on
Balanced Trees . . . . . . . . . . . . . 690--715
Joaquín Bustoz and
Alan Feldstein and
Richard Goodman and
Seppo Linnainmaa Improved Trailing Digits Estimates
Applied to Optimal Computer Arithmetic 716--730
J. C. Butcher A Transformed Implicit Runge-Kutta
Method . . . . . . . . . . . . . . . . . 731--738
Donald B. Johnson and
Webb Miller and
Brian Minnihan and
Celia Wrathall Reducibility Among Floating-Point Graphs 739--760
U. Narayan Bhat and
Richard E. Nance An Evaluation of CPU Efficiency Under
Dynamic Quantum Allocation . . . . . . . 761--778
Andrew S. Noetzel A generalized queueing discipline for
product form network solutions . . . . . 779--793
Robin Milner Flowgraphs and Flow Algebras . . . . . . 794--818
Luigi Logrippo Renamings, Maximal Parallelism, and
Space-Time Tradeoff in Program Schemata 819--833
Andrzej Proskurowski On the Generation of Binary Trees . . . 1--2
Marvin Solomon and
Raphael A. Finkel A Note on Enumerating Binary Trees . . . 3--5
David Nassimi and
Sartaj Sahni An Optimal Routing Algorithm for
Mesh-Connected Parallel Computers . . . 6--29
Krzysztof Pawlikowski Message Waiting Time in a Packet
Switching System . . . . . . . . . . . . 30--41
G. Boyd Swartz Polling in a Loop System . . . . . . . . 42--59
Peter B. Henderson and
Yechezkel Zalcstein Synchronization Problems Solvable by
Generalized PV Systems . . . . . . . . . 60--71
Abraham Silberschatz and
Zvi Kedem Consistency in Hierarchical Database
Systems . . . . . . . . . . . . . . . . 72--80
Richard J. Lipton and
Arnold L. Rosenberg and
Andrew C. Yao External Hashing Schemes for Collections
of Data Structures . . . . . . . . . . . 81--95
Joost Engelfriet and
Erik Meineche Schmidt and
Jan van Leeuwen Stack Machines and Classes of Nonnested
Macro Languages . . . . . . . . . . . . 96--117
Ravindran Kannan A Polynomial Algorithm for the
Two-Variable Integer Programming Problem 118--122
Richard A. DeMillo and
Stanley C. Eisenstat and
Richard J. Lipton Space-Time Trade-Offs in Structured
Programming: An Improved Combinatorial
Embedding Theorem . . . . . . . . . . . 123--127
Marc A. Kaplan and
Jeffrey D. Ullman A Scheme for the Automatic Inference of
Variable Types . . . . . . . . . . . . . 128--145
Bhaskaram Prabhala and
Ravi Sethi Efficient Computation of Expressions
with Common Subexpressions . . . . . . . 146--163
Mitchell Wand Continuation-Based Program
Transformation Strategies . . . . . . . 164--180
Edward A. Bender The Number of Fanout-Free Functions with
Various Gates . . . . . . . . . . . . . 181--190
Norihisa Suzuki and
David Jefferson Verification Decidability of Pressburger
Array Programs . . . . . . . . . . . . . 191--205
Andrew Chi-Chih Yao New Algorithms for Bin Packing . . . . . 207--227
M. Pease and
R. Shostak and
L. Lamport Reaching Agreements in the Presence of
Faults . . . . . . . . . . . . . . . . . 228--234
Raymond Reiter Equality and Domain Closure for
First-Order Databases . . . . . . . . . 235--249
Yehoshua Sagiv An Algorithm for Inferring Multivalued
Dependencies with an Application to
Propositional Logic . . . . . . . . . . 250--262
G. W. Wasilkowski Can Any Stationary Iteration Using
Linear Information be Globally
Convergent? . . . . . . . . . . . . . . 263--269
Tiko Kameda Testing Deadlock-Freedom of Computer
Systems . . . . . . . . . . . . . . . . 270--280
We-Min Chow The Cycle Time Distribution of
Exponential Cyclic Queues . . . . . . . 281--286
Teofilo F. Gonzalez and
Donald B. Johnson A New Algorithm for Preemptive
Scheduling of Trees . . . . . . . . . . 287--312
M. Reiser and
S. S. Lavenberg Mean-Value Analysis of Closed Multichain
Queuing Networks . . . . . . . . . . . . 313--322
Don Towsley Queuing Network Models with
State-Dependent Routing . . . . . . . . 323--337
Ramachandran Krishnaswamy and
Arthur B. Pyster On the Correctness of
Semantic-Syntax-Directed Translations 338--355
Greg Nelson and
Derek C. Oppen Fast Decision Procedures Based on
Congruence Closure . . . . . . . . . . . 356--364
Stephen A. Ward and
Robert H. Halstead, Jr. A Syntactic Theory of Message Passing 365--383
Harold Abelson Lower Bounds on Information Transfer in
Distributed Computations . . . . . . . . 384--392
David Lichtenstein and
Michael Sipser GO is Polynomial-Space Hard . . . . . . 393--401
R. Parchmann Corrigendum: ``Control System Model for
Critically Timed Sources'' . . . . . . . 402--402
Derek C. Oppen Reasoning About Recursively Defined Data
Structures . . . . . . . . . . . . . . . 403--411
Doris Altenkamp and
Kurt Mehlhorn Codes: Unequal Probabilities, Unequal
Letter Costs . . . . . . . . . . . . . . 412--427
Ronald L. Graham and
Andrew C. Yao and
F. Frances Yao Information Bounds Are Weak in the
Shortest Distance Problem . . . . . . . 428--444
Yossi Shiloach A Polynomial Solution in the Undirected
Two Paths Problem . . . . . . . . . . . 445--456
Kishor S. Trivedi and
Robert A. Wagner and
Timothy M. Sigmon Optimal Selection of CPU Speed, Device
Capacities, and File Assignments . . . . 457--473
Haim Mendelson and
Uri Yechiali A New Approach to the Analysis of Linear
Probing Schemes . . . . . . . . . . . . 474--483
Fred G. Abramson and
Yuri Breitbart and
Forbes D. Lewis Complex Properties of Grammars . . . . . 484--498
J. Engelfriet and
G. Rozenberg Fixed Point Languages, Equality
Languages, and Representation of
Recursively Enumerable Languages . . . . 499--518
G. Fayolle and
I. Mitrani and
R. Iasnogorodski Sharing a Processor Among Many Job
Classes . . . . . . . . . . . . . . . . 519--532
Christos H. Papadimitriou and
Paris C. Kanellakis Flowshop Scheduling with Limited
Temporary Storage . . . . . . . . . . . 533--549
Sartaj Sahni and
Yookun Cho Scheduling Independent Tasks with Due
Times on a Uniform Processor System . . 550--563
Carlo Ghezzi and
Dino Mandrioli Augmenting Parsers to Support
Incrementality . . . . . . . . . . . . . 564--579
Ravi Sethi and
Adrian Tang Constructing Call-by-value Continuation
Semantics . . . . . . . . . . . . . . . 580--597
Alan R. Aronson and
Barry E. Jacobs and
Jack Minker A Note on Fuzzy Deduction . . . . . . . 599--603
D. T. Lee Two-dimensional Voronoi diagrams in the
$L_p$-metric . . . . . . . . . . . . . . 604--618
S. Tsukiyama and
I. Shirakawa and
H. Ozaki and
H. Ariyoshi An Algorithm to Enumerate All Cutsets of
a Graph in Linear Time per Cutset . . . 619--632
Yehoshua Sagiv and
Mihalis Yannakakis Equivalences Among Relational
Expressions with the Union and
Difference Operators . . . . . . . . . . 633--655
A. Ehrenfeucht and
G. Rozenberg The Sequence Equivalence Problem Is
Decidable for 0S Systems . . . . . . . . 656--663
David Maier Minimum Covers in the Relational
Database Model . . . . . . . . . . . . . 664--674
S. A. Greibach and
E. P. Friedman Superdeterministic PDAs: A Subclass with
a Decidable Inclusion Problem . . . . . 675--700
J. T. Schwartz Fast Probabilistic Algorithms for
Verification of Polynomial Identities 701--717
Marshall L. Fisher and
Dorit S. Hochbaum Database Location in Computer Networks 718--735
K. G. Ramakrishnan Solving Two-Commodity Transportation
Problems with Coupling Constraints . . . 736--757
Peter J. Downey and
Ravi Sethi and
Robert Endre Tarjan Variations on the Common Subexpression
Problem . . . . . . . . . . . . . . . . 758--771
Jean-Claude Raoult and
Jean Vuillemin Operational and Semantic Equivalence
Between Recursive Programs . . . . . . . 772--796
Gérard Huet Confluent Reductions: Abstract
Properties and Applications to Term
Rewriting Systems . . . . . . . . . . . 797--821
Joseph Ja'Ja' Computation of Bilinear Forms over
Finite Fields . . . . . . . . . . . . . 822--830
Richard E. Ladner and
Michael J. Fischer Parallel Prefix Computation . . . . . . 831--838
Rüdiger Reischuk Improved Bounds on the Problem of
Time-Space Trade-Off in the Pebble Game 839--849
Shimon Even and
Yossi Shiloach An On-Line Edge-Deletion Problem . . . . 1--4
Yehoshua Perl and
Stephen R. Schach Max-Min Tree Partitioning . . . . . . . 5--15
Michael Rodeh and
Vaughan R. Pratt and
Shimon Even Linear Algorithm for Data Compression
via String Matching . . . . . . . . . . 16--24
Philip A. Bernstein and
Dah-Ming W. Chiu Using Semi-Joins to Solve Relational
Queries . . . . . . . . . . . . . . . . 25--40
Witold Lipski, Jr. On Databases with Incomplete Information 41--70
G. W. Wasilkowski $n$-Evaluation Conjecture for Multipoint
Iterations for the Solution of Scalar
Nonlinear Equations . . . . . . . . . . 71--80
James O. Achugbue and
Francis Y. Chin Bounds on Schedules for Independent
Tasks with Similar Execution Times . . . 81--99
J. Bruno and
P. Downey and
G. N. Frederickson Sequencing Tasks with Exponential
Service Times to Minimize the Expected
Flow Time or Makespan . . . . . . . . . 100--113
Ashok K. Chandra and
Dexter C. Kozen and
Larry J. Stockmeyer Alternation . . . . . . . . . . . . . . 114--133
Z. 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 and
Joel I. Seiferas New Real-Time Simulations of Multihead
Tape Units . . . . . . . . . . . . . . . 166--180
John H. Rowland and
Philip J. Davis On the Use of Transcendentals for
Program Testing . . . . . . . . . . . . 181--190
Peter B. Andrews Theorem Proving by Matings . . . . . . . 193--214
Prabhaker Mateti A Decision Procedure for the Correctness
of a Class of Programs . . . . . . . . . 215--222
Gerald E. Peterson and
Mark E. Stickel Complete Sets of Reductions for Some
Equational Theories . . . . . . . . . . 223--264
C. K. Chu A Note on Multiple Error Detection in
ASCII Numeric Data Communication . . . . 265--269
Kishor S. Trivedi and
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
R. M. Feldman and
G. W. Adkins and
G. L. Curry and
U. W. Pooch Measurement Bias in Feedback Queues . . 351--357
K. C. Sevcik and
I. Mitrani The Distribution of Queuing Network
States at Input and Output Instants . . 358--371
C. J. Hogger Derivation of Logic Programs . . . . . . 372--392
Martin Rem The Closure Statement: A Programming
Language Construct Allowing
Ultraconcurrent Execution . . . . . . . 393--410
K. J. Lieberherr and
E. Specker Complexity of Partial Satisfaction . . . 411--421
Mark E. Stickel A Unification Algorithm for
Associative-Commutative Functions . . . 423--434
Francis Y. Chin and
Long-Lieh Tsai On ${J}$-maximal and ${J}$-minimal
Flow-Shop Schedules . . . . . . . . . . 462--476
Yehoshua Sagiv and
Claude Delobel and
D. Stott Parker, Jr. and
Ronald Fagin An Equivalence Between Relational
Database Dependencies and a Fragment of
Propositional Logic . . . . . . . . . . 435--453
David Dobkin and
J. Ian Munro Optimal Time Minimal Space Selection
Algorithms . . . . . . . . . . . . . . . 454--461
Francis Y. Chin and
Long Lieh Tsai On J-Maximal and J-Minimal Flow-Shop
Schedules . . . . . . . . . . . . . . . 462--476
Leonard Kleinrock and
Arne Nilsson On Optimal Scheduling Algorithms for
Time-Shared Systems . . . . . . . . . . 477--486
Hanan Samet Connected Component Labeling Using
Quadtrees . . . . . . . . . . . . . . . 487--501
Sarangan Krishna Kumar and
Melvin A. Breuer Probabilistic Aspects of Boolean
Switching Functions via a New Transform 502--520
R. P. Brent and
H. T. Kung The Area-Time Complexity of Binary
Multiplication . . . . . . . . . . . . . 521--534
Eitan M. Gurari and
Oscar H. Ibarra The Complexity of the Equivalence
Problem for Simple Programs . . . . . . 535--560
Ernst W. Mayr and
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
M. Reiser and
S. S. Lavenberg Corrigendum: ``Mean-Value Analysis of
Closed Multichain Queuing Networks'' . . 629--629
Wolfgang Bibel On Matrices with Connections . . . . . . 633--645
D. W. Loveland and
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 and
Yehoshua Sagiv and
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
A. Ehrenfeucht and
G. Rozenberg and
K. 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 and
Jeffrey M. Jaffe Algorithms for Scheduling Tasks on
Unrelated Processors . . . . . . . . . . 721--736
Stefania Gnesi and
Ugo Montanari and
Alberto Martelli Dynamic Programming as Graph Searching:
An Algebraic Approach . . . . . . . . . 737--751
N. Katoh and
T. Ibaraki and
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 Shostak Deciding Linear Inequalities by
Computing Loop Residues . . . . . . . . 769--779
Andrew Chi-Chih Yao A Lower Bound to Finding Convex Hulls 780--787
George W. Ernst and
Michael M. Goldstein Mechanical Discovery of Classes of
Problem-Solving Strategies . . . . . . . 1--23
Eugene C. Freuder A Sufficient Condition of Backtrack-Free
Search . . . . . . . . . . . . . . . . . 24--32
Drew McDermott Nonmonotonic Logic II: Nonmonotonic
Modal Theories . . . . . . . . . . . . . 33--57
Ronald I. Becker and
Stephen R. Schach and
Yehoshua Perl A Shifting Algorithm for Min-Max Tree
Partitioning . . . . . . . . . . . . . . 58--67
Christoph M. Hoffmann and
Michael J. O'Donnell Pattern Matching in Trees . . . . . . . 68--95
Zvi Galil An Almost Linear-Time Algorithm for
Computing a Dependency Basis in a
Relational Database . . . . . . . . . . 96--102
Yehoshua Sagiv and
Scott F. Walecka Subset Dependencies and a Completeness
Result for a Subclass of Embedded
Multivalued Dependencies . . . . . . . . 103--117
H. A. Maurer and
A. Salomaa and
D. Wood Dense Hierarchies of Grammatical
Families . . . . . . . . . . . . . . . . 118--126
D. Chow and
C. T. Yu On the Construction of Feedback Queries 127--151
C. T. Yu and
K. Lam and
G. Salton Term Weighting in Information Retrieval
Using the Term Precision Model . . . . . 152--170
Ronald V. Book Confluent and Other Types of Thue
Systems . . . . . . . . . . . . . . . . 171--182
James E. Burns and
Paul Jackson and
Nancy A. Lynch and
Michael J. Fischer and
Gary L. Peterson Data Requirements for Implementation of
${N}$-Process Mutual Exclusion Using a
Single Shared Variable . . . . . . . . . 183--205
H.-D. Ehrich On the Theory of Specification,
Implementation, and Parametrization of
Abstract Data Types . . . . . . . . . . 206--227
H. B. Hunt, III On the Complexity of Flowchart and Loop
Program Schemes and Programming
Languages . . . . . . . . . . . . . . . 228--249
Michael L. Fredman The Complexity of Maintaining an Array
and Computing Its Partial Sums . . . . . 250--260
Charles Rackoff Relativized Questions Involving
Probabilistic Algorithms . . . . . . . . 261--268
Steve Winker Generation and Verification of Finite
Models and Counterexamples Using an
Automated Theorem Prover Answering Two
Open Questions . . . . . . . . . . . . . 273--284
Christos H. Papadimitriou and
Mihalis Yannakakis The Complexity of Restricted Spanning
Tree Problems . . . . . . . . . . . . . 285--309
Barry E. Jacobs On Database Logic . . . . . . . . . . . 310--332
Y. Edmund Lien On the Equivalence of Database Models 333--362
Fereidoon Sadri and
Jeffrey D. Ullman Template Dependencies: A Large Class of
Dependencies in Relational Databases and
Its Complete Axiomatization . . . . . . 363--372
Edward Sciore A Complete Axiomatization of Full Join
Dependencies . . . . . . . . . . . . . . 373--393
Ravi Sethi Useless Actions Make a Difference:
Strict Serializability of Database
Updates . . . . . . . . . . . . . . . . 394--403
Christopher Bader and
Arnaldo Moura A Generalization of Ogden's Lemma . . . 404--406
Jacques Cohen and
Timothy Hickey and
Joel Katcoff Upper Bounds for Speedup in Parallel
Parsing . . . . . . . . . . . . . . . . 408--428
H. B. Hunt, III On the Decidability of Grammar Problems 429--447
Theodore Brown Determination of the Conditional
Response for Quantum Allocation
Algorithms . . . . . . . . . . . . . . . 448--460
R. M. Bryant Maximum Processing Rates of Memory Bound
Systems . . . . . . . . . . . . . . . . 461--477
Hisao Kameda A Finite-Source Queue with Different
Customers . . . . . . . . . . . . . . . 478--491
Simon S. Lam Dynamic Scaling and Growth Behavior of
Queuing Network Normalization Constants 492--513
Manfred Ruschitzka The Performance of Job Classes with
Distinct Policy Functions . . . . . . . 514--526
Percy Tzelnic and
Izidor Gertner An Approach to Program Behavior Modeling
and Optimal Memory Control . . . . . . . 525--554
Albert R. Meyer and
Joseph Y. Halpern Axiomatic Definitions of Programming
Languages: A Theoretical Assessment . . 555--576
Michael A. Arbib and
Ernest G. Manes The Pattern-of-Calls Expansion Is the
Canonical Fixpoint for Recursive
Definitions . . . . . . . . . . . . . . 577--602
Robert W. Floyd and
Jeffrey D. Ullman The Compilation of Regular Expressions
into Integrated Circuits . . . . . . . . 603--622
K. Takamizawa and
T. Nishizeki and
N. Saito Linear-Time Computability of
Combinatorial Problems in
Series-Parallel Graphs . . . . . . . . . 623--641
David Nassimi and
Sartaj Sahni Parallel Permutation and Sorting
Algorithms and a New Generalized
Connection Network . . . . . . . . . . . 642--667
Peter Honeyman Testing Satisfaction of Functional
Dependencies . . . . . . . . . . . . . . 668--677
Seymour Ginsburg and
Sami Mohammed Zaiddan Properties of Functional-Dependency
Families . . . . . . . . . . . . . . . . 678--698
Anthony Klug Equivalence of Relational Algebra and
Relational Calculus Query Languages
Having Aggregate Functions . . . . . . . 699--717
Mihalis Yannakakis A Theory of Safe Locking Policies in
Database Systems . . . . . . . . . . . . 718--740
Dana Angluin Inference of Reversible Languages . . . 741--765
Harold N. Gabow An Almost-Linear Algorithm for
Two-Processor Scheduling . . . . . . . . 766--780
Errol L. Lloyd Critical Path Scheduling with Resource
and Processor Constraints . . . . . . . 781--811
Charles Martel Preemptive Scheduling with Release
Times, Deadlines, and Due Times . . . . 812--829
Christopher L. Samelson and
William G. Bulgren A Note on Product-Form Solution for
Queuing Networks with Poisson Arrivals
and General Service-Time Distributions
with Finite Means . . . . . . . . . . . 830--840
Krzysztof R. Apt and
M. H. Van Emden Contributions to the Theory of Logic
Programming . . . . . . . . . . . . . . 841--862
Eitan M. Gurari and
Oscar H. Ibarra Two-Way Counter Machines and Diophantine
Equations . . . . . . . . . . . . . . . 863--873
Mark Jerrum and
Marc Snir Some Exact Complexity Results for
Straight-Line Computations over
Semirings . . . . . . . . . . . . . . . 874--897
Andrew Chi Chih Yao On Parallel Computation for the Knapsack
Problem . . . . . . . . . . . . . . . . 898--903
R. P. Brent and
H. T. Kung Corrigendum: ``The Area-Time Complexity
of Binary Multiplication'' . . . . . . . 904--904
Fouad A. Tobagi Distributions of Packet Delay and
Interdeparture Time in Slotted ALOHA and
Carrier Sense Multiple Access . . . . . 907--927
James A. Storer and
Thomas G. Szymanski Data Compression via Textual
Substitution . . . . . . . . . . . . . . 928--951
Ronald Fagin Horn Clauses and Database Dependencies 952--985
John Grant and
Barry E. Jacobs On the Family of Generalized Dependency
Constraints . . . . . . . . . . . . . . 986--997
Christos H. Papadimitriou A Theorem in Database Concurrency
Control . . . . . . . . . . . . . . . . 998--1006
John C. Beatty On the Relationship Between the LL(1)
and LR(1) Grammars . . . . . . . . . . . 1007--1022
Toshimi Minoura Deadlock Avoidance Revisited . . . . . . 1023--1048
Eugene W. Stark Semaphore Primitives and Starvation-Free
Mutual Exclusion . . . . . . . . . . . . 1049--1072
Leslie M. Goldschlager A Universal Interconnection Pattern for
Parallel Computers . . . . . . . . . . . 1073--1086
Thomas Lengauer and
Robert E. Tarjan Asymptotically Tight Bounds on
Time-Space Trade-offs in a Pebble Game 1087--1130
David W. Matula Basic Digit Sets for Radix
Representation . . . . . . . . . . . . . 1131--1143
Carl H. Smith The Power of Pluralism for Automatic
Program Synthesis . . . . . . . . . . . 1144--1165
Esko Ukkonen The Equivalence Problem for Some
Non-Real-Time Deterministic Pushdown
Automata . . . . . . . . . . . . . . . . 1166--1181
A. Bagchi and
A. Mahanti Search Algorithms Under Different Kinds
of Heuristics--A Comparative Study . . . 1--21
Dennis de Champeaux Bidirectional Heuristic Search Again . . 22--32
D. V. Sarwate A Note on ``A Note on Multiple Error
Detection in ASCII Numeric Data
Communication'' . . . . . . . . . . . . 33--35
Anthony Klug Locking Expressions for Increased
Database Concurrency . . . . . . . . . . 36--54
Henry F. Korth Locking Primitives in a Database System 55--79
Greg N. Frederickson Implicit Data Structures for the
Dictionary Problem . . . . . . . . . . . 80--94
H. A. Maurer and
A. Salomaa and
D. Wood A Supernormal-Form Theorem for
Context-Free Grammars . . . . . . . . . 95--102
R. E. Lord and
J. S. Kowalik and
S. P. Kumar Solving Linear Algebraic Equations on an
MIMD Computer . . . . . . . . . . . . . 103--117
Bezalel Gavish Formulations and Algorithms for the
Capacitated Minimal Directed Tree
Problem . . . . . . . . . . . . . . . . 118--132
Ravindran Kannan Polynomial-Time Aggregation of Integer
Programming Problems . . . . . . . . . . 133--145
R. Schassberger and
H. Daduna The Time for a Round Trip in a Cycle of
Exponential Queues . . . . . . . . . . . 146--150
Steven Fortune and
Daniel Leivant and
Michael O'Donnell The Expressiveness of Simple and
Second-Order Type Structures . . . . . . 151--185
H. R. Strong Vector Execution of Flow Graphs . . . . 186--196
Krzysztof R. Apt Formal Justification of a Proof System
for Communicating Sequential Processes 197--216
Oscar H. Ibarra and
Shlomo Moran Probabilistic Algorithms for Deciding
Equivalence of Straight-Line Programs 217--228
Jeffrey Scott Vitter Analysis of the Search Performance of
Coalesced Hashing . . . . . . . . . . . 231--258
Seppo Sippu and
Eljas Soisalon-Soininen and
Esko Ukkonen The Complexity of LALR(k) Testing . . . 259--270
G. W. Stewart Computable Error Bounds for Aggregated
Markov Chains . . . . . . . . . . . . . 271--285
K. M. Chandy and
A. J. Martin A Characterization of Product-Form
Queueing Networks . . . . . . . . . . . 286--299
Jeffrey M. Jaffe Decentralized Simulation of Resource
Managers . . . . . . . . . . . . . . . . 300--322
Daniel Brand and
Pitro Zafiropulo On Communicating Finite-State Machines 323--342
C. Farshid Nourani Abstract Implementations and their
Correctness Proofs . . . . . . . . . . . 343--359
Zvi Galil and
Wolfgang J. Pauli An Efficient General-Purpose Parallel
Computer . . . . . . . . . . . . . . . . 360--387
Michael Tarsi Optimal Search on Some Game Trees . . . 389--396
Arnold L. Rosenberg Three-Dimensional VLSI: A Case Study . . 397--416
David W. Matula and
Leland L. Beck Smallest-Last Ordering and Clustering
and Graph Coloring Algorithms . . . . . 417--427
Kenneth J. Supowit The Relative Neighborhood Graph, with an
Application to Minimum Spanning Trees 428--448
Eshrat Arjomandi and
Michael J. Fischer and
Nancy A. Lynch Efficiency of Synchronous Versus
Asynchronous Distributed Systems . . . . 449--456
E. G. Coffman, Jr. and
Ravi Sethi Instruction Sets for Evaluating
Arithmetic Expressions . . . . . . . . . 457--478
Catriel Beeri and
Ronald Fagin and
David Maier and
Mihalis Yannakakis On the Desirability of Acyclic Database
Schemes . . . . . . . . . . . . . . . . 479--513
Ronald Fagin Degrees of Acyclicity for Hypergraphs
and Relational Database Schemes . . . . 514--550
Dan Gusfield Parametric Combinatorial Computing and a
Problem of Program Module Distribution 551--563
Rajan Suri Robustness of Queuing Network Formulas 564--594
Jean-Claude Raoult and
Ravi Sethi Properties of a Notation for Combining
Functions . . . . . . . . . . . . . . . 595--611
Edmund M. Clarke, Jr. and
Steven M. German and
Joseph Y. Halpern Effective Axiomatizations of Hoare
Logics . . . . . . . . . . . . . . . . . 612--636
Georg Gati The Complexity of Solving Polynomial
Equations by Quadrature . . . . . . . . 637--640
Oscar H. Ibarra and
Brian S. Leininger On the Simplification and Equivalence
Problems for Straight-Line Programs . . 641--656
Joseph Ja'Ja' Time-Space Trade-Offs for Some Algebraic
Problems . . . . . . . . . . . . . . . . 657--667
L. Lamport The Weak Byzantine Generals Problem . . 668--676
Xu Mei-Rui and
John E. Doner and
Ronald V. Book Refining Nondeterminism in
Relativizations of Complexity Classes 677--685
Dana S. Nau Decision Quality As a Function of Search
Depth on Game Trees . . . . . . . . . . 687--708
Jia-Wei Hong and
Kurt Mehlhorn and
Arnold L. Rosenberg Cost Trade-offs in Graph Embeddings,
with Applications . . . . . . . . . . . 709--728
Avi Wigderson Improving the Performance Guarantee for
Approximate Graph Coloring . . . . . . . 729--735
Toshihide Ibaraki and
Hussein M. Abdel-Wahab and
Tiko Kameda Design of Minimum-Cost Deadlock-Free
Systems . . . . . . . . . . . . . . . . 736--751
Giorgio Ausiello and
Alessandro D'Atri and
Domenico Sacc\`a Graph Algorithms for Functional
Dependency Manipulation . . . . . . . . 752--766
Nathan Goodman and
Oded Shmueli Syntactic Characterization of Tree
Database Schemas . . . . . . . . . . . . 767--786
Zvi M. Kedem and
Abraham Silberschatz Locking Protocols: From Exclusive to
Shared Locks . . . . . . . . . . . . . . 787--804
Per-Åke Larson Analysis of Uniform Hashing . . . . . . 805--819
Yael Krevner and
Amiram Yehudai An Iteration Theorem for Simple
Precedence Languages . . . . . . . . . . 820--833
Bruce Hajek The Proof of a Folk Theorem on Queuing
Delay with Applications to Routing in
Networks . . . . . . . . . . . . . . . . 834--851
Nimrod Megiddo Applying Parallel Computation Algorithms
in the Design of Serial Algorithms . . . 852--865
Robert E. Shostak Deciding Combinations of Theories . . . 1--12
H. J. Hoover and
M. M. Klawe and
N. J. Pippenger Bounding Fan-out in Logical Networks . . 13--18
Peter Eades and
Michael Hickey and
Ronald C. Read Some Hamilton Paths and a Minimal Change
Algorithm . . . . . . . . . . . . . . . 19--29
Catriel Beeri and
Martin Dowd and
Ronald Fagin and
Richard Statman On the Structure of Armstrong Relations
for Functional Dependencies . . . . . . 30--46
Lawrence J. Henschen and
Shamim A. Naqvi On Compiling Queries in Recursive
First-Order Databases . . . . . . . . . 47--85
Aurel A. Lazar Optimal Flow Control of an M/M/m Queue 86--98
Sidnie Dresher Feit A Fast Algorithm for the Two-Variable
Integer Programming Problem . . . . . . 99--113
Nimrod Megiddo Linear Programming in Linear Time When
the Dimension Is Fixed . . . . . . . . . 114--127
O. J. Boxma and
F. P. Kelly and
A. G. Konheim The Product Form for Sojourn Time
Distributions in Cyclic Exponential
Queues . . . . . . . . . . . . . . . . . 128--133
B. Simon Priority Queues with Feedback . . . . . 134--149
J. Ja'Ja' and
V. K. Prasanna Kumar Information Transfer in Distributed
Computing with Applications to VLSI . . 150--162
Douglas R. Smith Random Trees and the Analysis of Branch
and Bound Procedures . . . . . . . . . . 163--188
Allan Gottlieb and
Clyde P. Kruskal Complexity Results for Permuting Data
and Other Computations on Parallel
Processors . . . . . . . . . . . . . . . 193--209
Richard Hull Finitely Specifiable Implicational
Dependency Families . . . . . . . . . . 210--226
Mihalis Yannakakis Serializability by Locking . . . . . . . 227--244
Robert E. Tarjan and
Jan van Leeuwen Worst-Case Analysis of Set Union
Algorithms . . . . . . . . . . . . . . . 245--281
Karel Culik, II and
Tero Harju The $\omega$-Sequence Equivalence
Problem for D0L Systems Is Decidable . . 282--298
H. B. Hunt III Terminating Turing Machine Computations
and the Complexity and/or Decidability
of Correspondence Problems, Grammars,
and Program Schemes . . . . . . . . . . 299--318
C. W. Clenshaw and
F. W. J. Olver Beyond Floating Point . . . . . . . . . 319--328
George M. Trojan Lower Bounds and Fast Algorithms for
Sequence Acceleration . . . . . . . . . 329--335
Hans Röck The Three-Machine No-Wait Flow Shop Is
NP-Complete . . . . . . . . . . . . . . 336--345
J. McKenna and
Debasis Mitra Asymptotic Expansions and Integral
Representations of Moments of Queue
Lengths in Closed Markovian Networks . . 346--360
Akeo Adachi and
Shigeki Iwata and
Takumi Kasai Some Combinatorial Game Problems Require
${\Omega}(n^k)$ Time . . . . . . . . . . 361--376
Joseph Ja'Ja' The VLSI Complexity of Selected Graph
Problems . . . . . . . . . . . . . . . . 377--391
Christos H. Papadimitriou On the Complexity of Unique Solutions 392--400
John H. Reif Symmetric Complementation . . . . . . . 401--421
John E. Savage Space-Time Trade-Offs for Banded Matrix
Problems . . . . . . . . . . . . . . . . 422--437
Robert S. Boyer and
J. Strother Moore A Mechanical Proof of the Unsolvability
of the Halting Problem . . . . . . . . . 441--458
Yuri Gurevich and
Larry Stockmeyer and
Uzi Vishkin Solving NP-Hard Problems on Graphs That
Are Almost Trees and an Application to
Facility Location Problems . . . . . . . 459--473
François Baccelli and
Erol Gelenbe and
Brigitte Plateau An End-to-End Approach to the
Resequencing Problem . . . . . . . . . . 474--485
Ajoy Datta and
S. Ghosh Synthesis of a Class of Deadlock-Free
Petri Nets . . . . . . . . . . . . . . . 486--506
Eli Upfal Efficient Schemes for Parallel
Communication . . . . . . . . . . . . . 507--517
Richard Hull and
Chee K. Yap The Format Model: A Theory of Database
Organization . . . . . . . . . . . . . . 518--537
Michael L. Fredman and
János Komlós and
Endre Szemerédi Storing a Sparse Table with ${O(1)}$
Worst Case Access Time . . . . . . . . . 538--544
J. F. Traub and
H. Wo\'zniakowski On the Optimal Solution of Large Linear
Systems . . . . . . . . . . . . . . . . 545--559
S. D. Brookes and
C. A. R. Hoare and
A. W. Roscoe A Theory of Communicating Sequential
Processes . . . . . . . . . . . . . . . 560--599
John McLean A Formal Method for the Abstract
Specification of Software . . . . . . . 600--627
Micha Hofri Analysis of Interleaved Storage via a
Constant-Service Queuing System with
Markov-Chain-Driven Input . . . . . . . 628--648
Mikhail J. Atallah and
S. Rao Kosaraju Graph Problems on a Mesh-Connected
Processor Array . . . . . . . . . . . . 649--667
Friedhelm Meyer auf der Heide A Polynomial Linear Search Algorithm for
the $n$-Dimensional Knapsack Problem . . 668--676
S. G. Williamson Depth-First Search and Kuratowski
Subgraphs . . . . . . . . . . . . . . . 681--693
Jonathan W. Greene and
Abbas El Gamal Configuration of VLSI Arrays in the
Presence of Defects . . . . . . . . . . 694--717
Catriel Beeri and
Moshe Y. Vardi A Proof Procedure for Data Dependencies 718--741
Stavros S. Cosmadakis and
Christos H. Papadimitriou Updates of Relational Views . . . . . . 742--760
Tomasz Imieli\'nski and
Witold Lipski, Jr. Incomplete Information in Relational
Databases . . . . . . . . . . . . . . . 761--791
A. Boja\'nczyk Optimal Asynchronous Newton Method for
the Solution of Nonlinear Equations . . 792--803
P.-J. Courtois and
P. Semal Bounds for the Positive Eigenvectors of
Nonnegative Matrices and for Their
Approximations by Decomposition . . . . 804--825
A. R. Calderbank and
E. G. Coffman, Jr. and
L. Flatto Optimum Head Separation in a Disk System
with Two Read/Write Heads . . . . . . . 826--838
Benjamin Melamed and
Micha Yadin Numerical Computation of Sojourn-Time
Distributions in Queuing Networks . . . 839--854
Debasis Mitra and
P. J. Weinberger Probabilistic Models of Database
Locking: Solutions, Computational
Algorithms, and Asymptotics . . . . . . 855--878
P. A. Bloniarz and
H. B. Hunt, III and
D. J. Rosenkrantz Algebraic Structures with Hard
Equivalence and Minimization Problems 879--904
J. Pachl and
E. Korach and
D. Rotem Lower Bounds for Distributed
Maximum-Finding Algorithms . . . . . . . 905--918
A. Bagchi and
A. Mahanti Three Approaches to Heuristic Search in
Networks . . . . . . . . . . . . . . . . 1--27
A. Mahanti and
A. Bagchi AND/OR Graph Heuristic Search Methods 28--51
Leslie Lamport and
P. M. Melliar-Smith Synchronizing Clocks in the Presence of
Faults . . . . . . . . . . . . . . . . . 52--78
Serge Abiteboul Disaggregations in Databases . . . . . . 79--101
Ken Fuchs and
Dennis Kafura Memory-Constrained Task Scheduling on a
Network of Dual Processors . . . . . . . 102--129
Dorit S. Hochbaum and
Wolfgang Maass Approximation Schemes for Covering and
Packing Problems in Image Processing and
VLSI . . . . . . . . . . . . . . . . . . 130--136
Matthew Hennessy and
Robin Milner Algebraic Laws for Nondeterminism and
Concurrency . . . . . . . . . . . . . . 137--161
Hendrik Vantilborgh Aggregation with an Error of
${O}(\epsilon^2)$ . . . . . . . . . . . 162--190
Danny Dolev and
Rüdiger Reischuk Bounds on Information Exchange for
Byzantine Agreement . . . . . . . . . . 191--204
Shimon Even and
Alan L. Selman and
Yacov Yacobi Hard-Core Theorems for Complexity
Classes . . . . . . . . . . . . . . . . 205--217
Maria M. Klawe A Tight Bound for Black and White
Pebbles on the Pyramid . . . . . . . . . 218--228
J. C. Lagarias and
A. M. Odlyzko Solving Low-Density Subset Sum Problems 229--246
M. A. Bauer Soundness and Completeness of a
Synthesis Algorithm Based on Example
Computations . . . . . . . . . . . . . . 249--279
G. Gottlob and
A. Leitsch On the Efficiency of Subsumption
Algorithms . . . . . . . . . . . . . . . 280--295
Ching-Chy Wang and
Errol L. Lloyd and
Mary Lou Soffa Feedback Vertex Sets and Cyclically
Reducible Graphs . . . . . . . . . . . . 296--313
G. N. Buckley and
A. Silberschatz Beyond Two-Phase Locking . . . . . . . . 314--326
Brenda S. Baker and
Edward G. Coffman, Jr. and
Dan E. Willard Algorithms for Resolving Conflicts in
Dynamic Storage Allocation . . . . . . . 327--343
M. E. Gonzalez Smith and
J. A. Storer Parallel Algorithms for Data Compression 344--373
Michael J. Fischer and
Nancy A. Lynch and
Michael S. Paterson Impossibility of Distributed Consensus
with One Faulty Process . . . . . . . . 374--382
G. Cornuéjols and
D. Naddef and
W. Pulleyblank The Traveling Salesman Problem in Graphs
with $3$-Edge Cutsets . . . . . . . . . 383--410
John Staples and
V. L. Nguyen A Fixpoint Semantics for
Nondeterministic Data Flow . . . . . . . 411--444
Asser N. Tantawi and
Don Towsley Optimal Static Load Balancing In
Distributed Computer Systems . . . . . . 445--465
Eitan M. Gurari Decidable Problems for Powerful Programs 466--483
S. Skyum and
L. G. Valiant A Complexity Theory Based on Boolean
Algebra . . . . . . . . . . . . . . . . 484--502
Rina Dechter and
Judea Pearl Generalized Best-First Search Strategies
and the Optimality of A* . . . . . . . . 505--536
Edward A. Bender and
Jon T. Butler Enumeration of Structured Flowcharts . . 537--548
William H. Cunningham Optimal Attack and Reinforcement of a
Network . . . . . . . . . . . . . . . . 549--561
C. C. Lee and
D. T. Lee A Simple On-Line Bin-Packing Algorithm 562--572
Bernard Chazelle and
Louis Monier A Model of Computation for VLSI with
Related Complexity Results . . . . . . . 573--588
Albert G. Greenberg and
Shmuel Winograd A Lower Bound on the Time Needed in the
Worst Case to Resolve Conflicts
Deterministically in Multiple Access
Channels . . . . . . . . . . . . . . . . 589--596
Dan E. Willard and
George S. Lueker Adding Range Restriction Capability to
Dynamic Data Structures . . . . . . . . 597--617
Y. C. Tay and
Rajan Suri and
Nathan Goodman A Mean Value Performance Model for
Locking in Databases: The No-Waiting
Case . . . . . . . . . . . . . . . . . . 618--651
Daniel Dominic Sleator and
Robert Endre Tarjan Self-Adjusting Binary Search Trees . . . 652--686
Andrew C. Yao Uniform Hashing is Optimal . . . . . . . 687--693
David Zerling Generating Binary Trees Using Rotations 694--701
Wei-Lu Cao and
William J. Stewart Iterative Aggregation/Disaggregation
Techniques for Nearly Uncoupled Markov
Chains . . . . . . . . . . . . . . . . . 702--719
Udi Manber and
Martin Tompa Complexity of Problems on Probabilistic,
Nondeterministic, and Alternating
Decision Trees . . . . . . . . . . . . . 720--732
A. P. Sistla and
E. M. Clarke The Complexity of Propositional Linear
Temporal Logics . . . . . . . . . . . . 733--749
Christos H. Papadimitriou Correction to ``A Theorem in Database
Concurrency Control'' . . . . . . . . . 750--750
Eugene C. Freuder A Sufficient Condition for
Backtrack-Bounded Search . . . . . . . . 755--761
Richard M. Karp and
Avi Wigderson A Fast Parallel Algorithm for the
Maximal Independent Set Problem . . . . 762--773
Domenico Sacc\`a Closures of Database Hypergraphs . . . . 774--803
Baruch Awerbuch Complexity of Network Synchronization 804--823
Gabriel Bracha and
Sam Toueg Asynchronous Consensus and Broadcast
Protocols . . . . . . . . . . . . . . . 824--840
Hector Garcia-Molina and
Daniel Barbara How to Assign Votes in a Distributed
System . . . . . . . . . . . . . . . . . 841--860
Ulrich Faigle On Ordered Languages and the
Optimization of Linear Functions by
Greedy Algorithms . . . . . . . . . . . 861--870
Ilan Adler and
Nimrod Megiddo A Simplex Algorithm Whose Average Number
of Steps Is Bounded between Two
Quadratic Functions of the Smaller
Dimension . . . . . . . . . . . . . . . 871--895
M. Hennessy Acceptance Trees . . . . . . . . . . . . 896--928
Friedhelm Meyer Auf Der Heide Lower Bounds for Solving Linear
Diophantine Equations on Random Access
Machines . . . . . . . . . . . . . . . . 929--937
Shlomo Moran and
Marc Snir and
Udi Manber Applications of Ramsey's Theorem to
Decision Tree Complexity . . . . . . . . 938--949
Mihalis Yannakakis A Polynomial Algorithm for the Min-Cut
Linear Arrangement of Trees . . . . . . 950--988
Zohar Manna and
Richard Waldinger Special Relations in Automated Deduction 1--59
K. Mehlhorn and
F. P. Preparata Routing through a Rectangle . . . . . . 60--85
Benny Chor and
Charles E. Leiserson and
Ronald L. Rivest and
James B. Shearer An Application of Number Theory to the
Organization of Raster-Graphics Memory 86--104
Marc H. Graham and
Alberto O. Mendelzon and
Moshe Y. Vardi Notions of Dependency Satisfaction . . . 105--129
Boris Lubachevsky and
Debasis Mitra A Chaotic Asynchronous Algorithm for
Computing the Fixed Point of a
Nonnegative Matrix of Unit Spectral
Radius . . . . . . . . . . . . . . . . . 130--150
E. Allen Emerson and
Joseph Y. Halpern ``Sometimes'' and ``Not Never''
Revisited: On Branching versus Linear
Time Temporal Logic . . . . . . . . . . 151--178
Derek L. Eager and
Kenneth C. Sevcik Bound Hierarchies for Multiple-Class
Queuing Networks . . . . . . . . . . . . 179--206
Appie van de Liefvoort and
Lester Lipsky A Matrix-Algebraic Solution to Two
${K}_m$ Servers in a Loop . . . . . . . 207--223
David Harel Effective Transformations on Infinite
Trees, with Applications to High
Undecidability, Dominoes, and Fairness 224--248
Vincent J. Digricoli and
Malcolm C. Harrison Equality-Based Binary Resolution . . . . 253--289
Takao Asano and
Tetsuo Asano and
Hiroshi Imai Partitioning a Polygonal Region into
Trapezoids . . . . . . . . . . . . . . . 290--312
Leslie Lamport The Mutual Exclusion Problem: Part I ---
The Theory of Interprocess Communication 313--326
Leslie Lamport The Mutual Exclusion Problem: Part II
--- Statement and Solutions . . . . . . 327--348
Raymond Reiter A Sound and Sometimes Complete Query
Evaluation Algorithm for Relational
Databases with Null Values . . . . . . . 349--370
Philippe Flajolet and
Claude Puech Partial Match Retrieval of
Multidimensional Data . . . . . . . . . 371--407
Serge Abiteboul and
Seymour Ginsburg Tuple Sequences and Lexicographic
Indexes . . . . . . . . . . . . . . . . 409--422
Catriel Beeri and
Michael Kifer Elimination of Intersection Anomalies
from Database Schemes . . . . . . . . . 423--450
Francis Chin Security Problems on Inference Control
for SUM, MAX, and MIN queries . . . . . 451--464
Seymour Ginsburg and
Richard Hull Sort Sets in the Relational Model . . . 465--488
Luc Devroye A Note on the Height of Binary Search
Trees . . . . . . . . . . . . . . . . . 489--498
Danny Dolev and
Nancy A. Lynch and
Shlomit S. Pinter and
Eugene W. Stark and
William E. Weihl Reaching Approximate Agreement in the
Presence of Faults . . . . . . . . . . . 499--516
Thomas F. Coleman and
Anders Edenbrandt and
John R. Gilbert Predicting Fill for Sparse Orthogonal
Factorization . . . . . . . . . . . . . 517--532
Dorit S. Hochbaum and
David B. Shmoys A Unified Approach to Approximation
Algorithms for Bottleneck Problems . . . 533--550
Samar Singh Improved Methods for Storing and
Updating Information in the
Out-of-Kilter Algorithm . . . . . . . . 551--567
Debasis S. Mitra and
J. McKenna Asymptotic Expansions for Closed
Markovian Networks with State-Dependent
Service Rates . . . . . . . . . . . . . 568--592
John N. Tsitsiklis and
Christos H. Papadimitriou and
Pierre Humblet The Performance of a Precedence-Based
Queueing Discipline . . . . . . . . . . 593--602
Jose L. Balcázar and
Ronald V. Book and
Uwe Schöning The Polynomial-Time Hierarchy and Sparse
Oracles . . . . . . . . . . . . . . . . 603--617
Timothy J. Long and
Alan L. Selman Relativizing Complexity Classes with
Sparse Oracles . . . . . . . . . . . . . 618--627
Dennis de Champeaux Subproblem Finder and Instance Checker,
Two Cooperating Modules for Theorem
Provers . . . . . . . . . . . . . . . . 633--657
W. Eric L. Grimson The Combinatorics of Local Constraints
in Model-Based Recognition and
Localization from Sparse Data . . . . . 658--686
Vijaya Ramachandran On Driving Many Long Wires in a VLSI
Layout . . . . . . . . . . . . . . . . . 687--701
R. Chaudhuri and
A. N. V. Rao Approximating Grammar Probabilities:
Solution of a Conjecture . . . . . . . . 702--705
Bruce Jay Collings and
G. Barry Hembree Initializing Generalized Feedback Shift
Register Pseudorandom Number Generators 706--711
M. Cosnard and
Y. Robert Complexity of Parallel QR Factorization 712--723
K. R. Apt and
G. D. Plotkin Countable Nondeterminism and Random
Assignment . . . . . . . . . . . . . . . 724--767
A. E. Conway and
N. D. Georganas RECAL--A New Efficient Algorithm for the
Exact Analysis of Multiple-Chain Queuing
Networks . . . . . . . . . . . . . . . . 768--791
Oded Goldreich and
Shafi Goldwasser and
Silvio Micali How to Construct Random Functions . . . 792--807
R. Kannan and
R. J. Lipton Polynomial-Time Algorithm for the Orbit
Problem . . . . . . . . . . . . . . . . 808--821
John H. Rowland and
John R. Cowles Small Sample Algorithms for the
Identification of Polynomials . . . . . 822--829
B. Chazelle and
D. P. Dobkin Intersection of Convex Objects in Two
and Three Dimensions . . . . . . . . . . 1--27
Victor Vianu Dynamic Functional Dependencies and
Database Aging . . . . . . . . . . . . . 28--59
John H. Reif and
Leslie G. Valiant A Logarithmic Time Sort for Linear Size
Networks . . . . . . . . . . . . . . . . 60--76
Danny Dolev and
Cynthia Dwork and
Larry Stockmeyer On the Minimal Synchronism Needed for
Distributed Consensus . . . . . . . . . 77--97
Greg N. Frederickson and
Nancy A. Lynch Electing a Leader in a Synchronous Ring 98--115
Eli Upfal and
Avi Wigderson How to Share Memory in a Distributed
System . . . . . . . . . . . . . . . . . 116--127
Yoshihito Toyama On the Church-Rosser Property for the
Direct Sum of Term Rewriting Systems . . 128--143
Dorit S. Hochbaum and
David B. Shmoys Using Dual Approximation Algorithms for
Scheduling Problems: Theoretical and
Practical Results . . . . . . . . . . . 144--162
Rüdiger Reischuk Simultaneous WRITES of Parallel Random
Access Machines Do Not Help to Compute
Simple Arithmetic Functions . . . . . . 163--178
Lorenzo Donatiello and
Balakrishna R. Iyer Analysis of a Composite Performance
Reliability Measure for Fault-Tolerant
Systems . . . . . . . . . . . . . . . . 179--199
Richard Cole Slowing Down Sorting Networks to Obtain
Faster Sorting Algorithms . . . . . . . 200--208
Alasdair Urquhart Hard Examples for Resolution . . . . . . 209--219
Neil V. Murray and
Erik Rosenthal Inference with Path Resolution and
Semantic Graphs . . . . . . . . . . . . 225--254
Wen-Lian Hsu Recognizing Planar Perfect Graphs . . . 255--288
Albert G. Greenberg and
Philippe Flajolet and
Richard E. Ladner Estimating the Multiplicities of
Conflicts to Speed Their Resolution in
Multiple Access Channels . . . . . . . . 289--325
Yann-Hang Lee and
Kang G. Shin Optimal Reconfiguration Strategy for a
Degradable Multimodule Computing System 326--348
Edward P. F. Chan and
Alberto O. Mendelzon Answering Queries on Embedded-Complete
Database Schemes . . . . . . . . . . . . 349--375
Christos A. Papachristou Associative Table Lookup Processing for
Multioperand Residue Arithmetic . . . . 376--396
Georg Ch. Pflug and
Hans W. Kessler Linear Probing with a Nonuniform Address
Distribution . . . . . . . . . . . . . . 397--410
Pierpaolo Degano and
Ugo Montanari A Model for Distributed Systems Based on
Graph Rewriting . . . . . . . . . . . . 411--449
David Peleg Concurrent Dynamic Logic . . . . . . . . 450--479
Steven Homer Minimal Degrees for Polynomial
Reducibilities . . . . . . . . . . . . . 480--491
K. N. Venkataraman Decidability of the Purely Existential
Fragment of the Theory of Term Algebras 492--510
Zvi Galil and
Christoph M. Hoffmann and
Eugene M. Luks and
Claus P. Schnorr and
Andreas Weber An ${O}(n^3 \log n)$ Deterministic and
an ${O}(n^3)$ Las Vegas Isomorphism Test
for Trivalent Graphs . . . . . . . . . . 513--531
Robert W. Irving and
Paul Leather and
Dan Gusfield An Efficient Algorithm for the
``Optimal'' Stable Marriage . . . . . . 532--543
Catriel Beeri and
Michael Kifer A Theory of Intersection Anomalies in
Relational Database Schemes . . . . . . 544--577
A. Blumer and
J. Blumer and
D. Haussler and
R. McConnell and
A. Ehrenfeucht Complete Inverted Files for Efficient
Text Retrieval and Analysis . . . . . . 578--595
Michael L. Fredman and
Robert Endre Tarjan Fibonacci Heaps and Their Uses in
Improved Network Optimization Algorithms 596--615
D. S. Hirschberg and
L. L. Larmore New Applications of Failure Functions 616--625
T. K. Srikanth and
Sam Toueg Optimal Clock Synchronization . . . . . 626--645
Stanley Cabay and
Bart Domzy Systems of Linear Equations with Dense
Univariate Polynomial Coefficients . . . 646--660
Randolph Nelson Stochastic Catastrophe Theory in
Computer Performance Modeling . . . . . 661--685
Rajan Suri Infinitesimal Perturbation Analysis for
General Discrete Event Systems . . . . . 686--717
Ronald V. Book and
Ding-Zhu Du The Existence and Density of Generalized
Complexity Cores . . . . . . . . . . . . 718--730
Michio Oyamaguchi The Equivalence Problem for Real-Time
DPDAs . . . . . . . . . . . . . . . . . 731--760
Alfred Inselberg and
Tuval Chomut and
Mordechai Reif Convexity Algorithms in Parallel
Coordinates . . . . . . . . . . . . . . 765--801
Debasis Mitra and
Randall A. Cieslak Randomized Parallel Communications on an
Extension of the Omega Network . . . . . 802--824
Jeffrey Scott Vitter Design and Analysis of Dynamic Huffman
Codes . . . . . . . . . . . . . . . . . 825--845
Dan E. Willard Multidimensional Search Trees That
Provide New Types of Memory Reductions 846--858
Joshua J. Bloch and
Dean S. Daniels and
Alfred Z. Spector A Weighted Voting Algorithm for
Replicated Directories . . . . . . . . . 859--909
Gabriel Bracha An ${O}(\log n)$ Expected Rounds
Randomized Byzantine Generals Protocol 910--920
Prasoon Tiwari Lower Bounds on Communication Complexity
in Distributed Computer Networks . . . . 921--938
Shu Tezuka On the Discrepancy of GFSR Pseudorandom
Numbers . . . . . . . . . . . . . . . . 939--949
Donald B. Johnson Parallel Algorithms for Minimum Cuts and
Maximum Flows in Planar Networks . . . . 950--967
Michael Kaminski A Linear Time Algorithm for Residue
Computation and a Fast Algorithm for
Division with a Sparse Divisor . . . . . 968--984
James McKenna Asymptotic Expansions of the Sojourn
Time Distribution Functions of Jobs in
Closed, Product-Form Queuing Networks 985--1003
Miklos Ajtai and
Yuri Gurevich Monotone versus Positive . . . . . . . . 1004--1015
Y. Sagiv and
C. Delobel and
D. S. Parker, Jr. and
Ronald Fagin Correction to ``An Equivalence between
Relational Database Dependencies and a
Fragment of Propositional Logic'' . . . 1016--1018
Christoph Walther Many-Sorted Unification . . . . . . . . 1--17
N. Megiddo and
S. L. Hakimi and
M. R. Garey and
D. S. Johnson and
C. H. Papadimitriou The Complexity of Searching a Graph . . 18--44
Yann-Hang Lee and
Kang G. Shin Optimal Design and Use of Retry in
Fault-Tolerant Computer Systems . . . . 45--69
Serge Abiteboul and
Victor Vianu Equivalence and Optimization of
Relational Transactions . . . . . . . . 70--120
Vassos Hadzilacos A Theory of Reliability in Database
Systems . . . . . . . . . . . . . . . . 121--145
Anthony Klug On Conjunctive Queries Containing
Inequalities . . . . . . . . . . . . . . 146--160
Gaston H. Gonnet and
Per-Åke Larson External Hashing with Limited Internal
Storage . . . . . . . . . . . . . . . . 161--184
Timothy Hickey and
Jacques Cohen Automating Program Analysis . . . . . . 185--220
Satish K. Tripathi and
C. Murray Woodside A Vertex-Allocation Theorem for
Resources in Queuing Networks . . . . . 221--230
Erich Kaltofen Greatest Common Divisors of Polynomials
Given by Straight-Line Programs . . . . 231--264
Avikam Baltsan and
Micha Sharir On the shortest paths between two convex
polyhedra . . . . . . . . . . . . . . . 267--287
Cynthia Dwork and
Nancy Lynch and
Larry Stockmeyer Consensus in the Presence of Partial
Synchrony . . . . . . . . . . . . . . . 288--323
Robert McNaughton and
Paliath Narendran and
Friedrich Otto Church-Rosser Thue Systems and Formal
Languages . . . . . . . . . . . . . . . 324--344
Jeffrey D. Ullman and
Allen Van Gelder Efficient Tests for Top-Down Termination
of Logical Rules . . . . . . . . . . . . 345--373
Zvi Galil and
Éva Tardos An ${O}(n^2 (m + n \log n ) \log n)$
Min-Cost Flow Algorithm . . . . . . . . 374--386
Galen H. Sasaki and
Bruce Hajek The Time Complexity of Maximum Matching
by Simulated Annealing . . . . . . . . . 387--403
Ravinderpal Singh Sandhu The Schematic Protection Model: Its
Definition and Analysis for Acyclic
Attenuation Schemes . . . . . . . . . . 404--432
A. R. Calderbank and
E. G. Coffman, Jr. and
Leopold Flatto Optimal Directory Placement on Disk
Storage Devices . . . . . . . . . . . . 433--446
Helmut Alt Comparing the Combinational Complexities
of Arithmetic Functions . . . . . . . . 447--460
Ingo Wegener On the Complexity of Branching Programs
and Decision Trees for Clique Functions 461--471
N. Shankar A Mechanical Proof of the Church-Rosser
Theorem . . . . . . . . . . . . . . . . 475--522
Merrick L. Furst and
Jonathan L. Gross and
Lyle A. McGeoch Finding a Maximum-Genus Graph Imbedding 523--534
Wen-Lian Hsu The Coloring and Maximum Independent Set
Problems on Planar Perfect Graphs . . . 535--563
Wansoo T. Rhee and
Michel Talagrand Some Distributions That Allow Perfect
Packing . . . . . . . . . . . . . . . . 564--578
Jonathan Goodman and
Albert G. Greenberg and
Neal Madras and
Peter March Stability of Binary Exponential Backoff 579--602
Lenwood S. Heath and
Arnold L. Rosenberg and
Bruce T. Smith The Physical Mapping Problem for
Parallel Architectures . . . . . . . . . 603--634
S. Rao Kosaraju and
Mikhail J. Atallah Optimal Simulations between
Mesh-Connected Arrays of Processors . . 635--650
Faith E. Fich and
Martin Tompa The Parallel Complexity of
Exponentiating Polynomials over Finite
Fields . . . . . . . . . . . . . . . . . 651--667
Hans Daduna Busy Periods for Subnetworks in
Stochastic Networks: Mean Value Analysis 668--674
Jan Robin Rohlicek and
Alan S. Willsky The Reduction of Perturbed Markov
Generators: An Algorithm Exposing the
Role of Transient States . . . . . . . . 675--696
Jik H. Chang and
Oscar H. Ibarra and
Anastasios Vergis On the Power of One-Way Communication 697--726
Michael R. Fellows and
Michael A. Langston