18. FOCS 1977: Providence, Rhode Island, USA

18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977. IEEE Computer Society 1977

Session I

Richard J. Lipton:
A Necessary and Sufficient Condition for the Existence of Hoare Logics. 1-6
Daniel J. Lehmann, Michael B. Smyth:
Data Types (Extended Abstract). 7-12
Michael B. Smyth, Gordon D. Plotkin:
The Category-Theoretic Solution of Recursive Domain Equations (Extended Abstract). 13-17
Edmund M. Clarke:
Program Invariants as Fixed Points (Preliminary Reports). 18-29
Gérard P. Huet:
Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems. 30-45
Amir Pnueli:
The Temporal Logic of Programs. 46-57

Ronald V. Book:
Language Representation Theorems: How to Generate the R. E. Sets from the Regular Sets. 58-61
Harry R. Lewis:
A New Decidable Problem, with Applications (Extended Abstract). 62-73
Oscar H. Ibarra:
The Unsolvability of the Equivalence Problem for epsilon-free NGSM's with Unary Input (Output) Alphabet and Applications. 74-81
Howard P. Katseff, Michael Sipser:
Several Results in Program Size Complexity. 82-89
Richard Statman:
The Typed lambda-Calculus Is not Elementary Recursive. 90-94
Leonard Berman:
Precise Bounds for Presburger Arithmetic and the Reals with Addition: Preliminary Report. 95-99
Victor L. Bennison, Robert I. Soare:
Recursion Theoretic Characterizations of Complexity Theoretic Properties. 100-106

Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman:
The Theory of Joins in Relational Data Bases (Extended Abstract). 107-113
Greg Nelson, Derek C. Oppen:
Fast Decision Algorithms Based on Union and Find. 114-119
H. T. Kung, S. W. Song:
An Efficient Parallel Garbage Collection System and Its Correctness Proof. 120-131
David Maier:
A Space Efficient Method for the Lowest Common Ancestor Problem and an Application to Finding Negative Cycles. 132-141
Lawrence Snyder:
On Uniquely Represented Data Structures (Extended Abstract). 142-146
Manuel Blum, William J. Sakoda:
On the Capability of Finite Automata in 2 and 3 Dimensional Space. 147-161

Richard J. Lipton, Robert Endre Tarjan:
Application of a Planar Separator Theorem. 162-170
Laurent Hyafil:
The Power of Commutativity. 171-174
Leonard M. Adleman, Kenneth L. Manders, Gary L. Miller:
On Taking Roots in Finite Fields. 175-178
Zvi Galil, Joel I. Seiferas:
Saving Space in Fast String-Matching. 179-188
Leonidas J. Guibas, Andrew M. Odlyzko:
A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm. 189-195
Philippe Flajolet, Jean-Claude Raoult, Jean Vuillemin:
On the Average Number of Registers Required for Evaluating Arithmetic Expressions. 196-205

Eugene L. Lawler:
Fast Approximation Algorithms for Knapsack Problems. 206-213
Edward G. Coffman Jr., Joseph Y.-T. Leung:
Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation. 214-221
Andrew Chi-Chih Yao:
Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). 222-227
Errol L. Lloyd:
On Triangulations of a Set of Points in the Plane. 228-240
David A. Plaisted:
New NP-Hard and NP-Complete Polynomial and Integer Divisibility Problems. 241-253
Dexter Kozen:
Lower Bounds for Natural Proof Systems. 254-266

Last update Fri May 25 08:14:14 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page