19. FOCS 1978:
Ann Arbor,
Michigan
19th Annual Symposium on Foundations of Computer Science,
Ann Arbor, Michigan, 16-18 October 1978. IEEE Computer Society
- Jean Françon, G. Viennot, Jean Vuillemin:
Description and Analysis of an Efficient Priority Queue Representation.
1-7 BibTeX
- Leonidas J. Guibas, Robert Sedgewick:
A Dichromatic Framework for Balanced Trees.
8-21 BibTeX
- Andrew Chi-Chih Yao:
Should Tables Be Sorted? (Extended Abstract).
22-27 BibTeX
- George S. Lueker:
A Data Structure for Orthogonal Range Queries.
28-34 BibTeX
- Harry R. Lewis:
Complexity of Solvable Cases of the Decision Problem for the Predicate Calculus.
35-47 BibTeX
- David Lichtenstein, Michael Sipser:
GO Is PSPACE Hard.
48-54 BibTeX
- Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha:
The Complexity of Checkers on an N * N Board - Preliminary Report.
55-64 BibTeX
- Juris Hartmanis, Neil Immerman, Stephen R. Mahaney:
One-Way Log-Tape Reductions.
65-72 BibTeX
- Michael Sipser:
Halting Space-Bounded Computations.
73-74 BibTeX
- Leonard M. Adleman:
Two Theorems on Random Polynomial Time.
75-83 BibTeX
- Rüdiger Reischuk:
Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game (Preliminary Version).
84-91 BibTeX
- Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer:
Alternating Pushdown Automata (Preliminary Report).
92-106 BibTeX
- Janos Simon, John Gill, James Hunt:
On Tape-Bounded Probabilistic Turing Machine Transducers (Extended Abstract).
107-112 BibTeX
- Wolfgang J. Paul, Ernst J. Prauß, Rüdiger Reischuk:
On Alternation (Preliminary Version).
113-122 BibTeX
- Joost Engelfriet, Grzegorz Rozenberg:
Equality Languages, Fixed Point Languages and Representations of Recursively Enumerable Languages.
123-126 BibTeX
- Ashok K. Chandra:
Computable Nondeterministic Functions.
127-131 BibTeX
- Manuel Blum, Dexter Kozen:
On the Power of the Compass (or, Why Mazes Are Easier to Search than Graphs).
132-142 BibTeX
- Imre Simon:
Limited Subsets of a Free Monoid.
143-150 BibTeX
- Harold Abelson:
Lower Bounds on Information Transfer in Distributed Computations.
151-158 BibTeX
- Jean-Paul Van de Wiele:
An Optimal Lower Bound on the Number of Total Operations to Compute 0-1 Polynomials over the Field of Complex Numbers.
159-165 BibTeX
- Victor Y. Pan:
Strassen's Algorithm Is not Optimal: Trililnear Technique of Aggregating, Uniting and Canceling for Constructing Fast Algorithms for Matrix Operations.
166-176 BibTeX
- Rohit Parikh:
A Decidability Result for a Second Order Process Logic.
177-183 BibTeX
- Lawrence Flon, Norihisa Suzuki:
Consistent and Complete Proof Rules for the Total Correctness of Parallel Programs.
184-192 BibTeX
- Richard J. Lipton:
Model Theoretic Aspects of Computational Complexity.
193-200 BibTeX
- Bruno Courcelle:
On Recursive Equations Having a Unique Solution.
201-213 BibTeX
- Daniel J. Lehmann:
On the Algebra of Order (Extended Abstract).
214-220 BibTeX
- Akira Kanda:
Data Types as Initial Algebras: A unification of Scottery and ADJery (Extended Abstract).
221-230 BibTeX
- Zvi Galil:
A New Algorithm for the Maximal Flow Problem.
231-245 BibTeX
- Barbara Simons:
A Fast Algorithm for Single Processor Scheduling.
246-252 BibTeX
- J. Ian Munro, Mike Paterson:
Selection and Sorting with Limited Storage.
253-258 BibTeX
- C. Christen:
Improving the Bounds on Optimal Merging.
259-266 BibTeX
- Chee-Keng Yap:
On Lifted Problems (Preliminary Reports).
267-279 BibTeX
- Andrew Chi-Chih Yao, F. Frances Yao:
On the Average-case Complexity of Selecting k-th Best.
280-289 BibTeX
Copyright © Sat May 16 23:12:24 2009
by Michael Ley (ley@uni-trier.de)
