JCSS, Volume 54

Volume 54, Number 1, February 1997

Catriel Beeri, Tova Milo: Comparison of Functional and Predicative Query Paradigms. 3-33
Jan Van den Bussche, Dirk Van Gucht: A Semideterministic Approach to Object Creation and Nondeterminism in Database Queries. 34-47
Christos H. Papadimitriou, Mihalis Yannakakis: Tie-Breaking Semantics and Structural Totality. 48-60
Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. 61-78
Kenneth A. Ross, Yehoshua Sagiv: Monotonic Aggregation in Deductive Database. 79-97
Gösta Grahne, Alberto O. Mendelzon, Peter Z. Revesz: Knowledgebase Transformations. 98-112
Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. 113-135
Anthony J. Bonner, Tomasz Imielinski: Reusing and Modifying Rulebases by Predicate Substitution. 136-166

1st Annual Dagstuhl Seminar on Neural Computing (DSNC) November 7-11, 1994

Marek Karpinski, Angus Macintyre: Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks. 169-176
Pascal Koiran: A Weak Version of the Blum, Shub, and Smale Model. 177-189
Pascal Koiran, Eduardo D. Sontag: Neural Networks with Quadratic VC Dimension. 190-198
György Turán, Farrokh Vatan: On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-In. 199-212

32nd Annual Symposium on Foundations of Computer Science October 2-4, 1991

Dror Lapidot, Adi Shamir: Fully Parallelized Multi-Prover Protocols for NEXP-Time. 215-220
Jaikumar Radhakrishnan: Better Lower Bounds for Monotone Threshold Formulas. 221-226
Donald B. Johnson, Panagiotis Takis Metaxas: Connected Components in O (log^3/2 n) Parallel Time for the CREW PRAM. 227-242
Zvi Galil, Oded Margalit: All Pairs Shortest Paths for Graphs with Small Integer Length Edges. 243-254
Noga Alon, Zvi Galil, Oded Margalit: On the Exponent of the All Pairs Shortest Path Problem. 255-262

32nd Annual Symposium on Foundations of Computer Science November 3-5, 1993

Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton: Breaking the Theta (n log² n) Barrier for Sorting with Faults. 265-304
Uriel Feige: A Spectrum of Time-Space Trade-Offs for Undirected s-t Connectivity. 305-316
Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk: The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations. 317-331
Charles E. Leiserson, Satish Rao, Sivan Toledo: Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers. 332-344
Amir M. Ben-Amram: When Can We Sort in o(n log n) Time? 345-370
Avrim Blum, Ravindran Kannan: Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution. 371-380

Tenth Annual Conference on Structure in Complexity 1995

Manindra Agrawal: DSPACE(n) = NSPACE(n): A Degree Theoretic Characterization. 383-392
Harry Buhrman, Elvira Mayordomo: An Excursion to the Kolmogorov Random Strings. 393-399
Kousha Etessami: Counting Quantifiers, Successor Relations, and Logarithmic Space. 400-411
John D. Rogers: The Isomorphism Conjecture Holds and One-Way Functions Exists Relative to an Oracle. 412-423
James S. Royer: Semantics vs Syntax vs Computations: Machine Models for Type-2 Polynomial-Time Bounded Functionals. 424-436
Nicholas Q. Trân: On P-Immunity of Exponential Time Complete Sets. 437-440

Regular Articles

Domenico Saccà: The Expressive Powers of Stable Models for Bound and Unbound DATALOG Queries. 441-464
Liming Cai, Jianer Chen: On Fixed-Parameter Tractability and Approximability of NP Optimization Problems. 465-474
Yosi Ben-Asher, Ilan Newman: Geometric Approach for Optimal Routing on a Mesh with Buses. 475-486
H. David Mathias: A Model of Interactive Teaching. 487-501
Karl Meinke: A Completeness Theorem for the Expressive Power of Higher-Order Algebraic Specifications. 502-519