Information and Computation, Volume 52

Volume 52, Number 1, 1982

Louise Hay: On the Recursion-Theoretic Complexity of Relative Succinctness of Representations of Languages. 2-7
Robert I. Soare: Computational Complexity of Recursively Enumerable Sets. 8-18
Wolfgang Menzel, Volker Sperschneider: Universal Automata with Uniform Bounds on Simulation Time. 19-35
Alan L. Selman: Analogues of Semicursive Sets and Effective Reducibilities to the Study of NP Complexity. 36-51
Robert P. Daley: Busy Beaver Sets: Characterizations and Applications. 52-67
Keh-Jiann Chen: Tradeoffs in the Inductive Inference of Nearly Minimal Size Programs. 68-86
Albert R. Meyer: What is a Model of the Lambda Calculus? 87-122

Daniel N. Osherson, Scott Weinstein: Criteria of Language Learning. 123-138
Michael A. Arbib, Ernest G. Manes: Parametrized Data Types Do Not Need Highly Constrained Parameters. 139-158
Jan A. Bergstra, Anna Chmielinska, Jerzy Tiuryn: Another Incompleteness Result for Hoare's Logic. 159-171
J. Albert, Karel Culik II, Juhani Karhumäki: Test Sets for Context Free Languages and Algebraic Systems of Equations over a Free Monoid. 172-186
Etsuji Tomita: A Direct Branching Algorithm for Checking Equivalence of Some Classes of Deterministic Pushdown Automata. 187-238

Allan Borodin, Joachim von zur Gathen, John E. Hopcroft: Fast Parallel Matrix and GCD Computations. 241-256
Danny Dolev, Michael J. Fischer, Robert J. Fowler, Nancy A. Lynch, H. Raymond Strong: An Efficient Algorithm for Byzantine Agreement without Authentication. 257-274
Bruno Courcelle, Paul Franchi-Zannettacci: On the Equivalence Problem for Attribute Systems. 275-305
C. P. J. Koymans: Models of the Lambda Calculus. 306-332
H. C. M. Kleijn, Grzegorz Rozenberg: Corrigendum: Sequential, Continuous and Parallel Grammars. 364