Theoretical Computer Science, Volume 3

Volume 3, Number 1, 1976

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

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

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