JCSS, Volume 58

Volume 58, Number 1, February 1999

Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, Takeshi Tokuyama: Mining Optimized Association Rules for Numeric Attributes. 1-12
H. V. Jagadish, Alberto O. Mendelzon, Inderpal Singh Mumick: Managing Conflicts Between Rules. 13-28
Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. 29-53
Serge Abiteboul, Laurent Herr, Jan Van den Bussche: Temporal Connectives Versus Explicit Timestamps to Query Temporal Databases. 54-68
Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Query Processors. 69-82
Ronald Fagin: Combining Fuzzy Information from Multiple Systems. 83-99

Avrim Blum, R. Ravi, Santosh Vempala: A Constant-Factor Approximation Algorithm for the k-MST Problem. 101-108
Michael J. Kearns, Yishay Mansour: On the Boosting Ability of Top-Down Decision Tree Learning Algorithms. 109-128
Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Characterizing Linear Size Circuits in Terms of Pricacy. 129-136
Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. 137-147
Noam Nisan, Amnon Ta-Shma: Extracting Randomness: A Survey and New Constructions. 148-173

Regular Articles

Amir Ben-Dor, Anna R. Karlin, Nathan Linial, Yuri Rabinovich: A Note on the Influence of an epsilon-Biased Random Source. 174-176
Marcus Schaefer: Deciding the Vapnik-Cervonenkis Dimension in Sigma^p₃-Complete. 177-182
Joel Ratsaby, Vitaly Maiorov: On the Learnability of Rich Function Classes. 183-192
Sanjeev Arora, David R. Karger, Marek Karpinski: Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. 193-210
John Case, Mark A. Fulk: Maximal Machine Learnable Classes. 211-214
Gheorghe Antonoiu, Pradip K. Srimani: A Self-Stabilizing Distributed Algorithm to Find the Median of a Tree Graph. 215-221
Carsten Lund, Steven Phillips, Nick Reingold: Paging Against a Distribution and IP Networking. 222-232
Leslie Ann Goldberg, Philip D. MacKenzie: Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers. 232-258

Special Issue on the 36th IEEE Symposium on the Foundations of Computer Sciende

Robert Beals: Algorithms for Matrix Groups and the Tits Alternative. 260-279
Jin-yi Cai, D. Sivakumar: Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis. 280-296
Tamal K. Dey, Sumanta Guha: Transforming Curves on Surfaces. 297-325
Armin Haken, Stephen A. Cook: An Exponential Lower Bound for the Size of Monotone Real Circuits. 326-335
Moni Naor, Omer Reingold: Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions. 336-375
Michael E. Saks, Shiyu Zhou: BP _HSpace(S) subseteq DSPACE(S^3/2). 376-403

Christos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. 407-427
Serge Abiteboul, Victor Vianu: Regular Path Queries with Constraints. 428-452
Giansalvatore Mecca, Paolo Atzeni: Cut and Paste. 453-482
Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht: Complete Geometric Query Languages. 483-511
Joseph Albert, Yannis E. Ioannidis, Raghu Ramakrishnan: Equivalence of Keyed Relational Schemas by Conjunctive Queries. 512-534
Freddy Dumortier, Marc Gyssens, Luc Vandeurzen, Dirk Van Gucht: On the Decidability of Semilinearity for Semialgebraic Sets and Its Implications for Spatial Databases. 535-571

Regular Articles

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey Shallit: The Computational Complexity of Some Problems of Linear Algebra. 572-596
Giovanni Manzini, Luciano Margara: Attractors of Linear Cellular Automata. 597-610
Jürgen Dassow, Victor Mitrana: Stack Cooperation in Multistack Pushdown Automata. 611-621
Jianer Chen, Donald K. Friesen, Hao Zheng: Tight Bound on Johnson's Algorithm for Maximum Satisfiability. 622-640
Adam Krawczyk: The Complexity of Finding a Second Hmiltonian Cycle in Cubic Graphs. 641-647
Lane A. Hemaspaandra, Jörg Rothe: Creating Strong, Total, Commutative, Associative One-Way Functions from Any One-Way Function in Complexity Theory. 648-659