12. STOC 1980
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA. ACM 1980
- Albert R. Meyer, Rohit Parikh:
Definability in Dynamic Logic.
1-7
- John H. Reif:
Logics for Probabilistic Programming (Extended Abstract).
8-13
- Grazyna Mirkowska:
Complete Axiomatization of Algorithmic Properties of Program Schemes with Bounded Nondeterministic Interpretations.
14-21
- Vaughan R. Pratt:
Dynamic Algebras and the Nature of Induction.
22-28
- Esko Ukkonen:
A Decision Method for the Equivalence of some Non-Real-Time Deterministic Pushdown Automata.
29-38
- David A. Plaisted:
On the Distribution of Independent Formulae of Number Theory.
39-44
- Richard A. DeMillo, Richard J. Lipton:
The Consistency of ``P = NP'' and Related Problems with Fragments of Number Theory.
45-57
- Deborah Joseph, Paul Young:
Independence Results in Computer Science? (Preliminary Version).
58-69
- Nancy A. Lynch:
Fast Allocation of Nearby Resources in a Distributed System.
70-81
- Dana Angluin:
Local and Global Properties in Networks of Processors (Extended Abstract).
82-93
- Sam Toueg:
Deadlock- and Livelock-Free Packet Switching Networks.
94-99
- Donna J. Brown:
Kraft Storage and Access for List Implementations (Extended Abstract).
100-107
- H. Raymond Strong:
Vector Execution of Flow Graphs (Extended Abstract).
108-116
- Fereidoon Sadri, Jeffrey D. Ullman:
A Complete Axiomatization for a Large Class of Dependencies in Relational Databases.
117-122
- Ronald Fagin:
Horn Clauses and Database Dependencies (Extended Abstract).
123-134
- Mark H. Overmars, Jan van Leeuwen:
Dynamically Maintaining Configurations in the Plane (Detailed Abstract).
135-145
- Bernard Chazelle, David P. Dobkin:
Detection is Easier than Computation (Extended Abstract).
146-153
- Leonidas J. Guibas, F. Frances Yao:
On Translating a Set of Rectangles.
154-160
- Martin Tompa:
An Optimal Solution to a Wire-Routing Problem (Preliminary Version).
161-176
- Michael J. Fischer, Mike Paterson:
Optimal Tree Layout (Preliminary Version).
177-189
- Richard P. Brent, H. T. Kung:
The Chip Complexity of Binary Arithmetic.
190-200
- James A. Storer:
The Node Cost Measure for Embedding Graphs on the Planar Grid (Extended Abstract).
201-210
- Allen Cypher:
An Approach to The k Paths Problem.
211-217
- David Lichtenstein:
Isomorphism for Graphs Embeddable on the Projective Plane.
218-224
- Gary L. Miller:
Isomorphism Testing for Graphs of Bounded Genus.
225-235
- I. S. Filotti, Jack N. Mayer:
A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (Working Paper).
236-243
- Christoph M. Hoffmann:
Testing Isomorphism on Cone Graphs (Extended Abstract).
244-251
- Ravindran Kannan, Richard J. Lipton:
The Orbit Problem is Decidable.
252-261
- Joos Heintz, Claus-Peter Schnorr:
Testing Polynomials which Are Easy to Compute (Extended Abstract).
262-272
- Oscar H. Ibarra, Brian S. Leininger:
The Complexity of the Equivalence Problem for Straight-Line Programs.
273-280
- Hartmut Ehrig, Bernd Mahr:
Complexity of Implementations on the Level of Algebraic Specifications.
281-293
- Allan Borodin, Stephen A. Cook:
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.
294-301
- Richard M. Karp, Richard J. Lipton:
Some Connections between Nonuniform and Uniform Complexity Classes.
302-309
- Jia-Wei Hong:
On Some Deterministic Space Complexity Problems.
310-317
- Chee-Keng Yap:
Space-time Tradeoffs and First Order Problems in a Model of Programs.
318-325
- David A. Carlson, John E. Savage:
Graph Pebbling with Many Free Pebbles can be Difficult.
326-332
- Joseph JáJá:
Time-Space Tradeoffs for some Algebraic Problems.
339-350
- Nicholas Pippenger:
Comparative Schematology and Pebbling with Auxiliary Pushdowns (Preliminary Version).
351-356
- Wolfgang J. Paul, Joel I. Seiferas, Janos Simon:
An Information-Theoretic Approach to Time Bounds for On-Line Computation (Preliminary Version).
357-367
- Richard M. Karp, Robert Endre Tarjan:
Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract).
368-377
- Peter A. Bloniarz:
A Shortest-Path Algorithm with Expected Time O(n^2 log n log ^* n).
378-384
- John H. Reif, Paul G. Spirakis:
Random Matroids.
385-397
- Kenneth J. Supowit, David A. Plaisted, Edward M. Reingold:
Heuristics for Weighted Perfect Matching.
398-419
- Greg N. Frederickson, Donald B. Johnson:
Generalized Selection and Ranking (Preliminary Version).
420-428
- F. Frances Yao:
Efficient Dynamic Programming Using Quadrangle Inequalities.
429-435
- Errol L. Lloyd:
Critical Path Scheduling of Task Systems with Resource and Processor Constraints (Extended Abstract).
436-446
Copyright © Thu Nov 12 01:23:38 2009
by Michael Ley (ley@uni-trier.de)
