Theoretical Computer Science, Volume 3

Volume 3, Number 1, 1976

Larry J. Stockmeyer: The Polynomial-Time Hierarchy. 1-22 BibTeX
Celia Wrathall: Complete Sets and the Polynomial-Time Hierarchy. 23-33 BibTeX
Gerard Lallement: Regular Semigroups with D = R as Syntactic Monoids of Prefix Codes. 35-49 BibTeX
Günter Hotz: Schranken für Balanced Trees bei ausgewogenen Verteilungen. 51-59 BibTeX
Burkhard Monien: A Recursive and a Grammatical Characterization of the Exponential-Time Languages. 61-74 BibTeX
Karel Culik II: On the Decidability of the Sequence Equivalence Problem for D0L-Systems. 75-84 BibTeX
Toshiro Araki, Tadao Kasami: Some Decision Problems Related to the Reachability Problem for Petri Nets. 85-104 BibTeX
Neil D. Jones, William T. Laaser: Complete Problems for Deterministic Polynomial Time. 105-117 BibTeX
Franco P. Preparata: Corrigendum: A Fast Stable Sorting Algorithm with Absolutely Minimum Storage. 121 BibTeX , -> TCS 1: 185-190 (1975)

D. C. Jensen, Tomasz Pietrzykowski: Mechanizing omega-Order Type Theory Through Unification. 123-171 BibTeX
David Park: Finiteness is Mu-Ineffable. 173-181 BibTeX
Witold Lipski Jr.: Information Storage and Retrieval - Mathematical Foundations II (Combinatorial Problems). 183-211 BibTeX
Juris Hartmanis, Leonard Berman: On Tape Bounds for Single Letter Alphabet Language Processing. 213-224 BibTeX
Henk Barendregt: A Global Representation of the Recursive Functions in the lambda -Calculus. 225-242 BibTeX
Marcel Paul Schützenberger: Sur les Relations Rationnelles Entre Monoides Libres. 243-259 BibTeX
Peter H. Starke: Analyse und Synthese von Asynchronen ND-Automaten. 261-266 BibTeX
Arnold Schönhage: An Elementary Proof for Strassen's Degree Bound. 267-272 BibTeX

Thomas G. Szymanski: Concerning Bounded-Right-Context Grammars. 273-282 BibTeX
Keijo Ruohonen: Zeros of Z -Rational Functions and D0L Equivalence. 283-292 BibTeX
Ashok K. Chandra, Daniel S. Hirschberg, C. K. Wong: Approximate Algorithms for Some Generalized Knapsack Problems. 293-304 BibTeX
Catriel Beeri: An Improvement on Valiant's Decision Procedure for Equivalence of Deterministic Finite Turn Pushdown Machines. 305-320 BibTeX
Donald E. Knuth, Luis Trabb Pardo: Analysis of a Simple Factorization Algorithm. 321-348 BibTeX
Richard J. Lipton, David P. Dobkin: Complexity Measures and Hierarchies for the Evaluation of Integers and Polynomials. 349-357 BibTeX
David S. Wise: A Strong Pumping Lemma for Context-Free Languages. 359-369 BibTeX
Ronald L. Rivest, Jean Vuillemin: On Recognizing Graph Properties from Adjacency Matrices. 371-384 BibTeX