Theoretical Computer Science, Volume 4

Volume 4, Number 1, February 1977

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

George Markowsky: Categories of Chain-Complete Posets. 125-135
Chiharu Hosono, Masahiko Sato: The Retracts in P omega do not Form a Continuous Lattice - A Solution to Scott's Problem. 137-142
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
Jean Françon: On the Analysis of Algorithms for Trees. 155-169
Hans-Georg Stork: On the Paging-Complexity of Periodic Arrangements. 171-197
Hermann A. Maurer, Thomas Ottmann, Arto Salomaa: On the Form Equivalence of L-Forms. 199-225
Jeanne Ferrante, James R. Geiser: An Efficient Decision Procedure for the Theory of Rational Order. 227-233
Daniel J. Lehmann: A Note on Schnorr's Separatedness. 235

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