Theoretical Computer Science, Volume 4

Volume 4, Number 1, February 1977

Robin Milner: Fully Abstract Models of Typed lambda-Calculi. 1-22 BibTeX
Zvi Galil: On the Complexity of Regular Resolution and the Davis-Putnam Procedure. 23-46 BibTeX
Marcel Paul Schützenberger: Sur une Variante des Fonctions Sequentielles. 47-57 BibTeX
Daniel J. Lehmann: Algebraic Structures for Transitive Closure. 59-76 BibTeX
Jean Vuillemin: Comment Verifier l'Associativite d'une Table de Groupe. 77-82 BibTeX
Matti Linna: A Decidability Result for Deterministic omega-Context-Free Languages. 83-98 BibTeX
Toshiro Araki, Tadao Kasami: Decidable Problems on the Strong Connectivity of Petri Net Reachability Sets. 99-119 BibTeX
Shimon Even, Robert Endre Tarjan: Corrigendum: Computing an st-Numbering. TCS 2(1976):339-344. 123 BibTeX

George Markowsky: Categories of Chain-Complete Posets. 125-135 BibTeX
Chiharu Hosono, Masahiko Sato: The Retracts in P omega do not Form a Continuous Lattice - A Solution to Scott's Problem. 137-142 BibTeX
Matthew M. Geller, Harry B. Hunt III, Thomas G. Szymanski, Jeffrey D. Ullman: Economy of Description by Parsers, DPDA'S, and PDA'S. 143-153 BibTeX
Jean Françon: On the Analysis of Algorithms for Trees. 155-169 BibTeX
Hans-Georg Stork: On the Paging-Complexity of Periodic Arrangements. 171-197 BibTeX
Hermann A. Maurer, Thomas Ottmann, Arto Salomaa: On the Form Equivalence of L-Forms. 199-225 BibTeX
Jeanne Ferrante, James R. Geiser: An Efficient Decision Procedure for the Theory of Rational Order. 227-233 BibTeX
Daniel J. Lehmann: A Note on Schnorr's Separatedness. 235 BibTeX

Christos H. Papadimitriou: The Euclidean Traveling Salesman Problem is NP-Complete. 237-244 BibTeX
Matthew M. Geller, Michael A. Harrison: On LR(k) Grammars and Languages. 245-276 BibTeX
Neil D. Jones, Lawrence H. Landweber, Y. Edmund Lien: Complexity of Some Problems in Petri Nets. 277-299 BibTeX
Robert P. Daley: On the Inference of Optimal Descriptions. 301-319 BibTeX
Tmima Olshansky, Amir Pnueli: A Direct Algorithm for Checking Equivalence of LL(k) Grammars. 321-349 BibTeX