13. STOC 1981
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 11-13, 1981, Milwaukee, Wisconsin, USA. ACM 1981
- Karel Culik II, Tero Harju:
The omega-Sequence Equivalence Problem for DOL Systems Is Decidable.
1-6 BibTeX
- Paul Chew:
Unique Normal Forms in Term Rewriting Systems with Repeated Variables.
7-18 BibTeX
- Frank M. Hawrusik, K. N. Venkataraman, Ann Yasuhara:
Classes of Functions for Computing on Binary Trees (Extended Abstract).
19-27 BibTeX
- Balakrishnan Krishnamurthy, Robert N. Moll:
Examples of Hard Tautologies in the Propositional Calculus.
28-37 BibTeX
- Daniel Leivant:
The Complexity of Parameter Passing in Polymorphic Procedures (or: Programming Language Theorems Independent of Very Strong Theories).
38-45 BibTeX
- David E. Muller, Paul E. Schupp:
Pushdown Automata, Graphs, Ends, Second-Order Logic, and Reachability Problems.
46-54 BibTeX
- Deborah Joseph, Paul Young:
Fast Programs for Initial Segments and Polynomial Time Computation in Weak Models of Arithmetic (Preliminary Abstract).
55-61 BibTeX
- S. Rao Kosaraju:
Localized Search in Sorted Lists.
62-69 BibTeX
- Bernard Chazelle:
Convex Decompositions of Polyhedra.
70-79 BibTeX
- Chul E. Kim, Azriel Rosenfeld:
Digital Straightness and Convexity (Extended Abstract).
80-89 BibTeX
- Gaston H. Gonnet, J. Ian Munro:
A Linear Probing Sort and its Analysis (Preliminary Draft).
90-95 BibTeX
- Faith E. Fich:
Lower Bounds for the Cycle Detection Problem.
96-105 BibTeX
- Zvi Galil, Joel I. Seiferas:
Time-Space-Optimal String Matching.
106-113 BibTeX
- Daniel Dominic Sleator, Robert Endre Tarjan:
A Data Structure for Dynamic Trees.
114-122 BibTeX
- Andrew Chi-Chih Yao:
On the Parallel Computation for the Knapsack Problem.
123-127 BibTeX
- Eshrat Arjomandi, Michael J. Fischer, Nancy A. Lynch:
A Difference in Efficiency between Synchronous and Asynchronous Systems.
128-132 BibTeX
- John H. Reif, Paul G. Spirakis:
Distributed Algorithms for Synchronizing Interprocess Communication within Real Time.
133-145 BibTeX
- Tat-hung Chan:
Reversal Complexity of Counter Machines.
146-157 BibTeX
- Janos Simon:
Space-Bounded Probabilistic Turing Machine Complexity Classes Are Closed under Complement (Preliminary Version).
158-167 BibTeX
- Alberto Bertoni, Giancarlo Mauri, Nicoletta Sabadini:
A Characterization of the Class of Functions Computable in Polynomial Time on Random Access Machines.
168-176 BibTeX
- Pavol Duris, Zvi Galil:
Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version).
177-188 BibTeX
- K. N. King:
Measures of Parallelism in Alternating Computation Trees (Extended Abstract).
189-201 BibTeX
- Esko Ukkonen, Eljas Soisalon-Soininen:
LALR(k) Testing is PSPACE-Complete.
202-206 BibTeX
- Burkhard Monien, Ivan Hal Sudborough:
Bandwidth Constrained NP-Complete Problems.
207-217 BibTeX
- James B. Orlin:
The Complexity of Dynamic Languages and Dynamic Optimization Problems.
218-227 BibTeX
- Akeo Adachi, Shigeki Iwata, Takumi Kasai:
Low Level Complexity for Combinatorial Games.
228-237 BibTeX
- Ernst W. Mayr:
An Algorithm for the General Petri Net Reachability Problem.
238-246 BibTeX
- Zvi Galil, Wolfgang J. Paul:
An Efficient General Purpose Parallel Computer.
247-262 BibTeX
- Leslie G. Valiant, Gordon J. Brebner:
Universal Schemes for Parallel Communication.
263-277 BibTeX
- Daniel J. Kleitman, Frank Thomson Leighton, Margaret Lepley, Gary L. Miller:
New Layouts for the Shuffle-Exchange Graph (Extended Abstract).
278-292 BibTeX
- Mike Paterson, Walter L. Ruzzo, Lawrence Snyder:
Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract).
293-299 BibTeX
- Richard J. Lipton, Robert Sedgewick:
Lower Bounds for VLSI.
300-307 BibTeX
- Danny Dolev, Kevin Karplus, Alan Siegel, Alex Strong, Jeffrey D. Ullman:
Optimal Wiring between Rectangles.
312-317 BibTeX
- Bernard Chazelle, Louis Monier:
A Model of Computation for VLSI with Related Complexity Results.
318-325 BibTeX
- Jia-Wei Hong, H. T. Kung:
I/O Complexity: The Red-Blue Pebble Game.
326-333 BibTeX
- Jia-Wei Hong, Arnold L. Rosenberg:
Graphs that Are Almost Binary Trees (Preliminary Version).
334-341 BibTeX
- Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky:
Embedded Implicational Dependencies and their Inference Problem.
342-354 BibTeX
- Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis:
Properties of Acyclic Database Schemes.
355-362 BibTeX
- Mihalis Yannakakis:
Issues of Correctness in Database Concurrency Control by Locking.
363-367 BibTeX
- Francesco Parisi-Presicce:
On the Faithful Regular Extensions of Iterative Algebras.
368-374 BibTeX
- Robert S. Streett:
Propositional Dynamic Logic of Looping and Converse.
375-383 BibTeX
- Ashok K. Chandra, Joseph Y. Halpern, Albert R. Meyer, Rohit Parikh:
Equations between Regular Terms and an Application to Process Logic.
384-390 BibTeX
Copyright © Sat May 16 23:43:09 2009
by Michael Ley (ley@uni-trier.de)
