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