JCSS, Volume 55

Volume 55, Number 1, August 1997

26th Annual ACM Symposium on the Theory of Computing (STOC'94) May 23-25, 1994

Monika Rauch Henzinger, Philip N. Klein, Satish Rao, Sairam Subramanian: Faster Shortest-Path Algorithms for Planar Graphs. 3-23
Alexander A. Razborov, Steven Rudich: Natural Proofs. 24-35
Andrew Chi-Chih Yao: Decision Tree Complexity and Betti Numbers. 36-43
Ramesh Hariharan: Optimal Parallel Suffix Tree Construction. 44-69

Second Annual European Conference on Computational Learning Theory (Euro COLT '95) March 13-15, 1995

Ray J. Solomonoff: The Discovery of Algorithmic Probability. 73-88
Jorma Rissanen: Stochastic Complexity in Learning. 89-95
V. G. Vovk: Learning about the Parameter of the Bernoulli Model. 96-104
Kenji Yamanishi: On-Line Maximum Likelihood Prediction with Respect to General Loss Functions. 105-118
Yoav Freund, Robert E. Schapire: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. 119-139
Dale Schuurmans: Characterizing Rational Versus Exponential learning Curves. 140-160
Leonid Gurvits, Pascal Koiran: Approximation and Learning of Convex Superpositions. 161-170
Shai Ben-David, Michael Lindenbaum: Learning Distributions by Their Density Levels: A Paradigm for Learning without a Teacher. 171-182
John Case, Susanne Kaufmann, Efim B. Kinber, Martin Kummer: Learning Recursive Functions from Approximations. 183-196

13th Annual ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) May 24-26, 1994

Sushant Patnaik, Neil Immerman: Dyn-FO: A Parallel, Dynamic Complexity Class. 199-209
Foto N. Afrati: Bounded Arity Datalog (not-)Queries on Graphs. 210-228
Christos Faloutsos, Ibrahim Kamel: Relaxing the Uniformity and Independence Assumptions Using the Concept of Fractal Dimension. 229-240
Leonid Libkin, Limsoon Wong: Query Languages for Bags and Aggregate Functions. 241-272
Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. 273-298
Dan Suciu, Val Tannen: A Query Language for NC. 299-321
Dan Suciu, Jan Paredaens: The Complexity of the Evaluation of Complex Algebra Expressions. 322-343
Vashudha Krishnaswamy, Divyakant Agrawal, John L. Bruno, Amr El Abbadi: Relative Serializability: An Approach for Relaxing the Atomicity of Transactions. 344-354
Surajit Chaudhuri, Phokion G. Kolaitis: Can Datalog Be Approximated? 355-369

35th Annual Symposium of Computer Science November 20-22, 1994
Symposium Articles

Rakesh K. Sinha, Jayram S. Thathachar: Efficient Oblivious Branching Programs for Threshold and Mod Functions. 373-384
Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma: On the Design of Reliable Boolean Circuits That Contain Partially Unreliable Gates. 385-401
David R. Karger, Daphne Koller: (De)randomized Construction of Small Sample Spaces in NC. 402-413
Jeffrey C. Jackson: An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution. 414-440
Edith Cohen: Size-Estimation Framework with Applications to Transitive Closure and Reachability. 441-453
Karsten Weihe: Maximum (s, t)-Flows in Planar Networks in O(|V|log|V|)-Time. 454-476

Regular Articles

Jean Berstel, Luc Boasson: The Set of Minimal Words of a Context-Free Language is Context-Free. 477-488
Joost Engelfriet, Vincent van Oostrom: Logical Description of Contex-Free Graph Languages. 489-503
Joan Boyar, Rolf Fagerberg, Kim S. Larsen: Amortization Results for Chromatic Search Trees, with an Application to Priority Queues. 504-521
Eddy Fromentin, Michel Raynal: Shared Global States in Distributed Computations. 522-528
G. Y. Yan, Andreas Alexander Albrecht, G. H. F. Young, Chak-Kuen Wong: The Steiner Tree Problem in Orientation Metrics. 529-546
Lane A. Hemaspaandra, Mitsunori Ogihara: Universally Serializable Computation. 547-560