19. 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. Viennot, Jean Vuillemin: Description and Analysis of an Efficient Priority Queue Representation. 1-7
- 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
- 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
- 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
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
- C. Christen: Improving the Bounds on Optimal Merging. 259-266
- Chee-Keng Yap: On Lifted Problems (Preliminary Reports). 267-279
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team