Information and Computation, Volume 82

Volume 82, Number 1, 1989

Jean-Pierre Jouannaud, Emmanuel Kounalis: Automatic Proofs by Induction in Theories without Constructors. 1-33
Jin-yi Cai, Lane A. Hemachandra: Enumerative Counting Is Hard. 34-44
Dan E. Willard: Lower Bounds for the Addition-Subtraction Operations in Orthogonal Range Queries and Related Problems. 45-64
Manfred Droste: Recursive Domain Equations for Concrete Data Structures. 65-80
Nancy A. Lynch, Eugene W. Stark: A Proof of the Kahn Principle for Input/Output Automata. 81-92
Alistair Sinclair, Mark Jerrum: Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. 93-133

Alberto Bertoni, Giancarlo Mauri, Nicoletta Sabadini: Membership Problems for Regular and Context-Free Trace Languages. 135-150
Margaret Montenyohl, Mitchell Wand: Incorporating Static Analysis in a Combinator-Based Compiler. 151-184
László Babai, Shlomo Moran: Proving Properties of Interactive Proofs by a Generalized Counting Technique. 185-197
André Arnold, Anne Dicky: An Algebraic Characterization of Transition System Equivalences. 198-229

Andrzej Ehrenfeucht, David Haussler: Learning Decision Trees from Random Examples. 231-246
Andrzej Ehrenfeucht, David Haussler, Michael J. Kearns, Leslie G. Valiant: A General Lower Bound on the Number of Examples Needed for Learning. 247-261
Richard J. Anderson, Ernst W. Mayr, Manfred K. Warmuth: Parallel Approximation Algorithms for Bin Packing. 262-277
Frank A. Stomp, Willem P. de Roever, Rob Gerth: The upsilon-Calculus as an Assertion-Language for Fairness Arguments. 278-322
Rusins Freivalds, Carl H. Smith, Mahendran Velauthapillai: Trade-Off among Parameters Effecting Inductive Inference. 323-349
Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou: Corrigendum: The Complexity of Cubical Graphs. 350-353