| 1978 | 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978 |
| 1978 | A Data Structure for Orthogonal Range Queries George S. Lueker |
| 1978 | A Decidability Result for a Second Order Process Logic Rohit Parikh |
| 1978 | A Dichromatic Framework for Balanced Trees Leonidas J. Guibas, Robert Sedgewick |
| 1978 | A Fast Algorithm for Single Processor Scheduling Barbara Simons |
| 1978 | A New Algorithm for the Maximal Flow Problem Zvi Galil |
| 1978 | Alternating Pushdown Automata (Preliminary Report) Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer |
| 1978 | An Optimal Lower Bound on the Number of Total Operations to Compute 0-1 Polynomials over the Field of Complex Numbers Jean-Paul Van de Wiele |
| 1978 | Complexity of Solvable Cases of the Decision Problem for the Predicate Calculus Harry R. Lewis |
| 1978 | Computable Nondeterministic Functions Ashok K. Chandra |
| 1978 | Consistent and Complete Proof Rules for the Total Correctness of Parallel Programs Lawrence Flon, Norihisa Suzuki |
| 1978 | Data Types as Initial Algebras: A unification of Scottery and ADJery (Extended Abstract) Akira Kanda |
| 1978 | Description and Analysis of an Efficient Priority Queue Representation Jean Françon, Gérard Viennot, Jean Vuillemin |
| 1978 | Equality Languages, Fixed Point Languages and Representations of Recursively Enumerable Languages Joost Engelfriet, Grzegorz Rozenberg |
| 1978 | GO Is PSPACE Hard David Lichtenstein, Michael Sipser |
| 1978 | Halting Space-Bounded Computations Michael Sipser |
| 1978 | Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game (Preliminary Version) Rüdiger Reischuk |
| 1978 | Improving the Bounds on Optimal Merging C. Christen |
| 1978 | Limited Subsets of a Free Monoid Imre Simon |
| 1978 | Lower Bounds on Information Transfer in Distributed Computations Harold Abelson |
| 1978 | Model Theoretic Aspects of Computational Complexity Richard J. Lipton |
| 1978 | On Alternation (Preliminary Version) Wolfgang J. Paul, Ernst-Jürgen Prauß, Rüdiger Reischuk |
| 1978 | On Lifted Problems (Preliminary Reports) Chee-Keng Yap |
| 1978 | On Recursive Equations Having a Unique Solution Bruno Courcelle |
| 1978 | On Tape-Bounded Probabilistic Turing Machine Transducers (Extended Abstract) Janos Simon, John Gill, James Hunt |
| 1978 | On the Algebra of Order (Extended Abstract) Daniel J. Lehmann |
| 1978 | On the Average-case Complexity of Selecting k-th Best Andrew Chi-Chih Yao, F. Frances Yao |
| 1978 | On the Power of the Compass (or, Why Mazes Are Easier to Search than Graphs) Manuel Blum, Dexter Kozen |
| 1978 | One-Way Log-Tape Reductions Juris Hartmanis, Neil Immerman, Stephen R. Mahaney |
| 1978 | Selection and Sorting with Limited Storage J. Ian Munro, Mike Paterson |
| 1978 | Should Tables Be Sorted? (Extended Abstract) Andrew Chi-Chih Yao |
| 1978 | Strassen's Algorithm Is not Optimal: Trililnear Technique of Aggregating, Uniting and Canceling for Constructing Fast Algorithms for Matrix Operations Victor Y. Pan |
| 1978 | The Complexity of Checkers on an N * N Board - Preliminary Report Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha |
| 1978 | Two Theorems on Random Polynomial Time Leonard M. Adleman |