JCSS, Volume 52

Volume 52, Number 1, February 1996

Selected Papers from STOC 1993

David Eppstein, Zvi Galil, Giuseppe F. Italiano, Thomas H. Spencer: Separator Based Sparsification. I. Planary Testing and Minimum Spanning Trees. 3-27
Brenda S. Baker: Parameterized Pattern Matching: Algorithms and Applications. 28-42
Noam Nisan, David Zuckerman: Randomness is Linear in Space. 43-52
Nicholas Pippenger: Self-Routing Superconcentrators. 53-60

Regular Articles

Alessandra Cherubini, Pierluigi San Pietro: A Polynomial-Time Parsing Algorithm for K-Depth Languages. 61-79
Tsong Yueh Chen: On the Structural Properties of the Set of Fixpoints for Nondeterministic Recursive Definitions. 80-86
Johannes A. La Poutré: Lower Bounds for the Union-Find and the Sp;it-Find Problem on Pointer Machines. 87-99
Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability. 100-124
Leonid Libkin, Limsoon Wong: Semantic Representations and Query Labguages for Or-Sets. 125-142
Egidio Astesiano, Elena Zucca: A Free Construction of Dynamic Terms. 143-156
Dan E. Willard: Applications of Range Query Theory to Relational Data Base Join and Selection Operations. 157-169
Andrzej Ehrenfeucht, Joost Engelfriet, Grzegorz Rozenberg: Finite Languages for the Representation of Finite Graphs. 170-184
Juha Honkala: On Parikh Slender Languages and Power Series. 185-190
Lance Fortnow, Tomoyuki Yamakami: Generic Separations. 191-197

Sixth Annual Workshop on Computational Learning Theory (COLT), July 26-28, 1993

Robert E. Schapire, Linda Sellie: Learning Sparse Multivariate Polynomials over a Field with Queries and Counterexamples. 201-213
Martin Kummer, Frank Stephan: On the Structure of Degrees of Inferability. 214-238
Hans-Ulrich Simon: General Bounds on the Number of Examples Needed for Learning Probabilistic Concepts. 239-254
Sally A. Goldman, H. David Mathias: Teaching a Smarter Learner. 255-267
Nader H. Bshouty, Sally A. Goldman, Thomas R. Hancock, Sleiman Matar: Asking Questions to Minimize Errors. 268-286

Regular Articles

Ajay D. Kshemkalyani: Temporal Interactions of Intervals in Distributed Systems. 287-298
Amihood Amir, Gary Benson, Martin Farach: Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files. 299-307
Rainer Schuler, Tomoyuki Yamakami: Structural Average Case Complexity. 308-348
Vijay K. Vaishnavi: On k-Dimensional Balanced Binary Trees. 328-348
Gavin J. Gibson: Exact Classification with Two-Layer Neural Nets. 349-356
Marc Andries, Jan Paredaens: On Instance-Completeness for Database Query Languages involving Object Creation. 357-373
Shao C. Fang, Santosh S. Venkatesh: Learning Binary Perceptrons Perfectly Efficiently. 374-389

Seventh Annual Workshop on Computational Learning Theory (COLT) 1994

Sanjay Jain, Arun Sharma: The Intrinsic Complexity of Language Identification. 393-402
Martin Kummer, Frank Stephan: Inclusion Problems in Parallel Learning and Games. 403-420
Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, Christino Tamon: Oracles and Queries That Are Sufficient for Exact Learning. 421-433
Peter L. Bartlett, Philip M. Long, Robert C. Williamson: Fat-Shattering and the Learnability of Real-Valued Functions. 434-452
David P. Dobkin, Dimitrios Gunopulos, Wolfgang Maass: Computing the Maximum Bichromatic Discrepancy with Applications to Computer Graphics and Machine Learning. 453-470
Michael Frazier, Sally A. Goldman, Nina Mishra, Leonard Pitt: Learning from a Consistently Ignorant Teacher. 471-492

Limsoon Wong: Normal Forms and Conservative Extension Properties for Query Languages over Collection Types. 495-505
Shinichi Morishita: An Extension of Van Gelder's Alternating Fixpoint to Magic Programs. 506-521
Tirza Hirst, David Harel: Completeness Results for Recursive Data Bases. 522-536
Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen: Reflective Programming in the Relational Algebra. 537-549
Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Arun N. Swami: Selectivity and Cost Estimation for Joins Based on Random Sampling. 550-569
Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. 570-588
Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. 589-612