default search action
19th FOCS 1978: Ann Arbor, Michigan, USA
- 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978. IEEE Computer Society 1978
Session I
- Jean Françon, Gérard Viennot, Jean Vuillemin:
Description and Analysis of an Efficient Priority Queue Representation. 1-7 - Leonidas J. Guibas, Robert Sedgewick:
A Dichromatic Framework for Balanced Trees. 8-21 - Andrew Chi-Chih Yao:
Should Tables Be Sorted? (Extended Abstract). 22-27 - George S. Lueker:
A Data Structure for Orthogonal Range Queries. 28-34 - Harry R. Lewis:
Complexity of Solvable Cases of the Decision Problem for the Predicate Calculus. 35-47 - David Lichtenstein, Michael Sipser:
GO Is PSPACE Hard. 48-54 - 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
Session II
- Juris Hartmanis, Neil Immerman, Stephen R. Mahaney:
One-Way Log-Tape Reductions. 65-72 - Michael Sipser:
Halting Space-Bounded Computations. 73-74 - Leonard M. Adleman:
Two Theorems on Random Polynomial Time. 75-83 - Rüdiger Reischuk:
Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game (Preliminary Version). 84-91 - Richard E. Ladner
, Richard J. Lipton, Larry J. Stockmeyer:
Alternating Pushdown Automata (Preliminary Report). 92-106 - Janos Simon, John Gill, James Hunt:
On Tape-Bounded Probabilistic Turing Machine Transducers (Extended Abstract). 107-112 - Wolfgang J. Paul, Ernst-Jürgen Prauß, Rüdiger Reischuk:
On Alternation (Preliminary Version). 113-122
Session III
- Joost Engelfriet, Grzegorz Rozenberg:
Equality Languages, Fixed Point Languages and Representations of Recursively Enumerable Languages. 123-126 - Ashok K. Chandra:
Computable Nondeterministic Functions. 127-131 - Manuel Blum, Dexter Kozen:
On the Power of the Compass (or, Why Mazes Are Easier to Search than Graphs). 132-142 - Imre Simon:
Limited Subsets of a Free Monoid. 143-150 - Harold Abelson:
Lower Bounds on Information Transfer in Distributed Computations. 151-158 - 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 - 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
Session IV
- Rohit Parikh:
A Decidability Result for a Second Order Process Logic. 177-183 - Lawrence Flon, Norihisa Suzuki:
Consistent and Complete Proof Rules for the Total Correctness of Parallel Programs. 184-192 - Richard J. Lipton:
Model Theoretic Aspects of Computational Complexity. 193-200 - Bruno Courcelle:
On Recursive Equations Having a Unique Solution. 201-213 - Daniel J. Lehmann:
On the Algebra of Order (Extended Abstract). 214-220 - Akira Kanda:
Data Types as Initial Algebras: A unification of Scottery and ADJery (Extended Abstract). 221-230
Session V
- Zvi Galil:
A New Algorithm for the Maximal Flow Problem. 231-245 - Barbara Simons:
A Fast Algorithm for Single Processor Scheduling. 246-252 - J. Ian Munro, Mike Paterson:
Selection and Sorting with Limited Storage. 253-258 - C. Christen:
Improving the Bounds on Optimal Merging. 259-266 - Chee-Keng Yap:
On Lifted Problems (Preliminary Reports). 267-279 - Andrew Chi-Chih Yao, F. Frances Yao:
On the Average-case Complexity of Selecting k-th Best. 280-289
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-15 19:20 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: