9. STOC 1977: Boulder, Colorado, USA
John E. Hopcroft, Emily P. Friedman, Michael A. Harrison (Eds.):
Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA.
ACM 1977
- Alon Itai:
Finding a Minimum Circuit in a Graph.
1-10

- Andrew Chi-Chih Yao, David Avis, Ronald L. Rivest:
An Omega(n^2 log n) Lower Bound to the Shortest Paths Problem.
11-17

- Robert Endre Tarjan:
Reference Machines Require Non-linear Time to Maintain Disjoint Sets.
18-29

- Dana Angluin, Leslie G. Valiant:
Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings.
30-41

- Mark R. Brown:
The Complexity of Priority Queue Maintenance.
42-48

- Leonidas J. Guibas, Edward M. McCreight, Michael F. Plass, Janet R. Roberts:
A New Representation for Linear Lists.
49-60

- George S. Sacerdote, Richard L. Tenney:
The Decidability of the Reachability Problem for Vector Addition Systems (Preliminary Version).
61-76

- Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
77-90

- Gary L. Peterson, Michael J. Fischer:
Economical Solutions for the Critical Section Problem in a Distributed System (Extended Abstract).
91-97

- Arnie Rosenthal:
Nonserial Dynamic Programming Is Optimal.
98-105

- Larry Carter, Mark N. Wegman:
Universal Classes of Hash Functions (Extended Abstract).
106-112

- Gaston H. Gonnet, J. Ian Munro:
The Analysis of an Improved Hashing Technique.
113-121

- John C. Beatty:
Iteration Theorems for LL(k) Languages.
122-131

- Bhaskaram Prabhala, Ravi Sethi:
A Comparison of Instruction Sets for Stack Machines.
132-142

- Gary L. Miller:
Graph Isomorphism, General Remarks.
143-150

- Leonard M. Adleman, Kenneth L. Manders:
Reducibility, Randomness, and Intractability (Abstract).
151-163

- Dexter Kozen:
Complexity of Finitely Presented Algebras.
164-177

- Chandra M. R. Kintala, Patrick C. Fischer:
Computations with a Restricted Number of Nondeterministic Steps (Extended Abstract).
178-185

- István Simon, John Gill:
Polynomial Reducibilities and Upward Diagonalizations.
186-194

- Janos Simon:
On Feasible Numbers (Preliminary Version).
195-207

- Ivan Hal Sudborough:
Separating Tape Bounded Auxiliary Pushdown Automata Classes.
208-217

- Wolfgang J. Paul:
On Time Hierarchies.
218-222

- Juris Hartmanis:
Relations Between Diagonalization, Proof Systems, and Complexity Gaps (Preliminary Version).
223-227

- Nancy A. Lynch, Edward K. Blum:
Efficient Reducibility Between Programming Systems: Preliminary Report.
228-238

- Benton L. Leong, Joel I. Seiferas:
New Real-Time Simulations of Multihead Tape Units.
239-248

- David Harel, Amir Pnueli, Jonathan Stavi:
A Complete Axiomatic System for Proving Deductions about Recursive Programs.
249-260

- David Harel, Albert R. Meyer, Vaughan R. Pratt:
Computability and Completeness in Logics of Programs (Preliminary Report).
261-268

- Robert L. Constable:
On the Theory of Programming Logics.
269-285

- Michael J. Fischer, Richard E. Ladner:
Propositional Modal Logic of Programs (Extended Abstract).
286-294

- Mike O'Donnell:
Subtree Replacement Systems: A Unifying Theory for Recursive Equations, LISP, Lucid and Combinatory Logic.
295-305

- Matthew Hennessy, Edward A. Ashcroft:
Parameter-Passing Mechanisms and Nondeterminism.
306-311

Last update Thu May 23 18:02:02 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page