Theoretical Computer Science, Volume 2

Volume 2, Number 1, 1976

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

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

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