Theoretical Computer Science, Volume 82

Volume 82, Number 1, 1991

Klaus Weihrauch, Christoph Kreitz: Type 2 Computational Complexity of Functions on Cantor's Space. 1-18
Barbara Lando: Periodicity and Ultimate Periodicity of D0L Systems. 19-33
Jean-Jacques Hébrard: An Algorithm for Distinguishing Efficiently Bit-Strings by their Subsequences. 35-49
Ker-I Ko: On Adaptive Versus Nonadaptive Bounded Query Machines. 51-69
Filippo Mignosi: On the Number of Factors of Sturmian Words. 71-84
Marc Snir: Size-depth Trade-Offs for Monotone Arithmetic Circuits. 85-93
Joost Engelfriet, George Leih, Grzegorz Rozenberg: Nonterminal Separation in Graph Grammars. 95-111
Martin Dietzfelbinger, Wolfgang Maass, Georg Schnitger: The Complexity of Matrix Transposition on One-Tape Off-Line Turing Machines. 113-129
Kai Salomaa, Sheng Yu: Decidability of Structural Equivalence of E0L Grammars. 131-139
J. M. Robson: An O (T log T) Reduction from RAM Computations to Satisfiability. 141-149
Cristian Calude, Gabriel Istrate: Determining and Stationary Sets for Some Classes of Partial Recursive Functions. 151-155
Vladimir Palko, Ondrej Sýkora, Imrich Vrto: Area Complexity of Merging. 157-163
Joop M. I. M. Leo: A General Context-Free Parsing Algorithm Running in Linear Time on Every LR (k) Grammar Without Using Lookahead. 165-176

Michel Bauderon: Infinite Hypergraphs I. Basic Properties. 177-214
Giorgio Germano, Stefano Mazzanti: Closure Functions and General Iterates as Reflectors. 215-252
Martín Abadi, Leslie Lamport: The Existence of Refinement Mappings. 253-284
Jos C. M. Baeten, Jan A. Bergstra: Recursive Process Definitions with the State Operator. 285-302
Axel Lukassen, Gottfried Vossen: A Formal Framework for Independence with Respect to Transactions in the Universal Relation Model. 303-327
Wieslaw Szwast: On Horn Spectra. 329-339
Rodney R. Howell, Louis E. Rosier, Hsu-Chun Yen: A Taxonomy of Fairness and Temporal Logic Problems for Petri Nets. 341-372
François Denis, Jean-Paul Delahaye: Is there an Axiomatic Semantics for Standard Pure Prolog. 373-388
Pierre-Louis Curien: An Abstract Framework for Environment Machines. 389-402
Eric Badouel, Philippe Darondeau: On Guarded Recursion. 403-408
R. Hoofman: Weakly Expressive Models for Hoare Logic. 409-418