Journal of the ACM, Volume 29, 1982

Volume 29, Number 1, January 1982

• George W. Ernst, Michael M. Goldstein:
  Mechanical Discovery of Classes of Problem-Solving Strategies. 1-23
  
• Eugene C. Freuder:
  A Sufficient Condition for Backtrack-Free Search. 24-32
  
• Drew V. McDermott:
  Nonmonotonic Logic II: Nonmonotonic Modal Theories. 33-57
  
• Ronald I. Becker, Stephen R. Schach, Yehoshua Perl:
  A Shifting Algorithm for Min-Max Tree Partitioning. 58-67
  
• Christoph M. Hoffmann, 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, Scott F. Walecka:
  Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued Dependencies. 103-117
  
• Hermann A. Maurer, Arto Salomaa, Derick Wood:
  Dense Hierarchies of Grammatical Families. 118-126
  
• D. Chow, Clement T. Yu:
  On the Construction of Feedback Queries. 127-151
  
• Clement T. Yu, K. Lam, Gerard 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, Paul Jackson, Nancy A. Lynch, Michael J. Fischer, Gary L. Peterson:
  Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable. 183-205
  
• Hans-Dieter Ehrich:
  On the Theory of Specification, Implementation, and Parametrization of Abstract Data Types. 206-227
  
• Harry 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
  

Volume 29, Number 2, April 1982

• Steve Winker:
  Generation and Verification of Finite Models and Counterexamples Using an Automated Theorem Prover Answering Two Open Questions. 273-284
  
• Christos H. Papadimitriou, 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, 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, Arnaldo Moura:
  A Generalization of Ogden's Lemma. 404-407
  
• Jacques Cohen, Timothy J. Hickey, Joel Katcoff:
  Upper Bounds for Speedup in Parallel Parsing. 408-428
  
• Harry 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, Izidor Gertner:
  An Approach to Program Behavior Modeling and Optimal Memory Control. 527-554
  
• Albert R. Meyer, Joseph Y. Halpern:
  Axiomatic Definitions of Programming Languages: A Theoretical Assessment. 555-576
  
• Michael A. Arbib, Ernest G. Manes:
  The Pattern-of-Calls Expansion Is the Canonical Fixpoint for Recursive Definitions. 577-602
  

Volume 29, Number 3, July 1982

• Robert W. Floyd, Jeffrey D. Ullman:
  The Compilation of Regular Expressions into Integrated Circuits. 603-622
  
• K. Takamizawa, Takao Nishizeki, Nobuji Saito:
  Linear-time computability of combinatorial problems on series-parallel graphs. 623-641
  
• David Nassimi, 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, Sami Mohammed Zaiddan:
  Properties of functional-dependency families. 678-698
  
• Anthony C. 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 U. Martel:
  Preemptive Scheduling with Release Times, Deadlines, and Due Times. 812-829
  
• Christopher L. Samelson, 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, Maarten H. van Emden:
  Contributions to the Theory of Logic Programming. 841-862
  
• Eitan M. Gurari, Oscar H. Ibarra:
  Two-Way Counter Machines and Diophantine Equations. 863-873
  
• Mark Jerrum, 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
  
• Richard P. Brent, H. T. Kung:
  Corrigendum: ``The Area-Time Complexity of Binary Multiplication''. 904
  

Volume 29, Number 4, October 1982

• Fouad A. Tobagi:
  Distributions of packet delay and interdeparture time in slotted ALOHA and carrier sense multiple access. 907-927
  
• James A. Storer, Thomas G. Szymanski:
  Data compression via textural substitution. 928-951
  
• Ronald Fagin:
  Horn clauses and database dependencies. 952-985
  
• John Grant, 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 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, Robert Endre 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