- Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies. 2-41 BibTeX
- Eugene M. Luks: Isomorphism of Graphs of Bounded Valence can be Tested in Polynomial Time. 42-65 BibTeX
- Michael O. Rabin: N-Process Mutual Exclusion with Bounded Waiting by 4 Log_2 N-Valued Shared Variable. 66-75 BibTeX
- Neil Immerman: Upper and Lower Bounds for First Order Expressibility. 76-98 BibTeX
- Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. 99-128 BibTeX

- Stephen R. Mahaney: Sparse Complete Sets of NP: Solution of a Conjecture of Berman and Hartmanis. 130-143 BibTeX
- David Harel, Dexter Kozen, Rohit Parikh: Process Logic: Expressiveness, Decidability, Completeness. 144-170 BibTeX
- Philippe Flajolet, Andrew M. Odlyzko: The Average Height of Binary Trees and Other Simple Trees. 171-213 BibTeX
- Jon Louis Bentley, Donna J. Brown: A General Class of Resource Tradeoffs. 214-238 BibTeX
- Gérard P. Huet, Jean-Marie Hullot: Proofs by Induction in Equational Theories with Constructors. 239-266 BibTeX

- Jan A. Bergstra, J. V. Tucker: Expressiveness and the Completeness of Hoare's Logic. 267-284 BibTeX
- Takumi Kasai, Raymond E. Miller: Homomorphisms between Models of Parallel Computation. 285-331 BibTeX
- Christoph M. Hoffmann: Subcomplete Generalizations of Graph Isomorphism. 332-359 BibTeX
- Wolfgang Thomas: Classifying Regular Events in Symbolic Logic. 360-376 BibTeX
- Werner Kuich: An Algebraic Characterization of Some Principal Regulated Rational Cones. 377-401 BibTeX
- Mordechai Ben-Ari, Joseph Y. Halpern, Amir Pnueli: Deterministic Propositional Dynamic Logic: Finite Models, Complexity, and Completeness. 402-417 BibTeX
- Joost Engelfriet, Sven Skyum: The Copying Power of One-State Tree Transducers. 418-435 BibTeX