JCSS, Volume 59

Volume 59, Number 1, August 1999

Oscar H. Ibarra, Jianwen Su: A Technique for Proving Decidability of Containment and Equivalence of Linear Constraint Queries. 1-28 BibTeX
Yuri Breitbart, Henry F. Korth: Replication and Consistency in a Distributed Environment. 29-69 BibTeX
Zhixiang Chen, Foued Ameur: The Learnability of Unions of Two Rectangles in the Two-Dimensional Discretized Space. 70-83 BibTeX
Pranay Chaudhuri: A Self-Stabilizing Algorithm for Detecting Fundamental Cycles in a Graph. 84-93 BibTeX
Marianne Baudinet, Jan Chomicki, Pierre Wolper: Constraint-Generating Dependencies. 94-115 BibTeX
Gösta Grahne, Matti Nykänen, Esko Ukkonen: Reasoning about Strings in Databases. 116-162 BibTeX

Eric Allender, Klaus Reinhardt, Shiyu Zhou: Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds. 164-181 BibTeX
Harry Buhrman, Lance Fortnow: Two Queries. 182-194 BibTeX
Amos Beimel, Anna Gál: On Arithmetic Branching Programs. 195-220 BibTeX
Jin-yi Cai, Ajay Nerurkar: Approximating the SVP to within a Factor (1+1/dim^xi) Is NP-Hard under Randomized Reductions. 221-239 BibTeX
Lance Fortnow, John D. Rogers: Complexity Limitations on Quantum Computation. 240-252 BibTeX
Oded Goldreich, Madhu Sudan: Computational Indistinguishability: A Sample Hierarchy. 253-269 BibTeX
D. Sivakumar: On Membership Comparable Sets. 270-280 BibTeX
John Watrous: Space-Bounded Quantum Complexity. 281-326 BibTeX
Harry Buhrman, Dieter van Melkebeek: Hard Sets Are Hard to Find. 327-345 BibTeX
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin: Arthur-Merlin Games in Boolean Decision Trees. 346-372 BibTeX

Stephane Gaubert, Alessandro Giua: Petri Net Languages and Infinite Subsets of m. 373-391 BibTeX
Nicolò Cesa-Bianchi: Analysis of Two Gradient-Based Algorithms for On-Line Regression. 392-411 BibTeX
Flavio Corradini, Rocco De Nicola, Anna Labella: Models of Nondeterministic Regular Expressions. 412-449 BibTeX
Lin Chen: Graph Isomorphism and Identification Matrices: Sequential Algorithms. 450-475 BibTeX
Petr Jancar, Javier Esparza, Faron Moller: Petri Nets and Regular Processes. 476-503 BibTeX
Bob P. Weems: Bistable Versions of the Marriages and Roommates Problems. 504-520 BibTeX
Leo Liberti: Structure of the Invertible CA Transformations Group. 521-536 BibTeX
Roberto Barbuti, Nicoletta De Francesco, Antonella Santone, Gigliola Vaglini: Selective Mu-Calculus and Formula-Based Equivalence of Transition Systems. 537-556 BibTeX
Freddy Dumortier, Marc Gyssens, Luc Vandeurzen, Dirk Van Gucht: On the Decidability of Semilinearity for Semialgebraic Sets and Its Implications for Spatial Databases - CORRIGENDUM. 557-562 BibTeX