Information and Computation, Volume 67

Volume 67, Number 1-3, 1985

• Jerzy Tiuryn: Preface. 1
• J. M. Robson: Alternation with Restrictions on Looping. 2-11
• Wojciech Rytter: Fast Recognition of Pushdown Automaton and Context-free Languages. 12-22
• Matthew Hennessy, Colin Stirling: The Power of the Future Perfect in Program Logics. 23-52
• José L. Balcázar, Josep Díaz, Joaquim Gabarró: Uniform Characterizations of Non-Uniform Complexity Measures. 53-69
• Andreas Blass, Yuri Gurevich, Dexter Kozen: A Zero-One Law for Logic with a Fixed-Point Operator. 70-90
• Uzi Vishkin: Optimal Parallel Pattern Matching in Strings. 91-113
• Zvi Galil: Optimal Parallel Algorithms for String Matching. 144-157
• Marek Karpinski, Rutger Verbeek: There Is No Polynomial Deterministic Space Simulation of Probabilistic Space with a Two-Way Random-Tape Generator. 158-162
• Helge Szwerinski: Symmetrical One-Dimensional Cellular Spaces. 163-172
• Athanasios K. Tsakalidis: AVL-Trees for Localized Search. 173-194
• Friedhelm Meyer auf der Heide: Lower Time Bounds for Solving Linear Diophantine Equations on Several Parallel Computational Models. 195-211
• Ingo Wegener: The Critical Complexity of All (Monotone) Boolean Functions and Monotone Graph Properties. 212-222