Theoretical Computer Science, Volume 2

Volume 2, Number 1, 1976

Ivan Mezník: On Some Subclasses of the Class of Generable Languages. 1-7
Joost Engelfriet: Surface Tree Languages and Parallel Derivation Trees. 9-27
Seymour Ginsburg, Jonathan Goldstine, Sheila A. Greibach: Some Uniformly Erasable Families of Languages. 29-44
Gregory J. Chaitin: Information-Theoretic Characterizations of Recursive Infinite Strings. 45-48
Paul M. B. Vitányi: Deterministic Lindenmayer Languages, Nonterminals and Homomorphisms. 49-71
Michael Machtey: Minimal Pairs of Polynomial Degrees with Subexponential Complexity. 73-76
Michel Hack: The Equality Problem for Vector Addition Systems is Undecidable. 77-95
Jean-Jacques Lévy: An Algebraic Interpretation of the lambda beta K-Calculus; and an Application of a Labelled lambda -Calculus. 97-114
Gabor T. Herman, Adrian Walker: On the Stability of some Biological Schemes with Cellular Interactions. 115-130

Herbert Egli, Robert L. Constable: Computability Concepts for Programming Language Semantics. 133-145
Joel I. Seiferas, Robert McNaughton: Regularity-Preserving Relations. 147-154
J. W. de Bakker: Least Fixed Points Revisited. 155-181
Barry K. Rosen: Correctness of Parallel Programs: The Church-Rosser Approach. 183-207
Luc Boasson: Langages Algebriques, Paires Iterantes et Transductions Rationnelles. 209-223
Mark B. Trakhtenbrot: Relationships Between Classes of Monotonic Functions. 225-247
Bostjan Vilfan: Lower Bounds for the Size of Expressions for Certain Functions in d -Ary Logic. 249-269

Oscar H. Ibarra, Sartaj Sahni, Chul E. Kim: Finite Automata with Multiplication. 271-294
Frederick N. Springsteel: On the Pre-AFL of [log n] Space and Related Families of Languages. 295-304
Claus-Peter Schnorr: A Lower Bound on the Number of Additions in Monotone Computations. 305-315
Matti Soittola: Positive Rational Sequences. 317-322
Mariangiola Dezani-Ciancaglini: Characterization of Normal Forms Possessing Inverse in the lambda-beta-mu -Calculus. 323-337
Shimon Even, Robert Endre Tarjan: Computing an st -Numbering. 339-344
Eliana Minicozzi: Some Natural Properties of Strong-Identification in Inductive Inference. 345-360
Harry B. Hunt III, Daniel J. Rosenkrantz, Thomas G. Szymanski: The Covering Problem for Linear Context-Free Grammars. 361-382
Wolfgang J. Paul: Realizing Boolean Functions on Disjoint sets of Variables. 383-396
Mike Paterson, Leslie G. Valiant: Circuit Size is Nonlinear in Depth. 397-400