Theoretical Computer Science, Volume 288

Volume 288, Number 1, October 2002

• Georg Moser: Foreword. 1
• Arnold Beckmann: Notations for exponentiation. 3-19
• Harry Buhrman, Ronald de Wolf: Complexity measures and decision tree complexity: a survey. 21-43
• Alessandra Carbone: Streams and strings in formal proofs. 45-83
• Pierluigi Crescenzi, Gianluca Rossi: On the Hamming distance of constraint satisfaction problems. 85-100
• Thomas Eiter, Helmut Veith: On the complexity of data disjunctions. 101-128
• Erich Grädel: Guarded fixed point logics and the monadic theory of countable trees. 129-152
• Leonid Libkin, Limsoon Wong: Lower bounds for invariant queries in logics with counting. 153-180
• Zenon Sadowski: On an optimal propositional proof system and the structure of easy subsets of TAUT. 181-193

Volume 288, Number 2, October 2002

• Osamu Watanabe, Arun Sharma: Preface. 195-196
• José L. Balcázar, Jorge Castro, David Guijarro, Hans-Ulrich Simon: The consistency dimension and distribution-dependent learning from queries. 197-215
• Eiji Takimoto, Manfred K. Warmuth: Predicting nearly as well as the best pruning of a planar decision graph. 217-235
• Sally A. Goldman, Stephen Kwek: On learning unions of pattern languages and tree patterns in the mistake bound model. 237-254
• Nader H. Bshouty, Nadav Eiron, Eyal Kushilevitz: PAC learning with nasty noise. 255-275
• Steffen Lange, Gunter Grieser: On the power of incremental learning. 277-307
• Frank Stephan, Thomas Zeugmann: Learning classes of approximations to non-recursive function. 309-341