11. STOC 1979
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA. ACM 1979
- Jacobo Valdes, Robert Endre Tarjan, Eugene L. Lawler:
The recognition of Series Parallel digraphs.
1-12 BibTeX
- Zvi Galil, Amnon Naamad:
Network Flow and Generalized Path Compression.
13-26 BibTeX
- I. S. Filotti, Gary L. Miller, John H. Reif:
On Determining the Genus of a Graph in O(v^O(g)) Steps.
27-37 BibTeX
- Bernard Chazelle, David P. Dobkin:
Decomposing a Polygon into its Convex Parts.
38-48 BibTeX
- Philippe Flajolet, Jean Françon, Jean Vuillemin:
Computing Integrated Costs of Sequences of Operations with Application to Dictionaries.
49-61 BibTeX
- Michael L. Fredman:
A Near Optimal Data Structure for a Type of Range Query Problem.
62-66 BibTeX
- S. Rao Kosaraju:
On a Multidimensional Search Problem (Preliminary Version).
67-73 BibTeX
- Robert Sedgewick, Thomas G. Szymanski:
The Complexity of Finding Periods.
74-80 BibTeX
- Clark D. Thompson:
Area-Time Complexity for VLSI.
81-88 BibTeX
- Sam Toueg, Jeffrey D. Ullman:
Deadlock-Free Packet Switching Networks.
89-98 BibTeX
- Arnold L. Rosenberg, Derick Wood, Zvi Galil:
Storage Representations for Tree-Like Data Structures.
99-107 BibTeX
- J. Ian Munro, Hendra Suwanda:
Implicit Data Structures (Preliminary Draft).
108-117 BibTeX
- Adi Shamir:
On the Cryptocomplexity of Knapsack Systems.
118-129 BibTeX
- Dana Angluin:
Finding Patterns Common to a Set of Strings (Extended Abstract).
130-141 BibTeX
- Eitan M. Gurari, Oscar H. Ibarra:
The Complexity of the Equivalence Problem for Counter Machines, Semilinear Sets, and Simple Programs.
142-152 BibTeX
- Richard A. DeMillo, Richard J. Lipton:
Some Connections between Mathematical Logic and Complexity Theory.
153-159 BibTeX
- Francine Berman:
A Completeness Technique for D-Axiomatizable Semantics.
160-166 BibTeX
- Albert R. Meyer, Karl Winklmann:
On the Expressive Power of Dynamic Logic (Preliminary Report).
167-175 BibTeX
- Michael O'Donnell:
A Programming Language Theorem Which Is Independent of Peano Arithmetic.
176-188 BibTeX
- Leslie G. Valiant:
Negation Can Be Exponentially Powerful.
189-196 BibTeX
- Joseph JáJá:
On the Complexity of Bilinear Forms with Commutativity.
197-208 BibTeX
- Andrew Chi-Chih Yao:
Some Complexity Questions Related to Distributive Computing (Preliminary Report).
209-213 BibTeX
- Richard E. Ladner:
The Complexity of Problems in Systems of Communicating Sequential Processes (Extended Abstract).
214-223 BibTeX
- Gary L. Peterson:
Time-Space Trade-Offs for Asynchronous Parallel Models: Reducibilities and Equivalences.
224-230 BibTeX
- John R. Gilbert, Thomas Lengauer, Robert Endre Tarjan:
The Pebbling Problem is Complete in Polynomial Space.
237-248 BibTeX
- Thomas Lengauer, Robert Endre Tarjan:
Upper and Lower Bounds on Time-Space Tradeoffs.
262-277 BibTeX
- Timothy J. Long:
On gamma-Reducibility versus Polynomial Time Many-One Reducibility (Extended Abstract).
278-287 BibTeX
- John H. Reif:
Universal Games of Incomplete Information.
288-308 BibTeX
- Ashok K. Chandra, David Harel:
Computable Queries for Relational Data Bases (Preliminary Report).
309-318 BibTeX
- Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalence of Relational Database Schemes.
319-329 BibTeX
- David Maier:
Minimum Covers in the Relational Database Model (Extended Abstract).
330-337 BibTeX
- Stephen A. Cook:
Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space.
338-345 BibTeX
- Walter L. Ruzzo:
Tree-Size Bounded Alternation.
352-359 BibTeX
- Michael Sipser:
Lower Bounds on the Size of Sweeping Automata.
360-364 BibTeX
Copyright © Wed Jun 4 18:57:10 2008
by Michael Ley (ley@uni-trier.de)
