Information and Computation, Volume 71

Volume 71, Number 1-2, 1986

Werner Damm, Andreas Goerdt: An Automata-Theoretical Characterization of the OI-Hierarchy. 1-32
Hirofumi Yokouchi: Retraction Map Categories and Their Applications to the Construction of Lambda Calculus Models. 33-86
Stanislav Zák: An Exponential Lower Bound for Real-Time Branching Programs. 87-94
David B. MacQueen, Gordon D. Plotkin, Ravi Sethi: An Ideal Model for Recursive Polymorphic Types. 95-130
Marek Karpinski, Rutger Verbeek: On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation. 131-142

Hans L. Bodlaender, Jan van Leeuwen: Simulation of Large Networks on Smaller Networks. 143-180
Christos H. Papadimitriou, Mihalis Yannakakis: A Note on Succinct Representations of Graphs. 181-185
Chilukuri K. Mohan, Mandayam K. Srivas: Function Definitions in Term Rewriting and Applicative Programming. 186-217
Karel Culik II, Jozef Gruska, Arto Salomaa: Systolic Trellis Automata: Stability, Decidability and Complexity. 218-230
Hans Heller: On Relativized Exponential and Probabilistic Complexity Classes. 231-243