Theoretical Computer Science, Volume 73

Volume 73, Number 1, 1990

G. Jacopini, G. Sontacchi: Reversible Parallel Computation: An Evolving Space-Model. 1-46
Fred Kröger: On the Interpretability of Arithmetic in Temporal Logic. 47-60
Christian Lavault: Exact Average Message Complexity Values for Distributed Election on Bidirectional Rings of Processors. 61-79
Stefano Varricchio: Factorizations of Free Monoids and Unaviodable Regularities. 81-89
Mark Jerrum, Alistair Sinclair: Fast Uniform Generation of Regular Graphs. 91-100
Hagen Huwig, Axel Poigné: A Note on Inconsistencies Caused by Fixpoints in a Cartesian Closed Category. 101-112

Alexander Aiken: A Theory of Compaction-Based Parallelization. 121-154
You-Chin Fuh, Prateek Mishra: Type Inference with Subtypes. 155-175
Robert Giegerich: Code Selection by Inversion of Order-Sorted Derivors. 177-211
Susan Horwitz: Adding Relational Query Facilities to Software Development Environments. 213-230
Philip Wadler: Deforestation: Transforming Programs to Eliminate Trees. 231-248

Richard Beigel: Bi-Immunity Results for Cheatable Sets. 249-263
Jianer Chen: The Difference Between one Tape and two Tapes: with Respect to Reversal Complexity. 265-278
Jochen Hoffmann, Michael G. Main: Results on NLC Grammars with One-Letter Terminal Alphabets. 279-294
Changwook Kim: Complexity and Decidability for Restricted Classes of Picture Languages. 295-311
J. M. Robson: Strong Time Bounds: Non-Computable Bounds and a Hierarchy Theorem. 313-317
Alan A. Bertossi, Fabrizio Luccio, Elena Lodi, Linda Pagli: String Matching with Weighted Errors. 319-328
Tom Head: The Set of Strings Mapped Into a Submonoid by Iterates of a Morphism. 329-333
William Schmitt: Hopf Algebras and Identities in Free Partially Commutative Monoids. 335-340