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