JCSS, Volume 51

Volume 51, Number 1, August 1995

• 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 L. Cole, Ofer Zajicek: The Expected Advantage of Asynchrony. 286-300

Volume 51, Number 3, December 1995

• 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

• 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