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 BibTeX
Brenda S. Baker: Parameterized Pattern Matching: Algorithms and Applications. 28-42 BibTeX
Noam Nisan, David Zuckerman: Randomness is Linear in Space. 43-52 BibTeX
Nicholas Pippenger: Self-Routing Superconcentrators. 53-60 BibTeX

Regular Articles

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

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 BibTeX
Martin Kummer, Frank Stephan: On the Structure of Degrees of Inferability. 214-238 BibTeX
Hans-Ulrich Simon: General Bounds on the Number of Examples Needed for Learning Probabilistic Concepts. 239-254 BibTeX
Sally A. Goldman, H. David Mathias: Teaching a Smarter Learner. 255-267 BibTeX
Nader H. Bshouty, Sally A. Goldman, Thomas R. Hancock, Sleiman Matar: Asking Questions to Minimize Errors. 268-286 BibTeX

Regular Articles

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

Seventh Annual Workshop on Computational Learning Theory (COLT) 1994

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

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