JCSS, Volume 48

Volume 48, Number 1, February 1994

• 
  Mihály Geréb-Graus, Ming Li:
  Three One-Way Heads Cannot Do String Matching. 1-8
• 
  Stephen J. Hegner:
  Unique Complements and Decomposition of Database Schemata. 9-57
• 
  Joost Engelfriet, Linda Heyker:
  Hypergraph Languages of Bounded Degree. 58-89
• 
  Guy E. Blelloch, James J. Little:
  Parallel Solutions to Geometric Problems in the Scan Model of Computation. 90-115
• 
  Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz:
  Gap-Definable Counting Classes. 116-148
• 
  Jarkko Kari:
  Reversibility and Surjectivity Problems of Cellular Automata. 149-182
• 
  Jin-yi Cai, Anne Condon, Richard J. Lipton:
  PSPACE Is Provable by Two Provers in One Round. 183-193
• 
  Noga Alon, Pavel Pudlák:
  Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely). 194-202

Volume 48, Number 2, April 1994

• 
  Leong Kwan Li:
  Learning Fixed Point Patterns by Recurrent Networks. 203-213
• 
  Omer Berkman, Uzi Vishkin:
  Finding Level-Ancestors in Trees. 214-230
• 
  Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk:
  Exact Lower Time Bounds for Computing Boolean Functions on CREW PRAMs. 231-254
• 
  Marco Cadoli, Maurizio Lenzerini:
  The Complexity of Propositional Closed World Reasoning and Circumscription. 255-310
• 
  Gyora M. Benedek, Alon Itai:
  Nonuniform Learnability. 311-323
• 
  Steven Homer, Luc Longpré:
  On Reductions of NP Sets to Sparse Sets. 324-336
• 
  Douglas R. Stinson:
  Combinatorial Techniques for Universal Hashing. 337-346
• 
  Kai-Yeung Siu, Amir Dembo, Thomas Kailath:
  On the Perceptron Learning Algorithm on Data with High Precision. 347-356
• 
  Alan L. Selman:
  A Taxonomy of Complexity Classes of Functions. 357-381

Volume 48, Number 3, June 1994

Selected Papers of

FOCS 1990

• 
  Marshall W. Bern, David Eppstein, John R. Gilbert:
  Provably Good Mesh Generation. 384-409
• 
  Amos Fiat, Yuval Rabani, Yiftach Ravid:
  Competitive k-Server Algorithms. 410-428
• 
  C. Andrew Neff:
  Specified Precision Polynomial Root Isolation Is in NC. 429-463
• 
  Michael J. Kearns, Robert E. Schapire:
  Efficient Distribution-Free Learning of Probabilistic Concepts. 464-497
• 
  Christos H. Papadimitriou:
  On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. 498-532
• 
  Michael L. Fredman, Dan E. Willard:
  Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths. 533-551