JCSS, Volume 51

Volume 51, Number 1, August 1995

Selected Papers of PODS 1990

• 
  Yehoshua Sagiv:
  Editor's Forword. 1
• 
  Froduald Kabanza, Jean-Marc Stévenne, Pierre Wolper:
  Handling Infinite Temporal Data. 3-17
• 
  Richard J. Lipton, Jeffrey F. Naughton:
  Query Size Estimation by Adaptive Sampling. 18-25
• 
  Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz:
  Constraint Query Languages. 26-52
• 
  Divyakant Agrawal, Amr El Abbadi:
  Constrained Shared Locks for Increased Concurrency in Databases. 53-63
• 
  John S. Schlipf:
  The Expressive Powers of the Logic Programming Semantics. 64-86
• 
  Yatin P. Saraiya:
  On the Efficiency of Transforming Database Logic Programs. 87-109
• 
  Phokion G. Kolaitis, Moshe Y. Vardi:
  On the Expressive Power of Datalog: Tools and a Case Study. 110-134

Volume 51, Number 2, October 1995

• 
  Alberto O. Mendelzon:
  Editor's Foreword. 135
• 
  S. Seshadri, Jeffrey F. Naughton:
  On the Expected Size of Recursive Datalog Queries. 137-148
• 
  Stéphane Grumbach, Victor Vianu:
  Tractable Query Languages for Complex Object Databases. 149-167
• 
  Donald B. Johnson, Larry Raab:
  A Tight Upper Bound on the Benefits of Replica Control Protocols. 168-176
• 
  Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis:
  On Datalog vs. Polynomial Time. 177-196
• 
  Richard Helm, Kim Marriott, Martin Odersky:
  Spatial Query Optimization: From Boolean Constraints to Range Queries. 197-210
• 
  Hector Garcia-Molina, Kenneth Salem:
  Non-deterministic Queue Operations. 211-222
• 
  Catriel Beeri, Tova Milo:
  Subtyping in OODBs. 223-243
• 
  Sumit Ganguly, Sergio Greco, Carlo Zaniolo:
  Extrema Predicates in Deductive Databases. 244-259
• 
  Tomás Feder, Rajeev Motwani:
  Clique Partitions, Graph Compression and Speeding-Up Algorithms. 261-272
• 
  Ganesh Baliga, John Case, Sanjay Jain:
  Language Learning with Some Negative Information. 273-285
• 
  Richard Cole, Ofer Zajicek:
  The Expected Advantage of Asynchrony. 286-300
• 
  Hesham H. Ali, Hesham El-Rewini:
  An Optimal Algorithm for Scheduling Interval Ordered Tasks with Communication on N Processors. 301-306
• 
  Vince Grolmusz:
  Separating the Communication Complexities of MOD m and MOD p Circuits. 307-313
• 
  Jörg Desel, Javier Esparza:
  Shortest Paths in Reachability Graphs. 314-323
• 
  Francine Blanchet-Sadri:
  Some Logical Characterizations of the Dot-Depth Hierarchy and Applications. 324-337

Volume 51, Number 3, December 1995

Selected Papers of

STOC 1992

• 
  Wolfgang Maass:
  Editor's Foreword. 339
• 
  Yair Bartal, Amos Fiat, Yuval Rabani:
  Competitive Algorithms for Distributed Data Management. 341-358
• 
  Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra:
  New Algorithms for an Ancient Scheduling Problem. 359-366
• 
  Avrim Blum, Steven Rudich:
  Fast Learning of k-Term DNF Formulas with Queries. 367-373
• 
  Michael T. Goodrich:
  Planar Separators and Parallel Polygon Triangulation. 374-389
• 
  Jeff Kahn, Jeong Han Kim:
  Entropy and Sorting. 390-399
• 
  Raimund Seidel:
  On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs. 400-403

Regular Articles

• 
  Tomasz Imielinski, Ron van der Meyden, Kumar V. Vadaparty:
  Complexity Tailored Design: A New Design Methodology for Databases With Incomplete Information. 405-432
• 
  Serge Abiteboul, Paris C. Kanellakis, Sridhar Ramaswamy, Emmanuel Waller:
  Method Schemas. 433-455
• 
  Changho Seo, Jongin Lim, Hichum Eun:
  On Comparison and Analysis of Algorithms for Multiplication in GF(2^m). 456-459
• 
  Jirí Adámek, Evelyn Nelson, Jan Reiterman:
  Continuous Algebras Revisited. 460-471
• 
  Konstantin Skodinis, Egon Wanke:
  Emptiness Problems of eNCE Graph Languages. 472-485
• 
  Camino R. Vela, Antonio Bahamonde:
  The Best Nondeterministic Representations of Finite Orderings. 486-494
• 
  Yosi Ben-Asher, Ilan Newman:
  Decision Trees with Boolean Threshold Queries. 495-502
• 
  Takao Asano:
  An O(n log log n) Time Algorithm for Constructing a Graph of Maximum Connectivity with Prescribed Degrees. 503-510
• 
  Nadia Creignou:
  A Dichotomy Theorem for Maximum Generalized Satisfiability Problems. 511-522
• 
  Jan Chomicki, Damian Niwinski:
  On the Feasibility of Checking Temporal Integrity Constraints. 523-535